lewin's blog

By lewin, history, 2 weeks 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.

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

»
2 weeks 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).

»
2 weeks 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???

  • »
    »
    2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

what about the difficulty of the problems ?

»
2 weeks 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?

»
2 weeks ago, # |
  Vote: I like it -40 Vote: I do not like it

is it rated ?

»
2 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it
»
2 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

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

»
2 weeks 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?

  • »
    »
    2 weeks 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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +33 Vote: I do not like it

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

»
2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +58 Vote: I do not like it

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

  • »
    »
    2 weeks 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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      Of course they should rejudge only WA submissions.

  • »
    »
    2 weeks 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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It worked, at least mine. Why not?

      • »
        »
        »
        »
        2 weeks 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

        • »
          »
          »
          »
          »
          2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 weeks 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.

»
2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

I wish i hadn't not qualified :/

»
2 weeks 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.

»
2 weeks 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.

»
2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

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

»
2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thanks for your explanations.

  • »
    »
    13 days 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.

»
2 weeks 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?

  • »
    »
    2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Alice always win if n is odd.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Airplane Arrangments?

  • »
    »
    2 weeks 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).

»
2 weeks 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.com/contest/838/submission/29256987

  • »
    »
    2 weeks 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

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve D?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks 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.

»
2 weeks 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!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Where is editorial?

    • »
      »
      »
      2 weeks 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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Would the editorials be uploaded on Codeforces for this round?

      • »
        »
        »
        »
        2 weeks 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?

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 days 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.

    • »
      »
      »
      13 days 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.

»
2 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Deleted!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is B heavy-light decomposition?

  • »
    »
    2 weeks 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.

»
2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    2 weeks 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?

    • »
      »
      »
      13 days 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...

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can anyone provide counterexample for this solution?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the idea to solve problem A?

»
13 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Cause this trick with changing the statement during the contest, Pembesar Payudara when many people made submissions which were actually correct

»
11 days ago, # |
  Vote: I like it -11 Vote: I do not like it

LOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOL

»
10 days 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).

  • »
    »
    9 days 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?

»
10 days 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.

»
10 days 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?

  • »
    »
    9 days 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.