### AliShahali1382's blog

By AliShahali1382, history, 15 months ago,

Hello, Codeforces!

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

• +312

| Write comment?
 » 15 months ago, # | ← 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. Sorry, it wasn't intentional :( make it 6 nights...
•  » » 15 months ago, # ^ |   +212 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 :(
•  » » » 15 months ago, # ^ |   +142
•  » » » 15 months ago, # ^ |   +63 Sorry, it wasn't intentional :(
•  » » 15 months ago, # ^ |   +113 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:
•  » » » 15 months ago, # ^ |   +66 Omg It's so huge, May I share with family & friends? Give to charity?
•  » » » » 14 months ago, # ^ |   +1 There are amazing skits and plays. Then there are Global Rounds. :)
•  » » » 14 months ago, # ^ |   +18 Give us the Golden shaam, mr generous. It is more than 1 year we're waiting.
•  » » 15 months ago, # ^ |   +19 I think another problem with name SifidLee is coming XD isn't it?
•  » » » 15 months ago, # ^ |   +9 Omg that's such a nice idea.. I wish I was as smart :D
 » 15 months ago, # |   +76 As a tester, good luck on contest and upsolve all problems because they are awesome!
 » 15 months ago, # |   +106 As a tester, I can confirm that the problems are pretty nice! I would recommend participating in this round and enjoying the problems. SpoilerApologies to the setters for having them first change one problem's constraints and then for them to have to remove the problem entirely; it was a nice problem in my opinion. :(
•  » » 14 months ago, # ^ |   +3 Spoiler<3 :(
 » 15 months ago, # |   +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?
•  » » 15 months ago, # ^ |   +27 3, info will be updated soon
 » 15 months ago, # |   +40 What does sifid like this time :D ?
 » 15 months ago, # |   +74 Orz
•  » » 15 months ago, # ^ |   +59 Orz
•  » » » 15 months ago, # ^ |   +32 Orz
•  » » » » 15 months ago, # ^ |   +32 Orz
•  » » » » » 15 months ago, # ^ |   +23 gorz
•  » » » » » » 15 months ago, # ^ |   +45 goraz
•  » » » » » » » 15 months ago, # ^ |   -31 As a tester, orz
 » 15 months ago, # |   -73 Hope AliShahali1382 will not make shitty problems like 1440C2 - Binary Table (Hard Version) this time.
•  » » 15 months ago, # ^ | ← Rev. 2 →   +17 That problem was prepared and authored by Mohammad.H915 ! not AliShahali1382
 » 15 months ago, # |   +16 GL, HF
 » 15 months ago, # |   +160 As a tester
•  » » 15 months ago, # ^ |   +5 No light-hearted meme this time :(
 » 15 months ago, # | ← Rev. 2 →   +57 Iranian contests always had interesting problems,I am sure this one will be as good as others
•  » » 15 months ago, # ^ |   +89
•  » » 14 months ago, # ^ |   +32 CF Round 684 still gives me PTSD...
 » 15 months ago, # |   +7 meme
 » 15 months ago, # |   +39 Auto comment: topic has been updated by AmShZ (previous revision, new revision, compare).
 » 15 months ago, # |   +58 As a tester, I wish everyone good luck!
 » 15 months ago, # |   +57 R.I.P Tet
 » 15 months ago, # |   +10 I'm so excited for this round :")
 » 15 months ago, # |   +13 I am excited for another Iranian round :)
•  » » 14 months ago, # ^ |   0 This is an exciting competition :))
 » 14 months ago, # |   0 Hooray :D
 » 14 months ago, # | ← Rev. 2 →   +8 Please give the scoring distribution as early as you can as there are 9 problems
 » 14 months ago, # |   0 Expect Great Round :"
•  » » 14 months ago, # ^ |   0 Hope it meets your expectations brother
 » 14 months ago, # |   +16 heeeyyp... have good contest...
 » 14 months ago, # | ← Rev. 4 →   -25 Hidden...
 » 14 months ago, # |   0 every global contest makes me upset, I hope this round will be diffrent .Good luck to every one QwQ
 » 14 months ago, # |   0 "The score distribution will be announced at least 5 minutes before the round starts! :)" really very useful information :) thanks
 » 14 months ago, # |   +25 I definitely don't find any reason for not giving the scoring distribution an hour earlier before the contest
•  » » 14 months ago, # ^ |   +3 Why is scoring distribution so significant before the round? I don't quite understand, can you explain?
•  » » » 14 months ago, # ^ |   0 It helps to get an idea about the problems and how to approach those
 » 14 months ago, # |   +13 At least 30 minutes before: Where is the score distribution?
 » 14 months ago, # |   +39 At least 5 mins -> 6 mins :)
 » 14 months ago, # |   +6 I prolly will go back to being a specialist, but it would be fun anyway!Good luck everyone!
 » 14 months ago, # |   +95 Is this div.1?
 » 14 months ago, # | ← Rev. 2 →   -12 Sad :')
 » 14 months ago, # |   0 I think setters and testers are giving down votes to everyones comment
