Блог пользователя Lewin

Автор Lewin, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +135
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +84 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

what about the difficulty of the problems ?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -40 Проголосовать: не нравится

is it rated ?

»
7 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +46 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +58 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    So rejudging wouldn't help much

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It worked, at least mine. Why not?

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

I wish i hadn't not qualified :/

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится
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.

»
7 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Кажется уже слили этот контест

»
7 лет назад, # |
  Проголосовать: нравится +123 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Thanks for your explanations.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -32 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Alice always win if n is odd.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Airplane Arrangments?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve D?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Будет ли разбор?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Deleted!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is B heavy-light decomposition?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +40 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      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...

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the idea to solve problem A?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.