Lewin's blog

Invitation to IndiaHacks 2nd Elimination 2017
By Lewin, history, 7 years ago, In English

On Sunday, August 6th, 22:00 IST, we will hold the 2nd elimination for IndiaHacks (some more details here). The top 900 individuals who qualified through previous rounds will have the opportunity to participate in this round. The top 25 global participants and top 25 Indian participants will advance to the final round. The link to the contest is here.

After the official round is over, the next morning, on Monday, August 7th, 11:35 IST, we'll hold an unofficial unrated mirror here on Codeforces. This mirror will have ICPC rules. For participants of the official round, please hold off on discussing the problems publicly until after this mirror is over.

I was the author of the problems in this set, and I hope you will enjoy the problems. I would like to thank zemen for testing the set, Arpa for writing editorials, r3gz3n for his help on the HackerEarth side, KAN for helping us set up the mirror contest, and of course MikeMirzayanov for the great Polygon/Codeforces platform.

The round will consist of 6 problems and you will have 3 hours to complete them. Please note that the problems will be randomly arranged in both rounds, since I couldn't figure out how to sort them by difficulty. Be sure to read all the problems.

UPD1: Updated time of official round and posted link to contest.

UPD2: We should have updated the leaderboard to accept solutions that followed the first version of the first problem. We have also increased the number of finalists to 60 total (30 global + 30 indian) based on this new leaderboard.

UPD3: Here is the list of qualifiers. Congratulations to everyone.

global
indian
  • Vote: I like it
  • +135
  • Vote: I do not like it

Comments Comments (79)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Lewin (previous revision, new revision, compare).

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

6 problems, 3 hours, looks much similar to Codeforces rounds style, why not making it rated???

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

    For this round, it's almost impossible for us to prevent leaking problems since there's 900 official participants. We should be able to have a rated version for the final round where leaking is less likely.

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

what about the difficulty of the problems ?

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

I have not participated in the previous rounds. Am I able to participate in this round?

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

is it rated ?

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

Second elimination is live. Here is the link of the contest.  https://www.hackerearth.com/challenge/competitive/indiahacks-2017-programming-wave-20-eliminator/problems/

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

was contest extended? why there's no info about that?

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

Was it possible to understand that there's no partial scoring in this round without actually submitting the solution?

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

    It turns out that there's line

    Marking Scheme: Marks are awarded when all the testcases pass.

    in the same block with TL and ML

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

      This line is also presented in P5, but tourist got 74/100...?

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

Lewin Problem Binary Blocks is gonna be rejudged, doesn't it? Cause this trick with changing the statement during the contest, when many people made submissions which were actually correct, is not a good way to handle the issue.

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

    Good enough for HackerFuckingEarth. Silently change the statement, silently extend the contest.

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

    I dont understand the issue because I started from another problem, and when I solved Binary Blocks the statement was already updated. However I think that if they rejudge and I get WA, then it will be unfair for me

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

      Of course they should rejudge only WA submissions.

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

    Solution for initial problem didn't work for sample, did it?

    So rejudging wouldn't help much

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

      It worked, at least mine. Why not?

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

        Hm, maybe I didn't read the first version of the statement and just didn't understand the statement(or may be there were several incorrect versions) but my solution to what I read first gave answer that is less then expected

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

          The version I was solving was that the table is padded with zeroes, and it was confirmed in discussions. Than the answer on sample is the same.

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

    Yes, I'll see if we can get it rejudged.

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

The statement for first problem is bullshit. You must change model solution not change statement.

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

It seems that kut_msm1993 was trying to solve many hard problems simultaneously lol.

You can check his submission log here by clicking "All Submissions" and enter the username in the "Search User" box.

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

I wish i hadn't not qualified :/

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

How does memory work at Hackerearth?
I was only using static memory and kept getting this verdict several times.

→ Reply
»
7 years ago, # |
  Vote: I like it +52 Vote: I do not like it
problems will be randomly arranged

but p0 was the easiest. so to me seems like a notorious shuffling.

p4: when you need an extra problem for tomorrow's contest but it's hackerearth where nobody cares about quality, so you're fine.

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

Was it intentional that a brute force solution passes in P1? I coded my solution but got WA and couldn't find a bug. I wrote a brute force solution for testing and to be sure of its correctness I decided to submit it. I was really surprised when it just passed all tests.

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

Wish each problem is high-quality.good luck and have fun!

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

I want to explain what happened with the official round. I was on a plane for about 12 hours and I wasn't able to watch over the beginning of the contest, so I wasn't able to do some last minute proof-reading and I couldn't answer clarifications initially. I told Arpa to watch over the round while I was unavailable (and I'm sorry to Arpa for putting you in this situation).

