GlebsHP's blog

Round 1 of Yandex.Algorithm 2017
By GlebsHP, history, 8 years ago, translation, In English

Hello everybody!

Tomorrow, at 10:00 Moscow time will be held Round 1 of Yandex.Algorithm competition, authored by me. I would like to thank Zlobober for all the job he does to make this competition interesting, MikeMirzayanov for the great polygon that ease the preparation process a lot, and everyone, who tested the round and made useful comments. Of course, we did our best to make the problem diverse by topics and difficulty.

See you in the competition dashboard!

UPD Thanks to everyone who participated, hope each of you found at least one interesting problem. We apologize for the situation with problem F, we have googled for all the problems and asked all testers whether they have seen such problems or not, but that didn't helped. The editorial has been published.

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

Comments Comments (64)
| Write comment?
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

What do we have to do in order to qualify to the second round?

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

    Nothing, everyone can participate in rounds 1-3. In each round, top 30 get some points, and in the end, people with the most points go to the finals.

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

How do you select t-shirt winners? If there are only 4 rounds with 30 people earning any points.

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

    If two participants have the same amount of points earned(0), lowest rank in all 4 rounds matters. I dont actually understand what happens if somebody skips one round but in others he is like top50, he loses his chance to win a t-shirt?

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

      What if you didn't participate in all 4 rounds?

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

        I guess the ranks are compared numerically, i.e., the 1st place is "lower" than the 2nd place.

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

        To advance to final you have to submit a solution to at least one task. Nobody said about submitting to get tshirt. Hack found!

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

Problem F == http://agc009.contest.atcoder.jp/tasks/agc009_d == http://main.edu.pl/en/archive/oi/11/jas

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

    It has a nice solution, need to make sure that everyone has seen this problem!

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

    That's a great pity for us, but nobody among contest authors and testers have seen any of these problems.

    Both me and GlebsHP tried to Google this problem before the contest but we didn't succeed. As you can see, all three versions of this problem have almost nothing common in statements, so it was almost impossible to find them without seeing any of them before.

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

      I haven't participated in a lot of contests recently, so I haven't seen it either. But I don't like when people submit something in 5 minutes that's obviously not an easy problem. Probably, I won't waste my time on Yandex contests any more.

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

        That's frustrating and not a good thing to happen, but definitely not Yandex's fault (it's impossible to read and remember all existing tasks in the world). The same thing has happened in TopCoder, Codeforces, AtCoder, Facebook, etc.

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

    Okay, and how to solve it? :)

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

How to solve C?

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

    For every vertex, in any order: look at numbers of components in neighbours, choose minimal that is absent.

    Proof: In the end, for component number K, there are edges to components K-1, K-2, K-3,... because otherwise we wouldn't be able to assign this number to some vertex.

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

      What's the efficient way to get that mex?, I used set, but unfortunately TLE :(

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

        Use a set, put all number from 1 to N in it. Then for each u, iterate every v that is adjacent to u, remove ans[v] from the set. Then mex will be the smallest value in the set. After that, put all ans[v] back into the set. P.s: ans[v] is the answer for vertex v.

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

          What do you mean by ans[v] here?

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

        Boolean array. Set true for already used ids, find first non-used in O(ans), then set false for all that we set true before. All is done in O(degree), total complexity O(m).

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

        Stupid is most effective. Just dump heibours component numbers in array and sort it. Its O((M+N) log N)

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

        I found the bug, the problem was something else, set should work fine, but thanks anyway

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

Can we see the codes of the participants?

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

So, since I've never seen it publicly stated, I think it's worth moving this discussion to the public at this point.

Java in Yandex.Contest got broken a few months ago — execution time slowed down in the 10x range, simple linear solutions with n=200000 now get TLE. Today's problem F is a good example — I got a TLE with the straightforward linear solution, I'm pretty sure that if you upload my solution to Polygon it will run in less than a second.

We have reported it through various channels, but it seems that this problem is very hard to solve for Yandex.

