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

Автор AliShahali1382, история, 2 года назад, По-английски

Hello, Codeforces!

On Nov/23/2021 17:35 (Moscow time) we will host Codeforces Global Round 17.

It is the fifth round of a 2021 series of Codeforces Global Rounds. The rounds are open and rated 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 2021:

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

Thanks to XTX, which in 2021 supported the global rounds initiative!

The problems were written and prepared by AliShahali1382(Ali Shahali), AmShZ(AmirMohammad ShahRezaei), DeadlyCritic(MohammadHossein Paydar), Keshi(Alireza Keshavarz), alireza_kaviani(Alireza Kaviani).

We would like to thank these people:

You will have 3 hours to solve 9 problems. As usual, it is highly recommended to read all problems!

The score distribution will be announced at least 5 minutes before the round starts! :)

Score distribution : 500 — 1000 — 1500 — 2250 — 2500 — 2750 — 3250 — 3500 — 4000.

Editorial is out

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

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

Please give me contribution, I slept two hours later last 3 nights because I was trying to come up with a problem which makes the round better.

[edit] Sorry, it wasn't intentional :(

[edit] make it 6 nights...

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

As a tester, good luck on contest and upsolve all problems because they are awesome!

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

As a tester, I can confirm that the problems are pretty nice! I would recommend participating in this round and enjoying the problems.

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

You will have 3 hours to solve 9 problems.

The table at the contests tab currently shows 2 hours duration for Codeforces Global Round 17. Is it actually 2 or 3 hours?

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

What does sifid like this time :D ?

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

Orz

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

Hope AliShahali1382 will not make shitty problems like 1440C2 - Binary Table (Hard Version) this time.

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

GL, HF

»
2 года назад, # |
  Проголосовать: нравится +160 Проголосовать: не нравится
As a tester
»
2 года назад, # |
Rev. 2   Проголосовать: нравится +57 Проголосовать: не нравится

Iranian contests always had interesting problems,I am sure this one will be as good as others

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

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

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

As a tester, I wish everyone good luck!

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

R.I.P Tet

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

I'm so excited for this round :")

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

I am excited for another Iranian round :)

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

Hooray :D

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

Please give the scoring distribution as early as you can as there are 9 problems

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

Expect Great Round :"

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

heeeyyp... have good contest...

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

Hidden...

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

every global contest makes me upset, I hope this round will be diffrent .Good luck to every one QwQ

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

"The score distribution will be announced at least 5 minutes before the round starts! :)" really very useful information :) thanks

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

I definitely don't find any reason for not giving the scoring distribution an hour earlier before the contest

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

At least 30 minutes before: Where is the score distribution?

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

At least 5 mins -> 6 mins :)

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

I prolly will go back to being a specialist, but it would be fun anyway!

Good luck everyone!

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

Is this div.1?

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

Sad :')

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

I think setters and testers are giving down votes to everyones comment

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

Did B,C in first try still couldn't do A ;-;

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

tfw your only WAs on a problem were on A

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

Is this Rated?

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

    Noob question: I've searched for these and couldn't find answers: Within the post above, it says "The rounds are open and rated for everybody". However, within the title, it doesn't say it is rated. On my graph, this competition comes under unrated. I'm quite confused. Is there a way to tell which competitions are rated or not, that I'm not aware of?

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

B,C,D are decent problems but A is not appropriate for its position.

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

.

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

I don't know what to say about this round. I just appreciate that I don't feel bad although I performed poorly.

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

