We invite you to participate in CodeChef’s Starters 72, this Wednesday, 4th January.
Time: 8 PM — 11:00 PM IST
Joining us on the problem setting panel are:
- Setters: Sahil still_me Tiwari, Reyaan reyaan44 Jagnani
- Testers: Hriday the_hyp0cr1t3, Jatin rivalq Garg
- Statement Verifier: Nishank IceKnight1093 Suresh
- Video Editorialists: Garvit garvitvirmani0 Virmani, Madhav jhamadhav Jha, Suraj jhasuraj01 Jha, Jwala jwalapc
- Text Editorialists: Nishank IceKnight1093 Suresh
- Contest Admins: Nishank IceKnight1093 Suresh, Satyam satyam343
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest.
The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Hope to see you participating. Good Luck!
Auto comment: topic has been updated by satyam343 (previous revision, new revision, compare).
Test comment. (Blog doesn't show up on recent actions)
How to solve No Sequence
Hint: attempt to set every element in the answer to 1 at first, then decrement when you need, some small optimization may be needed
Cases $$$k = 1, 2$$$ are trivial. Notice that some element of $$$\{s - 1, s, s + 1\}$$$ should be divisible by $$$k$$$. Because $$$k \geq 3$$$ it must be exactly one element if solution exists. That way we found $$$b_1$$$. Solve recursively for others.
I have an easy intuitive solution for that.
Just take a var = 0 and check for decreasing powers of K(from n-1 to 0), whether adding/subtracting this to/from var will result in bringing var closer to s. Fill suitably 1 or -1 at this index in the answer array, and modify var.
After traversing all powers of K, if var != s, then print -2, else print the answer array.
My submission
Note why this works is because of the fact that K^N will always be greater than sum of K^(N-1) + K^(N-2) + .... + K + 1, so K^N will have the greatest hand in determining the closeness of var to required s.
Bro why u have taken abs(curr + powers[i] — s) instead of s-powers[i]-curr
You can take that also.
It'll give the same result, abs() just compares the absolute difference.
Story of the contest: I am happy with my performance solving (only !) 2 problems in a div2 round, and not even a speed solve
did anyone solve XOR Tree using multiset(to find the greatest xor value of leaf)?
Why multiset? You can use trie to get the maximum xor value.
I haven't learnt using trie yet :(
Then, I think it's time to learn it :)
seems like it lol
Edit: I am deeply ashamed of myself to discover that I had an integer overflow in pre-computation.
How to solve Good Arrangements ?
My idea is to fix a starting value, and then using some combinatorics formula to calculate arrangements. Am I in the right direction ?
Let's say we fixed a pivot = $$$v$$$, then let's say $$$c$$$ is $$$a_i = v$$$, $$$x$$$ is $$$a_i > v$$$ and $$$y$$$ is $$$a_i < v$$$. Then, the formula I got is:
which we have to sum up over all different $$$v$$$.
We need to fix not only the starting element — $$$v$$$ but also the amount of it in the beginning — $$$c$$$. Then your formulas are almost correct
Try to fix the number of indices i such that b[i] is the prefix maximum, then, since we know that maximums will occur in increasing order and minimums in decreasing order, we only need to choose the indices where we will keep the maximums.
there is a caveat, though, you need to make sure that all places other than the maximums will surely be minimums to avoid overcounting; try to figure that out, it isn't very hard.
Yeah, your formula is correct
Could you explain the reasoning behind this?
Editorial