Hello, Codeforces!
The CodeChef April Challenge will end in less than 4 days. You can still join and reach the top of the leaderboard. There are 9 binary/subtask problems and 1 approximation problem (a tie-breaker).
I was a tester and an author of some problems. Other problem setters are: gautam27, Frank Chen, cgy4ever, Sereja, and PraveenDhinwa who is also an editorialist. Translators: CherryTree (Russian), Team VNOI (Vietnamese) and huzecong (Mandarin). Language verifier: arjunarul.
There is no registration required, anybody with a CodeChef handle can participate. Top participants can win CodeChef laddus (details on the contest page). Prizes for first two places are 400$ and 300$.
I wish you great fun and no frustrating bugs. See you on the leaderboard!
In problem Chef and digits can larger sample cases(>10^5) be added?
Why do you think you should ask this question here instead of comments under the problem?
It seems that the problems are easier than usual.
While I agree that hard problems should be harder, I think that first few problems should be even easier than in the ongoing contest.
Long contests are a waste of time.
Sure.
in case you don't know: it's okay to eat, work, sleep and have normal life during an ongoing long challenge that you're participating in :)
So You're telling me that I have been starving for the past 7 days for no reason ?
Long Contest teaches the most. Keep trying a problem until 100 points AC verdict is the best thing. :D
Can anyone tell the solution for heavy light decomposition, the last problem? Thanks in advance. :)
The editorial should help you. https://discuss.codechef.com/questions/95668/hld-editorial
Fastest rating update ever! o_O
For problem Random Greed I have done very similar to What editorial tells.
My solution for p>0.1 case just does a brute force as mentioned in editorial.
My solution for p<0.1 case stores all the wall locations and then for each point goes through all the walls and finds minimum number of steps you will hit the wall from that starting point in O(W) time for each point. Similar time to editorial. This is my code It will be great help if you can go through the code and suggest a way to optimize it. Thanks a lot.
In some way, your solution is very similar to the intended one. You can make it faster by replacing
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=0;k<wa.size();k++) ...withfor(i = 1 ... n) for(j = 1 ... n) for(coordinates of #'s close to (i,j)) ...— since the string is generated uniformly at random, you can expect that blocked cells far away from (i,j) won't affect the answer in (i,j).Thanks for reply! I even tried something like that My other submission
I think this is what you are talking about. It did not help still. Though I did not completely ignore the walls that are far away. I tried breaking from the loop whenever going far away is not of much use. Are you saying I should just completely ignore them? Did expected solution do that?
One bonus question with HLD (which for me is more interesting than solving the original task): construct a tree with the answer is Ω(log2n).
So we know: the traditional way of selecting heavy edge (by choose the one with max number of nodes) is indeed optimal asymptotically.
For HLD, I tried this greedy approach. At each node, I stored the length of the longest path starting at that node in its sub-tree and the length of the continuous segment of heavy nodes at the start of that path. Now the recursion part. At each node, I will extend heavy edge to that node for which the length of the longest path is maximum. If 2 or more nodes have the same longest path, I will extend the heavy edge to the node for which the length of continuous segment of heavy nodes at the start is less. Someone please explain why this approach failed.
Link to my submission
Consider the following tree. First 9 edges are 1-2,2-3,3-4,....,9-10. Remaining 8 edges are 1-11,11-12,12-13,13-14,14-15,15-16,16-17,16-18. According to your greedy approach, the answer for this tree would be 6. But we can switch the heavy edge from 1, and get the answer to be 5.
EDIT: I just ran your submission for this input and the output of your code was 4. That certainly cannot be true as we have one path of length 9. The minimum cost for that path itself is ceil(log2(9))+1= 5
Thanks, I understood the flaw in my solution.