How to solve C ?

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

    My solution is based on binary search on the answer. The boundaries for BS are l = 1 (you can always call 1 friend), and r = n. Now we are interested in whether can we call m = (l+r)/2 friends to the party? Let's iterative from first to the last friend and keep count of the number of the friends we have already invited (this will be cnt).

    First of all — all friends to the left of the i-th friend are poorer, and all friends to the right are richer. If i-th friend satisfies these requirements we will call him, and update cnt = cnt+1:

    1) a[i] >= m-cnt-1 //number of friends who will be richer than i-th is m-cnt-1 (since we are trying to call m friends with cnt already called + himself, that leaves us with m-cnt-1 friends to the right)

    2) b[i] >= cnt //number of friend who will be poorer than i-th is cnt, since we called already cnt of them and all of them are to the left of the array

    If in the end cnt >= m, then it is possible to call m friends, otherwise it is not. According to this we continue with our binary search.

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

      how are finding the subset of m friends from the whole array? as each time a person is picked(say i), we have to check whether some person which was picked previously(say j < i)it's a[j] is not less than i-j i.e no of person's after it?

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

For anyone looking for video explanations (for A,B and C only)

You can visit here

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

Idk how D has so much solves compared to E. For me it felt D >> C > E.

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

    Shitttt!! Got the blunder upon seeing others' code T-T

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

      All you said is true apart of -> each difference has to be bigger than sum of all previous differences. So the number of elements chosen is O(log) + (the number of elements equal to the first one chosen, so there can be a lot of them, but we "jump over" them at once).

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

    I feel like its really easy to go down the wrong route on D after making observations on the first sample for $$$\equiv 0 (\text{mod } 4)$$$ and $$$\equiv 2 (\text{mod } 4)$$$ part, but if you realize (or guess) it generally applies to $$$\equiv 0 (\text{mod } 2^x)$$$ and $$$\equiv 2^{x - 1} (\text{mod } 2^x)$$$ then its fairly easy to arrive at the solution.

    Unfortunately took me wasting 1 hour hard coding a special case for pairs of $$$\equiv 0 (\text{mod } 4)$$$ and still overcount sample 2 to think about it properly and realize it.

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

    It took me 1 hour to solve D and only 15 min to solve E. I thought there was a better solution but it turned out people did the same. Am I incredibly dumb or how did a lot of people come up with a not-so-trivial idea that fast?

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

I did not like Problem D, as in my opinion it did not serve its purpose well, e.g. it wasn't a good problem to "balance" the round, and in my opinion Problem E was much easier than D.

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

Problem C has taken atleast a decade off my lifespan I think. How to do it?

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