•  » » 14 months ago, # ^ |   +39 We're too busy :(
 » 14 months ago, # |   +1 Did B,C in first try still couldn't do A ;-;
•  » » 14 months ago, # ^ |   +6 everyone who didn't pass A probably missed this case n==1 && m == 1
•  » » » 14 months ago, # ^ |   0 omg, I hate my life
 » 14 months ago, # |   +39 tfw your only WAs on a problem were on A
 » 14 months ago, # |   -13 I'm never doing global rounds in my entire life, never, ever, again.p.s: but it was a good contest, and it's not that because the problemsetters were Persian, not at all ;).
•  » » 14 months ago, # ^ |   +2
 » 14 months ago, # |   +26 Is this Rated?
•  » » 14 months ago, # ^ | ← 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?
•  » » » 14 months ago, # ^ |   +13 The system is calculating the rating change for each one
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +13
 » 14 months ago, # |   +25 B,C,D are decent problems but A is not appropriate for its position.
 » 14 months ago, # | ← Rev. 2 →   +5 .
 » 14 months ago, # |   +26 I don't know what to say about this round. I just appreciate that I don't feel bad although I performed poorly.
 » 14 months ago, # |   0 How to solve C ?
•  » » 14 months ago, # ^ | ← 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 arrayIf 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.
•  » » » 14 months ago, # ^ |   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?
 » 14 months ago, # |   -16 For anyone looking for video explanations (for A,B and C only)You can visit here
 » 14 months ago, # |   +53 Idk how D has so much solves compared to E. For me it felt D >> C > E.
•  » » 14 months ago, # ^ | ← Rev. 3 →   +2 Shitttt!! Got the blunder upon seeing others' code T-T
•  » » » 14 months ago, # ^ |   +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).
•  » » 14 months ago, # ^ | ← 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.
•  » » 14 months ago, # ^ |   +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?
 » 14 months ago, # | ← 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.
 » 14 months ago, # |   +6 Problem C has taken atleast a decade off my lifespan I think. How to do it?
•  » » 14 months ago, # ^ |   +6 binary search
 » 14 months ago, # |   +6 How do you do D?
•  » » 14 months ago, # ^ | ← 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.
•  » » » 14 months ago, # ^ |   +2 How did you come up with that least LSB thing? I wasn't able to solve this part.
•  » » » 14 months ago, # ^ |   +16 This isn't a solution unless you explain why exactly these subsequences are good.
•  » » » » 14 months ago, # ^ | ← 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.
•  » » » » » 14 months ago, # ^ |   +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?
•  » » » » » » 14 months ago, # ^ |   +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$.
•  » » » » 14 months ago, # ^ |   +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: $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. $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$.
•  » » 14 months ago, # ^ | ← 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
 » 14 months ago, # |   0 Contest so hard, but anyone can give me hint for solving problem C.
•  » » 14 months ago, # ^ |   +1 Binary Search on answer
 » 14 months ago, # | ← 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
 » 14 months ago, # |   0 what actually you want from problem solver for problem A??
•  » » 14 months ago, # ^ | ← Rev. 3 →   -27 Hint 1: 0 <= ans <= 2Hint 2: m == 1 && n == 1 => 0
•  » » » 14 months ago, # ^ |   +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.
•  » » 14 months ago, # ^ |   +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.
 » 14 months ago, # |   -17 Got MLE on F...
 » 14 months ago, # |   +39 Imagine coming 2nd and still have negative delta. Couldn't be me.
 » 14 months ago, # | ← Rev. 2 →   +3 I found B quite similar to this Grandma Capa Knits a Scarf
 » 14 months ago, # |   +11 I feel like I have seen Problem B in one of the previous cf rounds
•  » » 14 months ago, # ^ |   +11
•  » » » 14 months ago, # ^ |   0 I used same solution today, but got time limit exceeded.
•  » » » » 14 months ago, # ^ |   +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.
•  » » » » » 14 months ago, # ^ |   +8 Ohh, I felt it the same because I used the same O(n) logic in that problem too. Thanks for the clearance.
 » 14 months ago, # | ← 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?
•  » » 14 months ago, # ^ |   +1 Me haha, spent half an hour on trying to make DP work but failed.
 » 14 months ago, # |   +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.
•  » » 14 months ago, # ^ |   +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.
•  » » » 14 months ago, # ^ |   -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.
•  » » » » 14 months ago, # ^ |   +8 nothing != zero
•  » » » 14 months ago, # ^ | ← 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.
•  » » 14 months ago, # ^ |   0 Newbies smiling in the corner.
•  » » 14 months ago, # ^ |   -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.
•  » » 14 months ago, # ^ |   +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.
 » 14 months ago, # |   +12 Systests were super fast! :D Were pretests == full tests for most (if not all) the problems?
 » 14 months ago, # | ← Rev. 2 →   0 Pass pretests during the contest but finally TLE on the pretest 31 during system test :(136677675And the exactly same code passes after the contest:136680689
 » 14 months ago, # |   0 How to solve E? Two pointers?
