300iq's blog

By 300iq, 5 years ago, translation, In English

Hi!

At Apr/06/2019 14:35 (Moscow time) we will host Codeforces Global Round 2.

It is the second round of a new series of Codeforces Global Rounds supported by XTX Markets. The rounds are open for everybody, the rating will be updated for everybody.

The prizes for this round:

  • 30 best participants get a t-shirt.
  • 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2019:

  • In each round top-100 participants get points according to the table.
  • The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
  • The best 20 participants over all series get sweatshirts and place certificates.

The problems of this round were developed by a team of authors: 300iq, cyand1317, Aleks5d, RDDCCD, KAN, gen.

Thanks KAN for his help in the round's coordination, and also isaf27, Lewin, ----------, Errichto, arsijo, cdkrot for testing the round!

Удачи!

Congratulations the winners!

1) ecnerwala

2) tourist

3) Um_nik

4) Endagorion

5) Petr

Editorial.

Announcement of Codeforces Global Round 2
  • Vote: I like it
  • +341
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +52 Vote: I do not like it

Friendly time to Chinese!

»
5 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Hope that it won't happen again XD

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +76 Vote: I do not like it

    ofc, will be worse...

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -36 Vote: I do not like it

    Pretests for these rounds are extremely weak, that is why I won't participate in them anymore.

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can you add the link Codeforces Global Round 1

»
5 years ago, # |
  Vote: I like it +110 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

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

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

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

    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.

»
5 years ago, # |
  Vote: I like it +124 Vote: I do not like it

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?

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

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

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

      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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Maybe they are different T-shirts?

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

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

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

»
5 years ago, # |
  Vote: I like it -30 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

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

    So, it is rated for you

»
5 years ago, # |
  Vote: I like it +46 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Удачи! means Good Lucky!!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Удачи

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +81 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Same where the black number of 300iq

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Is this the difference between a blue coder and red coder ? :P

    When I get less upvotes for the same comment I did 17 hours ago :(

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

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

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

vammadur now has positive rating :o

»
5 years ago, # |
  Vote: I like it +233 Vote: I do not like it

A fair and balanced problemset.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What's the pretest 7 in E?

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

    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.

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

      How is answer 15 and not 14?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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)

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

          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?

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

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

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

            I'm sorry. I revised the comment.

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

      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.

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

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

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve problem E ?

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve E?

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

    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.

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

      This dp is two-dimensional?

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

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

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

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

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

          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.

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

            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

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

              I've been thinking on my way home and understood. Thanks a lot for teaching me anyway.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +28 Vote: I do not like it

    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.

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +119 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +74 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +70 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +97 Vote: I do not like it

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

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

Why the length of this contest is only 2h?

»
5 years ago, # |
  Vote: I like it +97 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

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

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

  • »
    »
    5 years ago, # ^ |
    Rev. 7   Vote: I like it +14 Vote: I do not like it

    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.

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

    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.

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

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

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +43 Vote: I do not like it

    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.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Greedy solution for E: https://codeforces.com/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.

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

    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.

»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

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?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +86 Vote: I do not like it

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!

»
5 years ago, # |
  Vote: I like it +60 Vote: I do not like it

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
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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

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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the editoral be published?

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

    Yep, just wait for the system testing to end.

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can the problem C be solved using brute force ?

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

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

    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

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

    I simulated the whole process using many speedup tricks. 52395830

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

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

      i literally simulated the process.

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

        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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?!!

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

    It's not a correct comparator. a > a for any a. It's bad.

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

    Comparator needs to be LESS function, not LESS_OR_EQUAL.

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

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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem B,I am so sad.

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

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

    You should have told yourself "hell yeah!".

    My previous rating change: 0. My rating change from 3 rounds ago: 0.

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

When will you announce tshirt winners?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will you distribute the t-shirts?

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

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
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yay!!!

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +101 Vote: I do not like it

      Wtf! My name got removed. fmllllllllllllll

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

    Wow, the contest couldn't have gone worse than this for me. I was selected in the previous list, but unfortunately, today was not my day! Guess I'll never get a cf t-shirt ;_; ...

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

    KAN My rank is also 288,how is the tie broken?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Rank, last submission time, handle. You can check the code for details.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Yay!

    But how to get the T-shirt? Shall I write an address? (My English is not good please don't laugh at me)

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

    I should have understand A earlier... (I got 235th place.. 2 points off from 234th)

»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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