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

Автор GlebsHP, история, 6 месяцев назад, По-русски,

Всем привет!

Завтра, в 10:00 мск состоится Раунд 1 соревнования Яндекс.Алгоритм, автором задач которого являюсь я. Хочу сказать спасибо Zlobober за помощь в подготовке раунда и за всю ту работу, которую он делает чтобы данное соревнование было интересным и качественным, а также MikeMirzayanov за замечательную платформу polygon, значительно облегчающую процесс разработки задач, а также всем, кто прорешивал раунд и давал ценные комментарии. Разумеется, мы приложили максимум усилий, чтобы сделать задачи разнообразными как по сложности, так и по тематике.

До встречи на соревновании!

UPD Спасибо всем, кто принял участие, надеюсь каждый нашёл для себя хотя бы одну интересную задачу. Мы приносим свои извинения за ситуацию с задачей F, мы честно искали все задачи в интернете и спрашивали у тестеров, не видели ли они аналогичных задач, но это не помогло. Опубликован разбор задач (пока только на английском).

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

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

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

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

    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.

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

Если ты не писал марафонский раунд. Предполагается, что ты занял в нем последнее место?

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

    В некотором смысле ДА. Но это не мешает бороться за финал (сумма ГП баллов) и футболки (лучшее место из 4 отборочных раундов).

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

      Я правильно понимаю, что в этом году не обязательно писать все раунды, чтобы получить футболку. Если хоть в одном из них ты занял место меньше чем 128?

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

        Да, более того, нужно будет не 128 место, а какое-то ниже (в зависимости от того, как часто одни и те же люди будут в топе)

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

Авторские решения на всех версиях java заходят? Или их вообще нет?

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

    Пожалуйста, задавайте вопросы через тестирующую систему.

    Авторские решения на java есть по всем задачам, где это существенно.

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

      Джава джаве рознь.

      А в тестирующей системе мне б no comments ответили на такой вопрос.

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

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

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

    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?

»
6 месяцев назад, # |
  Проголосовать: нравится +97 Проголосовать: не нравится
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +61 Проголосовать: не нравится

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

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

    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.

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

      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.

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

        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.

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

    Okay, and how to solve it? :)

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

How to solve C?

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

    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.

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

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

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

        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.

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

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

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

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

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

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

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

Как D?

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

    Будем считать, что деньги мы получаем всегда, а за проигрыш платим ai + bi. Зафиксируем, сколько мы заплатим при проигрыше (X). Тогда мы хотим в каждом из исходов просто набрать максимальную сумму, если мы платим не больше X. Напишем 3 независимых рюкзака, затем переберем X.

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

    Скажем, что взять ставку стоит a, и нам дают a+b, если она сыграла. Для каждого типа ставки насчитаем рюкзаки "максимальная сумма, которую можно получить, потратив не больше а". Теперь нам надо в каждом рюкзаке выбрать 1 вариант, мы заплатим за все три и получим профит от двух худших.

    Посортим все возможные варианты из рюкзаков и переберем тот, который будет вторым худшим в нашем выборе. Теперь осталось среди вариантов хуже взять тот, у которого оптимальный баланс (за него мы получим + баланс),а среди вариантов лучше — тот, у которого минимальная цена (он не сыграет, и за него заплатим зря). Это насчитывается максимумами на префиксах/суффиксах. Ну и еще не забыть, что надо взять ровно один вариант из каждого рюкзака — можно перебрать, из какого рюкзака брать вариант хуже, а из какого — лучше.

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

    Ну так

»
6 месяцев назад, # |
  Проголосовать: нравится -61 Проголосовать: не нравится

бомбит конечно, нельзя ли так составлять задачи, чтобы их можно было с одного раза решить?

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

    По Java по-моему нормально лимит выставлен был, TL не приходилось пробивать.

    A,B,C,F под твой критерий подходят. D,E не сдал, не знаю :)

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

Can we see the codes of the participants?

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

So for F I attempted to just do the centroid decomposition, and then return the height of that decomposition as the answer. This gives WA, but I am unable to construct a counterexample. Does somebody have one?

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

    Second pretest is a counterexample. In first CD chooses 4, but you need to choose 3.

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

      Sorry, I'm confusing centroid and graph center. What I did was pick some vertex u in the current subtree that minimized max(d_uv | v in subtree) and removed that.

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

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?

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится -30 Проголосовать: не нравится

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

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

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

      There was a jury message about this during the round

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

      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.

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

    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.

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

      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;
              }
      
      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится +66 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится
        int cur = Integer.lowestOneBit(~mask);
        mask |= cur;
        mask &= ~(cur - 1);
        

        This part is equivalent to

        ++mask;
        
      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I wrote the same O(N * loglogN)

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

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

    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)

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

      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.

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

      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.

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

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

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

    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.

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

      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.

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

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

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

Ignore.

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

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

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

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

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

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?

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

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

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

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

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

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

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

        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.

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

          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?

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

            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.

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

      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.

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

Is there O(1) B solution?

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

    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) );
    	}
    
    • »
      »
      »
      6 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
      	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.

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

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

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

    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.

»
6 месяцев назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Thank you for nice posting. I do like your all information. Thanks to email database provider company.