How do you do D?

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

    Count of all non-empty subsequences where there is at least one odd number, or the count of even numbers with the least LSB is even.

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

      How did you come up with that least LSB thing? I wasn't able to solve this part.

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

      This isn't a solution unless you explain why exactly these subsequences are good.

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

        When an odd number exists we can think of the numbers as a single odd number and have their sequences combined as a one sequence symmetrical around $$$0$$$, where the sum will be $$$0$$$. Every other odd number can have its sequence symmetrical around $$$0$$$ on its own with $$$0$$$ sum as well.

        When no odd numbers exist, the sequence sum corresponding to an even number $$$v$$$ is $$$\frac{v}{2}+c*v$$$ where $$$c$$$ is an arbitrary integer. We can re-write this as $$$v*c'$$$ where $$$c'$$$ is an odd number.

        We want to partition such sums into $$$2$$$ partitions with equal sums (one of them is negative):

        • If even numbers with the least LSB have odd count, we are sure one of the partitions will have that bit set and the other will not.
        • If the count is even, we can put odd count of such numbers in both partitions (to guarantee that bit will be set at the end), the remaining count is even (its sum will have that bit unset). So that remaining count with other even numbers can be put in any partition, and we can always choose the constants $$$c'$$$ to satisfy the equality.
        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится

          When no odd numbers exist, the sequence sum corresponding to an even number $$$v$$$ is $$$\frac{v}{2} + c * v$$$ where $$$c$$$ is an arbitrary integer. We can re-write this as $$$v∗c'$$$ where $$$c'$$$ is an odd number.

          Could you give more details or example about this?

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

            Suppose the starting sequence of any even number $$$v$$$ is $$$-(\frac{v}{2}-1)$$$, $$$-(\frac{v}{2}-2)$$$, $$$...$$$, $$$\frac{v}{2}-2$$$, $$$\frac{v}{2}-1$$$, $$$\frac{v}{2}$$$. The sum of this sequence is $$$\frac{v}{2}$$$. Whenever you shift this sequence $$$c$$$ units the sum changes by $$$c*v$$$. So we can generalize the sum formula as $$$\frac{v}{2}+c*v$$$.

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

        Probably overkill, but this is how I came up with it.

        For any $$$a_i$$$, the segment sum it can create is of the form $$$a_ix_i + \frac{a_i(a_i+1)}{2}$$$. For any subset $$$S$$$, we can say that:

        $$$ \sum_{i \in S} a_ix_i = \sum_{i \in S} \frac{a_i(a_i+1)}{2} $$$
        $$$ 2\sum_{i \in S} a_ix_i = \sum_{i \in S} a_i^2 + a_i $$$

        By Bezout's lemma, $$$g = 2 \cdot gcd(a_i), i \in S$$$ must divide $$$\sum_i a_i^2 + a_i$$$ for a solution to exist. Let every $$$a_i = 2^{p_i} o_i$$$, where $$$o_i$$$ is odd. Then $$$g = 2^{min(p_i)+1}$$$ times some odd number. This odd part will surely divide the sum, so I'll just ignore it from now on. Now we have two cases:

        1. $$$min(p_i) = 0$$$, i.e. it contains some odd number. Then, $$$g = 2$$$. This divides every even $$$a_i$$$, and for every odd $$$a_i$$$, $$$a_i^2 + a_i \equiv 0 \mod 2$$$. Hence, any number of odd numbers is ok and some solution still exists.
        2. $$$min(p_i) = y, y \neq 0$$$, i.e. it does not contain some odd number. Then, $$$g = 2^{y+1}$$$. For every $$$a_i$$$, $$$a_i^2 \equiv 0 \mod 2^{y+1}$$$, and if $$$p_i \geq y+1$$$, $$$a_i \equiv 0 \mod 2^{y+1}$$$. Hence, we only need to consider $$$\sum a_i$$$ for $$$i$$$ such that $$$p_i = y$$$. Then,
        $$$ \sum_i a_i = \sum_i 2^y o_i = 2^y \sum_i o_i $$$
        $$$ 2^y \sum_i o_i \mod 2^{y+1} = \sum_i o_i \mod 2 $$$

        This value is 0 if and only if we have an even number of $$$a_i$$$ such that $$$p_i = y$$$.

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

    Basically the idea in D is consider a number b then sum of all possible subsequences of b consecutive integers would be of the form b/2+rb when b is even, where r varies from -infinity to +infinity and when b is odd then it would be 0+rb here also r varies from -infinity to +infinity so the final conclusion comes that those subsets would be good where the m=(summation of even nos.)/2 is divisible the GCD of the whole subset. Here we should not bother about the odd factor of GCD as the m would always be divisible by the odd factor of GCD. Main concern is the power of 2 .Now by slight observation you could on just need to not count those subsets ,consider the even factor of GCD to be 2^i where i>=1 then the no of occurrences of no divisible by 2^i but not divisible by 2^(i+1) has occurred odd no. of times .Now let the total count of these subsets be m then the final answer would be 2^n-1-m

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

Contest so hard, but anyone can give me hint for solving problem C.

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

Not to say that the contest was bad, but problem F was quite known and problem I was very well-known. We gave some modification of problem F (with very similar solution, though) in a math summer school in 2018, where we took it from some Kolmogorov tournament, where it was from some obscure competition called "usa imo selection 2011" or smth, and problem I is just hackenbush, I looked it up in the Conway's ONAG.

GH seemed interesting, though

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

