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

Автор 300iq, 6 лет назад, По-русски

Добрый день!

6 апреля, в 14:35 UTC+3 состоится Codeforces Global Round 2.

Это второй раунд из серии Codeforces Global Rounds, которая проводится при поддержке XTX Markets. В раундах могут участвовать все, рейтинг тоже будет пересчитан для всех.

Призы в этом раунде:

  • 30 лучших участников получат футболки.
  • 20 футболок будут разыграны случайным образом среди участников с 31-го по 500-е место.

Призы в серии из 6 раундов в 2019 году:

  • За каждый раунд лучшим 100 участникам начисляются баллы согласно таблице.
  • Итоговый результат участника равны сумме баллов для четырех лучших выступлений этого участника.
  • Лучшие 20 участников по итоговым результатам получают толстовки и сертификаты с указанием места.

Задачи для этого раунда были разработаны целым коллективом авторов: 300iq, cyand1317, Aleks5d, RDDCCD, KAN, gen.

Спасибо KAN за помощь в координации раунда, а также isaf27, Lewin, ----------, Errichto, arsijo, cdkrot за тестирование!

Удачи!

Поздравляем победителей!

1) ecnerwala

2) tourist

3) Um_nik

4) Endagorion

5) Petr

Разбор задач.

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

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

Friendly time to Chinese!

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

Как так-то, а?

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

уже топ 8 по вкладу

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

Лол, Ильдар опять без нутеллы останется...

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

Hope that it won't happen again XD

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

hope high rating!

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

it feels like we have been waiting for ages for this round

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

can you add the link Codeforces Global Round 1

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

How many of you feel that Codeforces is decreasing the frequency of contests?

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

    Maybe because the best problem developers are busy with ICPC WF. XD Hope the Contests will be more soon.

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

    I actually think these days the quality of the problems is increasing. So it's reasonable that there are less contests. (Well, didn't mean that other problems are poor in quality)

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

    You can always participate virtually on some previous contest or on a one from the Gym.

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

    If you compare with the situation 2 months ago, well — this is true. But what about the frequency that was 2 years ago? Currently, codeforces is the most active and popular platform for competitive programming (IMHO). I think that we should be grateful for this to Mike, KAN, and other contest makers and problem setters, for the opportunity to write contests at least once a week.

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

Wait, what happens if someone gets in top 30 in all 6 rounds? That person gets 6 t-shirts? Wouldn't it be better to stop at some point (e.g. 2 or 3 t-shirts) and distribute the rest in some other way?

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

    Mb, "The prizes for this round:" means, that not all rounds will be with the same prizes?

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

      That would be even more unfair and no, I'm pretty sure that's not the case. Check the initial announcement of the Global Rounds.

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

    Maybe they are different T-shirts?

    I'm sure it's ok if such person gets all 6 different ones haha

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

    The more the better, I can give it to my mom, my girlfriend , my dad, etc...to advertise my cleverness.XD

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

wow!

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

so, it is not rated for normal contestants? Why !

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

А почему первая буква красная?

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

How many problems will be there and what's the score distribution?

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

i hope after this round my rating will be purple rather than stil blue.i still remember that in global contest 1,the difficulty between problems was not very proper.so i hope this round will be(and can be)better

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

Удачи! means Good Lucky!!

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

Удачи! means Good Lucky!!

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

Удачи

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

Expecting this round to be full of awesome questions with strong pretests ;)

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

Where is the number of problems and score distribution? :)

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

Удачи! -->> Good Luck !!!

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

I hope that my rating can be improved in this contest! Hope that all of us can have a good result!

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

vammadur now has positive rating :o

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

A fair and balanced problemset.

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

Imo, one of the most interesting contest I've ever participated.

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