•  » » 14 months ago, # ^ | ← 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
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 spoilerOk so i guessed that as long as every 3-tuple of the array is not terrible, then the array is good.So under this condition the good sequences are $a_0,a_1,a_2,\ldots$ where $a_i \geq 2(a_{i-1}-a_0)+a_0$.So actually there are only $log(10^9)$ distinct elements in each good subsequence and we can brute force each possible $a_0$. (Remember to handle equal elements properly or you might TLE).
•  » » » 14 months ago, # ^ | ← 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.
 » 14 months ago, # |   0 Solved E almost in 1 hour but can't solve C or D in the remaining 2 hours..
 » 14 months ago, # |   0 Reaction in the third question ---> Although that was the easy one !
 » 14 months ago, # |   0 how to solve C ?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0
•  » » 14 months ago, # ^ | ← Rev. 2 →   +4 Binary search on the range of answermonotonicity: 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.
 » 14 months ago, # |   +31 https://codeforces.com/contest/1610/submission/136663604wrong compiler :(
 » 14 months ago, # |   0 How to solve F?
•  » » 14 months ago, # ^ | ← 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!)
•  » » » 14 months ago, # ^ |   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)
 » 14 months ago, # |   +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.
•  » » 14 months ago, # ^ |   +30 no need for mention
 » 14 months ago, # |   +576 how is this supposed to be a global round?! just look at this submission for B136651931even 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
•  » » 14 months ago, # ^ |   +126
•  » » » 14 months ago, # ^ |   +71 Amshz :
•  » » 14 months ago, # ^ |   +14 TooBased
•  » » 14 months ago, # ^ |   +15 i was confused why you are being so mean, until i saw the spoiler...
•  » » 14 months ago, # ^ |   +16 I'm a stupid chicken that floats on water. Can confirm that I can see that it will TLE
 » 14 months ago, # |   +1 Not able to understand problem D, can anybody please explain what do we have to do.
 » 14 months ago, # |   +43 My solutions aren't judged on system tests? WTF?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +8 MikeMirzayanov hey man! can you fix this.
 » 14 months ago, # |   +47 The edge case in A is the case with no edges
 » 14 months ago, # |   0 Can someone help me with this?136659367Don't know why it is not passing testcases.
•  » » 14 months ago, # ^ |   +1 Here's my working submission: 136686415. The mistake is that in Java comparing Integers using == is unreliable. Better to compare integers using .equals().
•  » » » 14 months ago, # ^ |   0 Thanks a lot for finding out the problem.Don't you think it was compiler's fault?
•  » » » » 14 months ago, # ^ |   +1 Emm, no. It's just that == compares by object's reference, which is not what you expect when comparing integers.
•  » » » » » 14 months ago, # ^ |   0 I don't think it's a valid point. The program ran successfully for so many testcases comparing integers with ==
•  » » » » » » 14 months ago, # ^ |   +1 Read about java primitives/wrappers comparison and integer pool
•  » » » » » » 14 months ago, # ^ |   +1 This is not true. read here
 » 14 months ago, # |   +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
•  » » 14 months ago, # ^ |   +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.
•  » » » 14 months ago, # ^ |   0 I completely agree,the reply given basically spoils the solution
•  » » » » 14 months ago, # ^ |   +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.
 » 14 months ago, # |   +99 Meme:
 » 14 months ago, # |   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?
•  » » 14 months ago, # ^ | ← 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: Codewhile (low < high) { int mid = (low + high) >> 1; if (cond(mid)) { low = mid + 1; } else { high = mid; } } assert(low == high); assert(low == b + 1); 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: Codewhile (low < high) { int mid = (low + high + 1) >> 1; if (cond(mid)) { low = mid; } else { high = mid - 1; } } assert(low == high); assert(low == b); 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.
 » 14 months ago, # |   +1 This round not for beginners ....i am fullly depressed
 » 14 months ago, # | ← 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 xDBut I'm writing this to ask, who is the problem setter for problem D?
•  » » 14 months ago, # ^ | ← 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.
•  » » » 14 months ago, # ^ |   +10 I'm low-key writing the comment to let more people discover it :P
 » 14 months ago, # |   +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?
•  » » 14 months ago, # ^ |   +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...
 » 14 months ago, # |   +82 :D
 » 14 months ago, # | ← 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
•  » » 14 months ago, # ^ |   +3 Your code should not pass because it's $O(n^2)$.
 » 14 months ago, # |   +6 Problem A lacks the sense of clarification
 » 14 months ago, # |   -27 Thanks for this great contest!
 » 14 months ago, # |   +22 Author of problem A might not have survived in ancient greece
•  » » 14 months ago, # ^ |   0 Actually its the first time I appreciate living in Iran...
 » 14 months ago, # |   +4 Random works in problem F? 136677110
 » 14 months ago, # | ← 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.
 » 14 months ago, # | ← Rev. 2 →   +7 Shout out to everyone who solved D, you deserve massive respect. After reading the solution for 2h I barely understand it...
»
14 months ago, # |
+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
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 gs18115
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 Serin
315 1610 315 arianfkh
330 1610 330 Zetr0
355 1610 355 guperman
470 1610 470 tobias.glimmerfors
483 1610 483 Gurban