what actually you want from problem solver for problem A??

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

    Hint 1: 0 <= ans <= 2

    Hint 2: m == 1 && n == 1 => 0

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

      I think he wants to understand the statement, not the solution. What you wrote is also kinda pointless because it's not obvious why these implications hold.

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

    You have an $$$m\times n$$$ grid; you know one cell in this grid is chosen, for example $$$(x, y)$$$; you can choose $$$k$$$ cells from this grid. For each of these cells you choose, say $$$(x_i, y_i)$$$, you will be given the Manhattan distance from $$$(x_i, y_i)$$$ to $$$(x, y)$$$; then you are asked to determine $$$(x, y)$$$; now, the question is asking for the minimum number of cells you need to choose, which is $$$\text{min}(k)$$$, so that you can always find $$$(x, y)$$$ regardless of where it is in the grid.

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

Got MLE on F...

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

Imagine coming 2nd and still have negative delta. Couldn't be me.

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

I found B quite similar to this

Grandma Capa Knits a Scarf

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

I feel like I have seen Problem B in one of the previous cf rounds

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

      I used same solution today, but got time limit exceeded.

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

        That's because it's not the same problem. In round 750, the alphabet size is 26. You have enough time to brute force over all possible removals. A solution O(A*N) where A = alphabet size is fine.

        In this round, A <= 200000. A solution O(A*N) is far too slow. Therefore an observation is required: how can we narrow down the pool of candidates for removal? It turns out we can limit the number of possible removals to 2 (and check the starting array), which allows for an O(N) solution.

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

          Ohh, I felt it the same because I used the same O(n) logic in that problem too. Thanks for the clearance.

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

How many of you make at least 1 WA for problem A because the case m=n=1 ?

How many of you tried to implement dynamic programming on problem C and get stuck on it?

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

The case $$$n = m = 1$$$ on A is so dumb, at least include that in the samples. Do you want participants to solve problems or notice dumb edge cases? In general I am fine with a few sneaky edge cases but I think problem A is a bit special and should be as easy as possible.

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

    +1. What I think is the worst is that the statement does not mention about the range of $$$k$$$, so it is incomplete (if strictly speaking). Such a "dumb" with an incomplete statement is... not good.

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

      Due to this case i did't submit the solution till the last minute just because in the problems it is not mentioned that it is also possible that system return nothing.

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

      We can take it even further. Since there is no constraint on k. What is stopping me from asking -1 question to computer for $$$n = m = 1$$$ case. Where -1 denotes that instead of me computer asks me such queries and I reply correct Manthan distance for that query. I lost 90 pts and ACed A on 30th min after ACing B,C.

      Authors could have added a "non-negative" keyboard before k, but all they wanted was to troll people on A.

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

    Newbies smiling in the corner.

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

    +1. I think that not including this case in samples was an absolute shame. Problems were good but this issue alone is sufficient to make me downvote the round.

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

    I'm generally okay if the corner case involves some thinking. This one is, on the other hand, just boring and annoying.

    Let's read the statement again. The author intentionally left out $$$k \geq 0$$$, which made the definition of giving $$$0$$$ cells to the computer and receiving $$$0$$$ numbers extremely unnatural. Do we even receive if we give nothing? If you hate contestants that much, please don't set the first problem.

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

Systests were super fast! :D Were pretests == full tests for most (if not all) the problems?

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

