Errichto's blog

CodeChef April Challenge — a few days left
By Errichto, 7 years ago, In English

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!

  • Vote: I like it
  • +38
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it -9 Vote: I do not like it

In problem Chef and digits can larger sample cases(>10^5) be added?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Why do you think you should ask this question here instead of comments under the problem?

    → Reply
»
7 years ago, # |
  Vote: I like it +32 Vote: I do not like it

It seems that the problems are easier than usual.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    While I agree that hard problems should be harder, I think that first few problems should be even easier than in the ongoing contest.

    → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it -22 Vote: I do not like it

Long contests are a waste of time.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Sure.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +38 Vote: I do not like it

    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 :)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +66 Vote: I do not like it

      So You're telling me that I have been starving for the past 7 days for no reason ?

      → Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Long Contest teaches the most. Keep trying a problem until 100 points AC verdict is the best thing. :D

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell the solution for heavy light decomposition, the last problem? Thanks in advance. :)

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Fastest rating update ever! o_O

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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++) ... with for(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).

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I understood the flaw in my solution.

      → Reply