What's the pretest 7 in E?

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

    My guess is something like that: 5 — 11 7 5 13 9. Answer is 15 but my answer is 14. Only noticed it at last minute.

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

      How is answer 15 and not 14?

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

        It is possible. One example is that:

        1 1 1 (1) 1 2 2 (2) 1 3 3 (3) 1 4 4 (4) 1 4 4 (5) 1 4 4 (6) 1 4 4 (7) 1 4 4 (8) 1 5 5 (9) 2 2 2 (10) 2 3 3 (11) 2 4 4 (12) 3 5 5 (13) 4 5 5 (14) 5 5 5 (15)

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

          But.. how can you make triangle from 2 sticks of length 2^x and one with length 2^(x+1)? Sum of every 2 sides needs to be greater than 3rd side. What am I missing?

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

            You're right. One correct solution is

            3*(1,1,1), 2*(1,2,2), 1*(2,2,2), 1*(3,3,3), 2*(3,4,4), 3*(4,4,4), 3*(5,5,5).

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

            I'm sorry. I revised the comment.

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

      But I got TLE on the pretest 7 once, and after removing time-consuming loop, I passed that pretest(though I couldn't pass the pretest 11). So the possibility, that the pretest 7 is that in which n is large, also exists.

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

    maybe you should use "I64d" in C++ for the answer

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

How to solve problem E ?

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

How to solve E?

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

    Observe that there are only two possible type of triangles, ($$$2^{x}, 2^{x}, 2^{x}$$$) or ($$$2^{x}, 2^{y}, 2^{y}$$$) where $$$x<y$$$. Now, you can do dp storing the number of triangles and number of sticks unused till i.

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

      This dp is two-dimensional?

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

      I still don't understand the DP; Can't the number of unused sticks be up to $$$10^9 \cdot n$$$ ?

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

        When it gets to "3", you make a new triangle. So it's only 0/1/2

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

          Well, I'm not sure I've understood your solution; but how about the case something like {10, 2, 2, 2, 2} ? In my opinion you have to store the state where there are 10 unused sticks when looking at the second element of the array.

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

            No. Let dp[i] store number of maximum triangles you can make till i and f[i] store number of unused sticks till i. Then, recurrence relation is first pair sticks of length $$$2^{i}$$$ with f[i-1] as much as you can and then make triangles using remaining sticks of $$$2^{i}$$$ length.
            So, when we look at second element, there is only 1 unused stick and 3 triangles made

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

    The triangle either has to have three sides of of the same length, or two of the same length and one shorter. Iterate through the lengths from smallest to largest. Keep the number of leftover sticks. In every step, make as many triangles from two sticks of the length you are at, plus one leftover stick. Then, make as many triangles from 3 of the current length. If any sticks of the current length remain, add them to leftovers.

    This works because the sticks of the current length are "rarer" than the leftover ones, because they turn into leftovers at the end of the step. Thus, you want to use the "rarer" type less and the "less rare" type more.

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

oh god if there are people talking it's so hard to think my mind exploded thinking in A only ... I will never participate without having quite place again

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

Did anyone solve E by dp, i dont know why I got WA 52411976

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

Div.2 A~C & Div.1 E/F

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

What a big difficulty gap! (Well, not being able to solve E, I have no right to complain about it though:(

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

как решать E??

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

wow a speed contest.

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

Very unbalanced contest. D and E are too easy, F and G are too difficult :/

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

Were problems F, G, H given to solve just for fun?

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

Why the length of this contest is only 2h?

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

Almost all div.1 coders have same set of AC. I think this is bad choice (The problems are good, although).

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

How to solve C?

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

    Hint : Number of non-matching squares in every column must be even, and you can reverse a[i][j] and a[i][1] together.

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

    For the answer to be "Yes", a necessary condition is that the XOR of each row must be the same in A and B, because the operation cannot change it; the sum in each row can only decrease by 2, stay the same or increase by 2, thus the XOR stays the same. Similarly for columns.

    And it turns out that this is sufficient as well. Think of the 1D case, where you have 1 row and you must always flip two elements. Iterate i from 1 to N and always change a[i] to b[i], flipping also a[n]. Then, when you reach i=n, a[i]=b[i] by the XOR invariant. For the 2D case, you can fix rows in this way and then solve for a smaller matrix. Once you reach a state where you have only 2 rows, observe that fixing one row must fix the other, also by the XOR invariant.

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

    You iterator through all position if that position in A different with B you can find any rectangle with top-right and bottom-left is needed to change. Repeat until you cant find such rectangle or all position has been processed.

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

    Check the xorsum of every row/column. You can transform into any matrix with the same xors.

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

    Here's a different way to do it that is also really simple to implement:

    Notice that all operations can be done as multiple operations of 2x2 submatrices. Then, notice that this operator is commutative and associative (since xor is commutative and associative) and you would never do the same operation twice.

    Thus, iterate from i=1..n-1 and j=1..m-1 and if a[i][j] is different from b[i][j], then apply the operation to the submatrix of (i,j) and (i+1, j+1). It suffices to check at the end whether the last column and row of a and b are the same.

    If you know some group theory, then in general, there is a type of question that appears that can be boiled down to "Here's a group action and a set. Given two objects, are they in the same orbit?" Often times these problems can be solved by finding a small list of generators and simply brute force testing whether it's possible. Other times it is solved with invariants, as other people noted.

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

Problem C is a good problem out of the easy problem.

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

Greedy solution for E: https://codeforces.me/contest/1119/submission/52403202

Go from right to left and greedily make as many triangles of this type as you can. A triangle of type i is made of (i,i,j), where j <= i. There's a O(1) formula instead of my binary search, I'm 99% sure.

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

    Yes, you can just keep track of the max number of triangles created at each step. Then, calculate the number of unused legs. It's optimal to use as many of these as possible, and the most you will be able to use is min(a[i]/2, unused). Then use as many triangles from the leftover a[i] as possible.

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

I think the length of this contest should be 02:30. :)

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

I don't think that F is conceptually that hard, but it's a lot of work.

Excerpt from my code: calculate degrees of vertices, and then sort the adjacency list by the degree, so that I can do edge removals in $$$O(1)$$$:

for (int i = 0; i < N; ++i) {
    D[i] = E[i].size();
    sort(E[i].begin(),E[i].end(), [&](pii&a, pii&b) { return D[a.x] > D[b.x]; });
}

Such a thing is hard to find if you get WA on pretests two minutes before the end. Where can I apply for mental disability pension?

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

I think the length of this contest should be 02:30. :)

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

A-E are solved by 1000+ users while FGH are solved no more than 8 users each.

Amazing gap! So I think it's not a balanced problemset at all.

A-E is too easy for candidate masters and masters. But even most grandmasters can't solve one of FGH. When I noticed that it took tourist 1h to solve F, I understood that I have no chance to solve it during contest.

Congratulations to those who solved 6 problems, real legand!

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

Another case of the classic "Let's make a div1 round by appending some insanely hard problems to a div3 one" :(

Does the following work for F?

solution? to F
»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Absolutely beautiful test cases! Especially for problem C. That's how you do it.

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

The problem difficulty gap should be taken care of, else it is speed which differentiates everyone which is really unfair on some masters and above who know much more.

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

Will the editoral be published?

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

vammadur makes the new record for highest rating change. Congrats!!

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

I want a T-shirt so bad, I would kill for one , the probability of me getting is 1/470 :)

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

I want a T-shirt so bad, I would kill for one , the probability of me getting it is 1/470 :)

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