Pass pretests during the contest but finally TLE on the pretest 31 during system test :(

136677675

And the exactly same code passes after the contest:

136680689

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

How to solve E? Two pointers?

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

    We can just greedy, consider a[i] is the smallest number in the array. We add the largest number a[n-1] to the set, then the next element is the largest that not bigger than a[k]=(a[n-1]+a[i])/2. Then the third should be the largest that not bigger than (a[k]+a[i])/2. My submission right after the contest :( https://codeforces.com/contest/1610/submission/136680210

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

      How did you come up with $$$a_i \geq 2(a_{i-1}-a_0)$$$ condition? All along I had $$$a_i \geq 2*a_{i-1}-a_0$$$ on paper and it lead me to nowhere.

      Nwm. Got an AC using it. Later I further relaxed that to $$$a_r-a_m \geq a_m-a_l$$$ and that was a mistake because I used $$$l=i,m=i+1,r=i+2$$$ after that.

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

Solved E almost in 1 hour but can't solve C or D in the remaining 2 hours..

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

Reaction in the third question ---> Although that was the easy one !

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

how to solve C ?

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

    Binary search on the range of answer

    monotonicity: if we can invite some k friends, then we can invite some k-1 friends. we want to find the smallest x s.t. we can't invite x friends, then the answer will be x-1.

    the greedy strategy to check a x: if we can invite some x friends, and say the first (the poorest one among all invited friends) friend's index is $$$f$$$, then both $$$a_f \geq x-1$$$ and $$$b_f \geq 0$$$ must be satisfied. similarly, for the second invited friend whose index is $$$s$$$, $$$a_s \geq x-2$$$ and $$$b_s \geq 1$$$ must hold, ... and so on. so for a given x we can loop through all friends (from the poorest to the richest) and keep track of the number of current invited friends, then check whether we can indeed invite x (or more) friends in the end.

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

How to solve F?

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

    A vertex can be an Oddysey vertex only if the weights of its incident edges have an odd sum. It turns out that it is always possible to make every such vertex an Oddysey vertex.

    From well-known Euler path stuff, it is always possible to partition the edges of any finite graph with exactly $$$k$$$ odd-degree vertices into $$$k/2$$$ paths and some number of cycles, such that the path endpoints are exactly the $$$k$$$ odd-degree vertices. Do this for the subgraph consisting of weight-1 edges and for the subgraph consisting of weight-2 edges. Then we can direct the cycles arbitrarily and just need to direct the paths so that every vertex which is an endpoint of a path in both subgraphs has one path coming in and one going out. (But that can be done by the same routine!)

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

      hey, is there a place i can read about this algorithm? (partition the edges of any finite graph with exactly k odd-degree vertices into k/2 paths and some number of cycles)

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

Once upon a time cf contests were good filled with beautiful tasks and nice ideas. And among all of them Persian contests were filled with nice graph dp problems as once Clix said. But now I see these contests filled with adhoc tasks and not quite programming for example this contest could be a perfect atcoder contest but in cf I expect seeing cf-like contests as I once did. I know people have different tastes of problems but in my opinion there are many nice sites for solving adhoc problem so let cf be for non-adhoc ones.

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

how is this supposed to be a global round?! just look at this submission for B

136651931

even a stupid chicken can clearly see that it will TLE. I find it strange that such retarded authors who can't even make decent pretests were allowed to create a global round.

idk ive been waiting 9 months to say this
»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Not able to understand problem D, can anybody please explain what do we have to do.

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

My solutions aren't judged on system tests? WTF?

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

The edge case in A is the case with no edges

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

Can someone help me with this?

136659367

Don't know why it is not passing testcases.

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

    Here's my working submission: 136686415. The mistake is that in Java comparing Integers using == is unreliable. Better to compare integers using .equals().

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

      Thanks a lot for finding out the problem.

      Don't you think it was compiler's fault?

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

        Emm, no. It's just that == compares by object's reference, which is not what you expect when comparing integers.

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

I have 2 friends that asked about if k can be equal to zero in problem A and they got a "yes" reply , how come this wasn't posted to all of us in global clarifications , very unfair

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

    If there is anything unfair about it it is the fact that your friends were given a reply. Obviously it is part of the problem to understand what the possible answers are.

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

      I completely agree,the reply given basically spoils the solution

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

        I disagree.

        I think the statement was poorly written and should have clarified in at least some way that k could be zero.

        However, I also think that if someone realizes "oh, it could be zero" and then asks if that is allowed, at that point they have already figured out the insight and replying to their message doesn't spoil the problem.

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

In C, I see lots of solutions using int mid = (low + high + 1) >> 1; instead of the usual int mid = (low + high) >> 1;. Can someone explain why?

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

    For convenience only. Imagine you have some condition cond which is true for all x <= b and false for all x > b (just like in task C). Now you want to find the smallest integer number x for which cond(x) == false (it is b + 1 as you can see). Typically your code will look something like the following:

    Code

    Imagine now, that the task has changed and now you wanna find the greatest number x for which cond(x) == true. Of course you can use the same code as above, but sometimes you will have to write additional conditional expressions for border cases. However in some cases we can use another approach without any additional code:

    Code

    In the second code example we cannot use int mid = (low + high) >> 1;, because high may be invalidated in case high = low + 1 before last iteration. That's why it is necessary to add one in the second approach.

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

This round not for beginners ....i am fullly depressed

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

Just got back to solving problem D since I couldn't solve it in the contest, and it is really a cool problem in my opinion.

When I came back I had my dark-mode filter enabled and found a funny easter egg in the statement! I won't ruin the fun for you so go find it yourself xD

But I'm writing this to ask, who is the problem setter for problem D?

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

    Good to see someone found it :)

    [edit:] guess who. Hind: Someone who doesn't have Lee in their username and they are not from China.

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

      I'm low-key writing the comment to let more people discover it :P

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

Would it make sense to have an option to buy tshirts if you are in the top 500, but not in the randomly selected list?

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

    The problem is it's not guarantied that the t-shirt will actually reach you in finite time. So if you buy, then they have to fix it I think, hard to fix...

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

:D

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

Can anyone understand why my Python solution for B has been TLEd when it looks the same as other python solutions that were accepted? https://codeforces.com/contest/1610/submission/136645557

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

Problem A lacks the sense of clarification

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

Thanks for this great contest!

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

Author of problem A might not have survived in ancient greece

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

Random works in problem F? 136677110

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

MikeMirzayanov, there is something weird going on with difficulty of problem H (it is currently 2100), which is clearly not the correct rating.

PS: It is fixed now, thanks.

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

Shout out to everyone who solved D, you deserve massive respect. After reading the solution for 2h I barely understand it...

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

Congratulations to tshirts winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_tshirts.py
randgen.cpp
List place Contest Rank Name
1 1610 1 Radewoosh
2 1610 2 tourist
3 1610 3 Petr
4 1610 4 he_____hezhou
5 1610 5 SpyCheese
6 1610 6 Subconscious
7 1610 7 huyinghao0706
8 1610 8 ksun48
9 1610 9 Golovanov399
10 1610 10 tmwilliamlin168
11 1610 11 Froggygua
12 1610 12 gisp_zjz
13 1610 13 maroonrk
14 1610 14 Toxel
15 1610 15 snuke
16 1610 16 hank55663
17 1610 17 aid
18 1610 18 natsugiri
19 1610 19 dlalswp25
20 1610 20 l1ll5
21 1610 21 inaFSTream
22 1610 22 Worteltje
23 1610 23 SSRS_
24 1610 24 hos.lyric
25 1610 25 lumibons
26 1610 26 nuip
27 1610 27 Endagorion
28 1610 28 jiangly
29 1610 29 zh0ukangyang
30 1610 30 AutumnKite
40 1610 40 ainta
51 1610 51 ljcleo
75 1610 75 Vercingetorix
78 1610 78 Marcin_smu
85 1610 85 Rubikun
94 1610 94 Laurie
106 1610 106 thenymphsofdelphi
126 1610 126 Nachia
164 1610 164 zundamochi_1117
171 1610 171 zerver52
180 1610 180 mshcherba
191 1610 190 Qzy___
256 1610 256 physics0523
279 1610 278 atodo
310 1610 310 CarrotCarrot
315 1610 315 arianfkh
330 1610 330 Zetr0
355 1610 355 guperman
470 1610 470 tobias.glimmerfors
483 1610 483 Gurban