AliShahali1382's blog

By AliShahali1382, history, 3 years ago, In English

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

Announcement of Codeforces Global Round 17
  • Vote: I like it
  • +312
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 3   Vote: I like it +259 Vote: I do not like it

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

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

    I'm so depressed that all of my hard work and dedication on preparing problems has failed as I couldn't achieve the first comment :(

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

    On behalf of the contest setter's committee, I would like to congrate you for achieving the position of first commenter. Here's a golden titop prepared by the committee for all your dedication and hard work:

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

      Omg It's so huge, May I share with family & friends? Give to charity?

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

        There are amazing skits and plays. Then there are Global Rounds. :)

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

      Give us the Golden shaam, mr generous. It is more than 1 year we're waiting.

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

    I think another problem with name SifidLee is coming XD isn't it?

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

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

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

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

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

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?

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

What does sifid like this time :D ?

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

Orz

»
3 years ago, # |
  Vote: I like it -73 Vote: I do not like it

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

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

GL, HF

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

    No light-hearted meme this time :(

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

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

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it
meme
»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

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

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

As a tester, I wish everyone good luck!

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

R.I.P Tet

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

I'm so excited for this round :")

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

I am excited for another Iranian round :)

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

Hooray :D

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

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

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

Expect Great Round :"

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

heeeyyp... have good contest...

»
3 years ago, # |
Rev. 4   Vote: I like it -25 Vote: I do not like it

Hidden...

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

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

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

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

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

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

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

    Why is scoring distribution so significant before the round? I don't quite understand, can you explain?

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

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

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

At least 5 mins -> 6 mins :)

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

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

Good luck everyone!

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

Is this div.1?

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

Sad :')

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

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

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

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

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

    everyone who didn't pass A probably missed this case n==1 && m == 1

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

    you missed the case with answer 2 sad(

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

tfw your only WAs on a problem were on A

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

Is this Rated?

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

    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?

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

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

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

.

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

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

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

How to solve C ?

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

    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.

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

      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?

»
3 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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

You can visit here

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

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

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

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

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

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

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

    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.

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

    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?

»
3 years ago, # |
Rev. 3   Vote: I like it +42 Vote: I do not like it

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.

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

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

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

How do you do D?

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

    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.

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

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

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

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

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

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

          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?

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

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

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

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

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

    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

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

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

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

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

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

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

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it -27 Vote: I do not like it

    Hint 1: 0 <= ans <= 2

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

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

      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.

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

    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.

»
3 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Got MLE on F...

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

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

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

I found B quite similar to this

Grandma Capa Knits a Scarf

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

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

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

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

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

        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.

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

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

»
3 years ago, # |
Rev. 3   Vote: I like it +39 Vote: I do not like it

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?

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

    Me haha, spent half an hour on trying to make DP work but failed.

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

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.

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

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

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

      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.

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

      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.

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

    Newbies smiling in the corner.

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

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

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

    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.

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

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

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

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

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

How to solve E? Two pointers?

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

    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.net/contest/1610/submission/136680210

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

      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.

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

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

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

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

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

how to solve C ?

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

    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.

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

How to solve F?

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

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

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

      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)

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

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.

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

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

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

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

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

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

The edge case in A is the case with no edges

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

Can someone help me with this?

136659367

Don't know why it is not passing testcases.

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

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

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

      Thanks a lot for finding out the problem.

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

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

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

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

          I don't think it's a valid point. The program ran successfully for so many testcases comparing integers with ==

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

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

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

    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.

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

      I completely agree,the reply given basically spoils the solution

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

        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.

»
3 years ago, # |
  Vote: I like it +99 Vote: I do not like it
Meme:
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

    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.

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

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

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

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?

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

    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.

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

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

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

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?

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

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

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

:D

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

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.net/contest/1610/submission/136645557

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

Problem A lacks the sense of clarification

»
3 years ago, # |
  Vote: I like it -27 Vote: I do not like it

Thanks for this great contest!

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

Author of problem A might not have survived in ancient greece

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

    Actually its the first time I appreciate living in Iran...

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

Random works in problem F? 136677110

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

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.

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

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

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

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