Anyways, I was able to get some brief internet access after I landed about an hour and a half into the contest, and I saw that there was a lot of confusion about Binary Blocks, which Arpa tried his best to address. Unfortunately, the problem statement was incorrect, so some of his clarifications were also incorrect, which is entirely my fault. I tried my best to clarify the situation, but I had to leave again in order to continue on my journey and get some sleep. I had decided it was best to make an announcement that the statement has been corrected, and time will be extended (but it looks like the announcement didn't work for some reason). Now, looking back, that may not have been the best solution, but I didn't feel I had enough time to change the test data to the first version of the statement. Anyways, I'll see what we can do about it and think about fair solutions to this issue (it may take some time, but I hope to get this done by next week).

I apologize for these issues. I probably shouldn't have agreed to write an important round if I knew I couldn't watch over it, and I promise it won't happen again.

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

    Thanks for your explanations.

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

    If possible please host the contest again. Just because of that problem many were not able to qualify as they wasted alot of time on that question.

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

So sqrt-decomposition won't work in time for B? And the observation that Alice will always win if the initial string has an even number of ways to re-permute is wrong in C?

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

    I don't think it's wrong, however it's not easy to find all the strings that have even number of ways to re-permute. I tried some recursion that finds all such strings, but I'm getting wa 6.

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

    Alice always win if n is odd.

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

How to solve Airplane Arrangments?

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

    Let's reformulate the problem. Suppose we have n + 1 seats arranged in a circle and every passenger chooses a seat and a direction. We have (2(n + 1))m ways to do this. Now, since it's a circle every passenger will find a seat. Some seats will remain empty. An arrangement is good if the last seat is empty. In this situation, the same arrangement works for the original problem. Since exactly n + 1 - m seats will be empty, and every seat has an equal probability of being empty through all possible arrangements, the answer is (2(n + 1))m * (n + 1 - m) / (n + 1).

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

Am I the one who solved B without lazy segment tree? http://codeforces.me/contest/838/submission/29256987

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

    So you call this function

    intt dfs_dis (intt v) {
    intt res = rootweight[v];
    for (int i = 0; i < g[v].size(); i++) {
        int to = g[v][i];
        intt tmp = dfs_dis (to) + parweight[to];
        res = min (res, tmp);
    }
    return res;
}

    for each query:

    printf("%lld\n", distoroot (u) + dis (v));

    Weak test data? Or I am missing something? If the former, you didn't really solve the problem :P

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

How to solve D?

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

can someone tell me whats wrong with my solution for b ? 29256918

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

    My approach is using Lazy propagation on the array of depth (+return edge) in euler tour order. Which works well in time. Your approach seems different. If you clarify it then it will be easier to debug.

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

Btw editorials for Airplanes and Earnings problems suck :( Hope they will be updated or at least explained in more details here, because the most interesting parts are skipped. Yes maybe I can understand them after some thinking reading the code, but I thought that editorial should explain the ideas by itself too.

On the other side, I must say that problems were interesting to solve, except the issue in the easiest problem and yet another standard problem to write segment tree on Euler tour. So thank you for the contest!

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

    Where is editorial?

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

      They are on hackerearth contest page, but I believe it is available only to participants of IndiaHacks.

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

        Would the editorials be uploaded on Codeforces for this round?

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

        I could not find editorial on contest page although I participated in the contest. Can you give me the link?

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

          There is a button 'editorial' on each problem page.

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

    This problem is extremely similar to problem G from IPSC 2009, and the editorial is explained very well there.

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

      Yeah thank you, it turned out that the problem statement of Airplanes was too hard for me to understand correctly, now everything is clear, cool solution.

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

Deleted!

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

Is B heavy-light decomposition?

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

    I think that it's possible to solve B with HLD but you can use normal max-seg-tree.

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

Why greedy algorithm in Prob.E is not right? For a start point A, there are left side and right side, for example, first go to the right side, then to the left side, then right side... Then you enumerate all the point as start point, enumerate both side as a start direction.

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

    You might need to walk by edge of convex. :) Its clearly DP.

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

    What do you mean by greedy algorithm in Prob.E? How do you expect someone to answer your question?

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

      For a start point A, there are left side and right side, for example, first go to the right side, then to the left side, then right side...

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

        Can anyone provide counterexample for this solution?

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

What is the idea to solve problem A?

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

Auto comment: topic has been updated by Lewin (previous revision, new revision, compare).

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

    How to see only Indian Rankings ?

    Or could you say what is the rank of the 30th Indian on the ranklist?

    Also do Indians in top 30 count under global or Indians?

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

Somehow I wasn't notified of the contest through email and didn't remember till today when I read this post.

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

Am I the only one who read information on the contest page and aimed at top 50 because there was nothing about top 25 global and top 25 Indian?

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

    I have updated the details. We have increased the number of finalists to 60 total (30 global + 30 Indian) based on this new leaderboard. Sorry for the inconvenience.

    → Reply