Can the problem C be solved using brute force ?

i'm getting TLE, just curios if anyone managed to solve it in such way !

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

    I don't think that it's possible with your bruteforce. Imagine 500*500 matrix with all zeros and you need to transsform it into all ones. It would need 500*125 inversions and it's quite long

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

    I simulated the whole process using many speedup tricks. 52395830

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

      No, you used the XOR invariant solution ( which still don't understand )

      i literally simulated the process.

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

        What my code does is the same with your code, just without "Counter" variable and one observation that if there is just single 1 in any row or column, then it's No.

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

I think A was really hard for A I think C was popular problem and i have seen it before

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

I submitted this solution 52405088 for problem D during the contest but I got RTE in the system test, then I only modified something after the contest and got AC 52416473

My question is, why did the first one got RTE and why actually this modification made any difference?!!

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

Who on earth could solve the first 5 problems within 12 minutes in the contest... tourist, are you a human? I wanna know how "TOO obvious" for you on these problems.

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

How to solve problem B,I am so sad.

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

Contest rank : 666 New rating : 1900 Ok, I'm cool.

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

When will you announce tshirt winners?

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

When will you distribute the t-shirts?

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

UPD: I accidentally computed 80 winners instead of 50 in the first edition, now the list is fixed.

T-shirt winners!

As always, we used the following two files and the seed equal to the score of the winner (this time it is 9848).

randgen.cpp
get_ranklist.py

And the t-shirt winners are:

List place Contest Rank Name
1 1119 1 ecnerwala
2 1119 2 tourist
3 1119 3 Um_nik
4 1119 4 Endagorion
5 1119 5 Petr
6 1119 6 mnbvmar
7 1119 7 sunset
8 1119 8 Rewinding
9 1119 9 yokozuna57
10 1119 10 realDonaldTrunp
11 1119 11 krijgertje
12 1119 12 yhx-12243
13 1119 13 lumibons
14 1119 14 leaf1415
15 1119 15 Arterm
16 1119 16 peltorator
17 1119 17 jonathanirvings
18 1119 18 lych_cys
19 1119 19 fateice
20 1119 20 vammadur
21 1119 21 ksun48
22 1119 21 MofK
23 1119 23 webmaster
24 1119 24 Kostroma
25 1119 25 hos.lyric
26 1119 26 neal
27 1119 27 Alex_2oo8
28 1119 28 TLEwpdus
29 1119 29 I_love_Tanya_Romanova
30 1119 30 E869120
37 1119 36 edisonhello
40 1119 40 Rzepa
47 1119 47 Itst
153 1119 152 Jatana
184 1119 184 beet
208 1119 208 lzyrapx
210 1119 210 sas4eka
234 1119 234 Atreus
257 1119 254 cuiaoxiang
266 1119 265 altunyanv
268 1119 268 Trisolaris
284 1119 284 t90tank
288 1119 288 Kloze
335 1119 335 trabbbart
392 1119 392 zaki_joho
398 1119 397 StevenZhu
431 1119 429 DQS
434 1119 434 Filyan
446 1119 445 knshnb
463 1119 462 Jungarr1k
»
6 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Got a notification that KAN mentioned me, and then I see the update. This is so sad.

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

300iq tasks difficulties have not been assigned yet. Could you please fix that?

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

Anyone with FFT idea in problem E? it is in the FFT category .. although i have the greedy solution