Given that the testing system is broken and fix is hard/impossible, would you please consider moving the remaining rounds to Codeforces or ejudge? It is really frustrating to get TLEs for linear-time solutions, and it's even more frustrating with the contest format where failures are super costly. Moreover, this impacts all problems, not just those where one actually gets TLE — having got such TLE in today's problem F with such simple code, how can I be sure in almost any other problem that I won't get a TLE?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it -30 Vote: I do not like it

    Did you use Java7 x32? It worked for my F solution.

    And yes, I remember we both had problems with Java in last opencup ;)

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

      There was a jury message about this during the round

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

      It does indeed pass with Java 7 x32. Before the contest I asked the organizers which version of Java to use, and they told to use Java 7 x64 or x32 (also duplicated in the announcement), so I assumed that x32 and x64 have similar performance.

      But I think it is somewhat besides the point. Even if it's possible to squeeze in a solution to this particular problem, some problems do not pass with x32, too (we had quite a few in the recent open cups), and what's more important, it is hugely disadvantageous in this contest format because you always fear getting TLE everywhere.

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

    Well, it is a bit offtopic but...

    How to solve F in O(n) time? Both AtCoder editorial and my solution (slightly different) work in time.

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

      I was assuming various bitmask operations are O(1), which I guess is not strictly correct:

              int solve(Vertex parent) {
                int mask = 0;
                int doubleMask = 0;
                for (Vertex v : adj) {
                    if (v != parent) {
                        int child = v.solve(this);
                        doubleMask |= (mask & child);
                        mask |= child;
                    }
                }
                if (doubleMask > 0) {
                    mask |= (Integer.highestOneBit(doubleMask) << 1) - 1;
                }
                int cur = Integer.lowestOneBit(~mask);
                mask |= cur;
                mask &= ~(cur - 1);
                return mask;
        }
      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +66 Vote: I do not like it

        BTW, if i am not missing something then the last 4 lines could be ++mask

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it 
        int cur = Integer.lowestOneBit(~mask);
mask |= cur;
mask &= ~(cur - 1);

        This part is equivalent to 

        ++mask;
        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I wrote the same O(N * loglogN)

        Btw, this decomposition looks good. May be there will be more problems based on it, who knows ;)

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

    Object creation is expensive in Java 7 x64 / Java 8 x64. The only reliable version is Java 7 x32 (why not add Java 8 x32? I wanna use streams and lambdas sometimes)

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

      Please see comments above — we had plenty of cases where Java 7 x32 was getting unexpected TLEs in Open Cup, too. And I believe snarknews has rejudged our solutions from older Open Cup rounds and they got several times slower, so something is definitely broken with the system.

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

      Our firs encounter with this issue was on an OpenCup problem where a linear solution with arrays of ints (so almost no objects involved) with n = 200000 was getting TL. So it's not object creation, but rather broken Java.

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

    FWIW, exactly this issue was discussed during the recent marathon round one week ago. My measurements back then showed that even Java 7 32 on server is several times slower than Java 8 locally.

    I don't understand why is it so hard just to roll back to the state several months ago, when everything was working fine... Also, so far I've never seen any Yandex representative even acknowledging that the issue exists, which is mildly frustrating (given that many different Java-users are complaining about it after every single contest).

    For the sake of transparency, it would be much nicer if someone from Yandex publishes smth like "we changed <this and this> several months ago, which broke Java, sorry about that, we're going to do <this and this> to fix it".

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

    Hi. Thanks for taking part in Round 1 and sorry for the trouble caused, there is indeed a significant slowing down in java execution on large input data cases.

    We prepared the problems in such way that they would be less affected by the java issue, made sure to add problem X for server side testing and notified all contestants about java 7 recommendation at the contest start.

    Nevertheless I understand that wasting time on problem X testing and not being sure in your language of choice is annoying.

    We put our best effort to this problem right after the opencup round, where the problem was reported, and will do so in two upcoming weeks before the next algorithm round.

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

      Thanks a lot for looking into this problem, and for telling more about the measures being taken. I'm really sorry for assuming that nothing was being done — now I understand that it was completely not true.

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

      Thanks for acknowledging that the problem exists, and working on fixing it!

      FWIW, the issue doesn't seem to be related to I/O (or at least, not just to I/O). It seems that Java heap is very slow for some reason (and I/O is just a side effect, because it allocates String objects). I've performed the following measurements, for Java 8 locally, and Java 7 32bit on Yandex.Contest server (and C++ locally/on server for comparison):

      C++, locally Java 8, locally C++, server Java 7 32, server
      Simple Floyd, ints 0.842s 2.288s 1.028s 1.137s
      Simple Floyd, objects 3.073s 16.902s 4.066s 14.9s
      Allocating 10M objects 0.490s 0.458s 0.648s 6.033s
      Allocating 1M objects 0.066s 0.148s 0.069s 468ms

      One can see that Java on Yandex.Contest outperforms my local Java on simple int operations, and performs roughly the same for de-referencing pointers. However, it drastically changes if I compare time of object allocation: allocating 10M objects is 13 times slower than locally (and it's not a system issue: for C++, it works just fine).

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

Ignore.

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

    I've added assertion to my AC code that times are greater than 0 and it still passes. Probably you have some other problem

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

      You're right. It's 4AM and I'm not thinking clearly. Thanks for the help!

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

I logged in using my Facebook account and the scoreboard shows that I'm from the US which is not true. Is it possible to somehow change the country flag?

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

does marathon round scored for giving t-shirt or you just send t-shirt for top 500 of round1,2,3 ?!

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

    T-shirt winners and finalists will be determined based on 4 rounds (Marathon and Round 1, 2, 3).

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

      Is this ranking accurate?
      What happens if someone skips a contest?

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

        AFAIK, the ranking is done as follows..
        A participant can participate in any number of rounds (out of the four). If after the end of all the four elimination rounds, a participant has some NGP30 score (summation of all the four rounds), he gets ranked on the basis of that. (the larger the better)
        Now, for all the participants, who have NGP30 score sum == 0, they are ranked on the basis of the minimum rank they have got in all the four rounds, (the smaller the better), below the participants whi have NGP30 score sum > 0.
        If you don't participate in a round, it's equivalent to, NGP30 score 0 and rank infinity.

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

          Yep, I understood that as well, but given the grand prix point system at most 120 people will have a score, probably much less. So now we rank the rest by minimum position. But then by that criteria a person who has been 50th in 3 rounds but missed one should be ranked lower than one person who participated in all rounds?

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

            Yes,
            If person A participates in only round-1 and gets a rank of 40, while person B participates in all the four rounds and gets ranks 150, 200, 180, 257 respectively, then:

            minimum rank of A = 40
            minimum rank of B = 150
            and hence person A gets a better rank than person B.

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

      General rant against such comparisons

      It's a bit weird to compare people by ranks in contests that have unequal participation. For example rank 200 in marathon(which had ~400 participants) is over rank 201 in Round 1(which had ~800 participants)[assuming both don't participate in other rounds]. Besides, you are comparing someone's skills in approximate challenges with someone's skill in Algorithm tasks, which is weird in itself.

      But it's your decision, so if this is intended result, it's okay.

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

Is there O(1) B solution?

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

    Almost constant I guess (independent of N)

            for(int i = 0; i <= 1000; i++)
	{
		ll x = i + A;
		ll y = N - x;

		if(x < A || y < A || x > N || y > N)
		{
			break;
		}

		x = 5000 - (x % 500);
		y = 5000 - (y % 500);

		ans = max(ans, (x % 500) + (y % 500) );
	}
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it 
      	for(long long i = a; i <= a + 500 && i <= n - a; i++)
		ans = max(ans, (500 - i%500)%500 + (500 - (n - i)%500)%500);

      A shorter version of your code.

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

What is the solution for D? I came up with O(N^4 log N) but didn't write it.

Anyway here is my idea: Divide bets in three categories. Let us focus on W-bets. We compute dp[1...N*M] where

It can be computed in O(N^2*M) (we add bets one by one and update all N*M answers)

We compute similar dp for L-bets, and D-bets. Now we do a bin-search for the answer. For an amount of money C we fix an outcome from W-bets and L-bets and find if there is suitable outcome in D-bets. It will take O(N^4 log N).

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

    Replace ai and bi with xi=bi and yi=ai+bi . You can restate problem in the following way: for each bet you take you receive xi and in case of proper outcome you pay yi. Now notice that for the chosen subset of bets, you receive sum of their xi and may lose maximal of three sums of yi for W,D,L respectively. Iterate over maximal loss X and pick best subsets of bets with loss <=X. Your dp suits it quite perfectly if you replace a and b with x and y.

    → Reply