### AliShahali1382's blog

By AliShahali1382, history, 2 weeks ago,

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

• +304

 » 2 weeks 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...
•  » » 2 weeks 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 :(
•  » » » 2 weeks ago, # ^ |   +142
•  » » » 2 weeks ago, # ^ |   +63 Sorry, it wasn't intentional :(
•  » » » 12 days ago, # ^ |   0 AMAZING!
•  » » 2 weeks 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:
•  » » » 2 weeks ago, # ^ |   +66 Omg It's so huge, May I share with family & friends? Give to charity?
•  » » » » 12 days ago, # ^ |   +1 There are amazing skits and plays. Then there are Global Rounds. :)
•  » » » 12 days ago, # ^ |   0 muri khaw
•  » » » 11 days ago, # ^ |   +18 Give us the Golden shaam, mr generous. It is more than 1 year we're waiting.
•  » » 2 weeks ago, # ^ |   +19 I think another problem with name SifidLee is coming XD isn't it?
•  » » » 2 weeks ago, # ^ |   +9 Omg that's such a nice idea.. I wish I was as smart :D
 » 2 weeks ago, # |   +76 As a tester, good luck on contest and upsolve all problems because they are awesome!
 » 2 weeks 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. :(
•  » » 2 weeks ago, # ^ |   0 Hi is the registration close now ? T-T
•  » » 2 weeks ago, # ^ |   +3 Spoiler<3 :(
 » 2 weeks 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?
•  » » 2 weeks ago, # ^ |   +27 3, info will be updated soon
 » 2 weeks ago, # |   +40 What does sifid like this time :D ?
 » 2 weeks ago, # |   +74 Orz
•  » » 2 weeks ago, # ^ |   +59 Orz
•  » » » 2 weeks ago, # ^ |   +32 Orz
•  » » » » 2 weeks ago, # ^ |   +32 Orz
•  » » » » » 2 weeks ago, # ^ |   +23 gorz
•  » » » » » » 2 weeks ago, # ^ |   +45 goraz
•  » » » » » » » 2 weeks ago, # ^ |   -31 As a tester, orz
 » 2 weeks ago, # |   -73 Hope AliShahali1382 will not make shitty problems like 1440C2 - Binary Table (Hard Version) this time.
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +17 That problem was prepared and authored by Mohammad.H915 ! not AliShahali1382
•  » » » 2 weeks ago, # ^ |   -27 1440C2 — Binary Table (Hard Version) was authored and prepared by Mohammad.H915! not AliShahali1382
 » 2 weeks ago, # | ← Rev. 2 →   -28 I expect that there would be just lengthy implementation based problems.
•  » » 2 weeks ago, # ^ |   0 Yes, but actually No.
 » 2 weeks ago, # |   +16 GL, HF
 » 2 weeks ago, # |   +160 As a tester
•  » » 2 weeks ago, # ^ |   +5 No light-hearted meme this time :(
•  » » » 2 weeks ago, # ^ |   +27 Here you go...https://imgflip.com/i/5uz8py
•  » » » » 2 weeks ago, # ^ |   +8 :omglol:
•  » » » » 13 days ago, # ^ |   +6 Dies in WA on test 2
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   -6 XD
 » 2 weeks ago, # | ← Rev. 2 →   +57 Iranian contests always had interesting problems,I am sure this one will be as good as others
•  » » 2 weeks ago, # ^ |   +89
•  » » 13 days ago, # ^ |   +32 CF Round 684 still gives me PTSD...
 » 2 weeks ago, # |   +7 meme
 » 2 weeks ago, # |   +39 Auto comment: topic has been updated by AmShZ (previous revision, new revision, compare).
 » 2 weeks ago, # |   +58 As a tester, I wish everyone good luck!
 » 2 weeks ago, # |   +57 R.I.P Tet
 » 2 weeks ago, # |   +10 I'm so excited for this round :")
•  » » 13 days ago, # ^ |   0 same dude same
 » 2 weeks ago, # | ← Rev. 5 →   -36 :)
 » 2 weeks ago, # |   +13 I am excited for another Iranian round :)
•  » » 13 days ago, # ^ |   0 This is an exciting competition :))
 » 2 weeks ago, # |   0 Hooray :D
 » 2 weeks ago, # | ← Rev. 2 →   +8 Please give the scoring distribution as early as you can as there are 9 problems
 » 2 weeks ago, # |   0 Hope for a good one :v
 » 2 weeks ago, # |   0 Good luck everyone!
 » 13 days ago, # |   0 Expect Great Round :"
•  » » 13 days ago, # ^ |   0 Hope it meets your expectations brother
 » 13 days ago, # |   +16 heeeyyp... have good contest...
•  » » 13 days ago, # ^ |   0 and Lets Hope you will participate :_:
 » 13 days ago, # | ← Rev. 2 →   -25 NOTE THE USUAL TIMING AND UNUSUAL LENGTH!!! :D[ edit 1 ] : knew will get dislikes but still there was something inside me that was telling me this is a little better comment to post, compared to my other comments but okay -_-
 » 13 days ago, # |   0 wow, two contests in a row! It's sad that Monday and Tuesday are the only days I go to school this week..
 » 13 days ago, # |   0 Good luck!
 » 13 days ago, # |   0 every global contest makes me upset, I hope this round will be diffrent .Good luck to every one QwQ
 » 13 days ago, # |   0 "The score distribution will be announced at least 5 minutes before the round starts! :)" really very useful information :) thanks
 » 13 days ago, # |   0 its irretating to get stuck on (pupil-specialist) for months.
 » 13 days ago, # |   -33 AliShahali1382 Can I write my previous comment?
 » 13 days ago, # |   +25 I definitely don't find any reason for not giving the scoring distribution an hour earlier before the contest
•  » » 12 days ago, # ^ |   +3 Why is scoring distribution so significant before the round? I don't quite understand, can you explain?
•  » » » 12 days ago, # ^ |   0 It helps to get an idea about the problems and how to approach those
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   -25 As if you will solve more than AB lmao
•  » » » » » 12 days ago, # ^ |   +7 do one thing, solve more than me in this contest and show that you can code rather than talking like an asshole,everytime I comment anywhere you come and irritate such a pure asshole,go get a life *****
 » 12 days ago, # |   0 Hope everyone has a good contest, xqcL my juicer
 » 12 days ago, # |   +13 At least 30 minutes before: Where is the score distribution?
 » 12 days ago, # |   +39 At least 5 mins -> 6 mins :)
 » 12 days ago, # |   +6 I prolly will go back to being a specialist, but it would be fun anyway!Good luck everyone!
 » 12 days ago, # |   +95 Is this div.1?
 » 12 days ago, # |   -25 What kind of questions are these! Very difficult for me to understand, couldn't make out A; if you think something is missing please update the problem statement with a good example.
 » 12 days ago, # |   -25 more than 30 min still couldn't get what they ask for in problem A
 » 12 days ago, # | ← Rev. 2 →   -12 Sad :')
 » 12 days ago, # |   0 I think setters and testers are giving down votes to everyones comment
•  » » 12 days ago, # ^ |   +39 We're too busy :(
 » 12 days ago, # |   +1 Did B,C in first try still couldn't do A ;-;
•  » » 12 days ago, # ^ |   +6 everyone who didn't pass A probably missed this case n==1 && m == 1
•  » » » 12 days ago, # ^ |   0 omg, I hate my life
•  » » 12 days ago, # ^ |   0 you missed the case with answer 2 sad(
 » 12 days ago, # |   +39 tfw your only WAs on a problem were on A
 » 12 days 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 ;).
•  » » 12 days ago, # ^ |   +2
•  » » » 10 days ago, # ^ |   0
 » 12 days ago, # |   +26 Is this Rated?
•  » » 12 days 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?
•  » » » 12 days ago, # ^ |   +13 The system is calculating the rating change for each one
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   +13
 » 12 days ago, # |   +25 B,C,D are decent problems but A is not appropriate for its position.
 » 12 days ago, # |   +5 Loved problem D! Brilliant round
 » 12 days ago, # |   -7 Question a is so difficult to understand that I am very sad
 » 12 days 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.
 » 12 days ago, # |   0 How to solve C ?
•  » » 12 days 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.
•  » » » 12 days ago, # ^ |   0 thanks alot, i implemented the similiar idea and got accepted.
•  » » » 12 days ago, # ^ |   0 wow, best explanation.
•  » » » 12 days ago, # ^ | ← Rev. 3 →   0 i thought that : let that r[i] is all peoples that strictly rich than i . And p[i] is all peoples that strictly poor than i, so i made it for r[i] = n - i; p[i] = i - 1; But why is my solution got a WA?And my 1st testcase's wrong too Thanks a lot for your great explanation before.
•  » » » 12 days 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?
 » 12 days ago, # |   0 not good at english but 3 hour i can't understand A .........
 » 12 days ago, # |   -22 D is easier than C
•  » » 12 days ago, # ^ |   0 How did u know?
 » 12 days ago, # |   -16 For anyone looking for video explanations (for A,B and C only)You can visit here
 » 12 days ago, # |   +53 Idk how D has so much solves compared to E. For me it felt D >> C > E.
•  » » 12 days ago, # ^ | ← Rev. 3 →   +2 Shitttt!! Got the blunder upon seeing others' code T-T
•  » » » 12 days 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).
•  » » 12 days 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.
•  » » 12 days 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?
 » 12 days 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.
 » 12 days ago, # |   +6 Problem C has taken atleast a decade off my lifespan I think. How to do it?
•  » » 12 days ago, # ^ |   +6 binary search
 » 12 days ago, # |   -9 where are the tutorials ??
 » 12 days ago, # |   +6 How do you do D?
•  » » 12 days 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.
•  » » » 12 days ago, # ^ |   +2 How did you come up with that least LSB thing? I wasn't able to solve this part.
•  » » » 12 days ago, # ^ |   +16 This isn't a solution unless you explain why exactly these subsequences are good.
•  » » » » 12 days 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.
•  » » » » » 12 days 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?
•  » » » » » » 11 days 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$.
•  » » » » 12 days 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$.
•  » » 12 days 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
 » 12 days ago, # |   0 Contest so hard, but anyone can give me hint for solving problem C.
•  » » 12 days ago, # ^ |   +1 Binary Search on answer
•  » » » 12 days ago, # ^ |   -6 tks, I solved this problem.
 » 12 days 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
 » 12 days ago, # |   0 what actually you want from problem solver for problem A??
•  » » 12 days ago, # ^ | ← Rev. 3 →   -27 Hint 1: 0 <= ans <= 2Hint 2: m == 1 && n == 1 => 0
•  » » » 12 days 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.
•  » » » » 12 days ago, # ^ |   -11 tks, but i think problem A, n = 1 and m = 1, it's crazy.
•  » » 12 days 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.
 » 12 days ago, # |   -17 Got MLE on F...
 » 12 days ago, # |   +39 Imagine coming 2nd and still have negative delta. Couldn't be me.
 » 12 days ago, # | ← Rev. 2 →   +3 I found B quite similar to this Grandma Capa Knits a Scarf
 » 12 days ago, # |   +11 I feel like I have seen Problem B in one of the previous cf rounds
•  » » 12 days ago, # ^ |   +11
•  » » » 12 days ago, # ^ |   0 I used same solution today, but got time limit exceeded.
•  » » » » 12 days 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.
•  » » » » » 12 days ago, # ^ |   +8 Ohh, I felt it the same because I used the same O(n) logic in that problem too. Thanks for the clearance.
 » 12 days 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?
•  » » 12 days ago, # ^ |   +1 Me haha, spent half an hour on trying to make DP work but failed.
•  » » 12 days ago, # ^ |   0 Yes to both. For (c) I used a 3D DP int[][][] solution but got Memory exceeded. Then, I thought that I should use a hash map instead since the int[][][] would be very sparse, but this got TLE
 » 12 days ago, # |   0 What's the logic behind solving B?
 » 12 days 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.
•  » » 12 days 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.
•  » » » 12 days 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.
•  » » » » 12 days ago, # ^ |   +8 nothing != zero
•  » » » 12 days 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.
•  » » 12 days ago, # ^ |   0 Newbies smiling in the corner.
•  » » 12 days 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.
•  » » 12 days 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.
 » 12 days ago, # |   +12 Systests were super fast! :D Were pretests == full tests for most (if not all) the problems?
 » 12 days 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
 » 12 days ago, # |   0 How to solve E? Two pointers?
•  » » 12 days 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
•  » » 12 days 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).
•  » » » 12 days 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.
 » 12 days ago, # |   0 Looks like I'm never gonna get out of green. Once in a blue moon, I can solve all three otherwise No :(
•  » » 12 days ago, # ^ |   0 and you didn't participated
•  » » » 12 days ago, # ^ |   0 I tried C. couldn't get a working solution. Greedy became too messy. Gave up.
•  » » » » 12 days ago, # ^ |   0 try reading this 136689986.maybe it'll help
 » 12 days ago, # |   0 Solved E almost in 1 hour but can't solve C or D in the remaining 2 hours..
 » 12 days ago, # |   0 Reaction in the third question ---> Although that was the easy one !
 » 12 days ago, # |   0 can we solve c using binary search on map??
 » 12 days ago, # |   0 how to solve C ?
•  » » 12 days ago, # ^ | ← Rev. 2 →   0
•  » » 12 days 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.
•  » » » 12 days ago, # ^ |   0 Thanks
 » 12 days ago, # |   +31 https://codeforces.com/contest/1610/submission/136663604wrong compiler :(
 » 12 days ago, # |   0 How to solve F?
•  » » 12 days 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!)
•  » » » 11 days 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)
 » 12 days 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.
•  » » 12 days ago, # ^ |   +30 no need for mention
 » 12 days 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
•  » » 12 days ago, # ^ |   +126
•  » » » 12 days ago, # ^ |   +71 Amshz :
•  » » 12 days ago, # ^ |   +14 TooBased
•  » » 12 days ago, # ^ |   +15 i was confused why you are being so mean, until i saw the spoiler...
•  » » 12 days ago, # ^ |   +16 I'm a stupid chicken that floats on water. Can confirm that I can see that it will TLE
 » 12 days ago, # |   +37 First time tourist upsolved a problem since ages!
 » 12 days ago, # |   +1 Not able to understand problem D, can anybody please explain what do we have to do.
•  » » 12 days ago, # ^ |   -10 For example we have nonempty subsequence of indices of array a: $i_1  » 12 days ago, # | +43 My solutions aren't judged on system tests? WTF? •  » » 12 days ago, # ^ | ← Rev. 2 → +8 MikeMirzayanov hey man! can you fix this.  » 12 days ago, # | +47 The edge case in A is the case with no edges  » 12 days ago, # | 0 Can someone help me with this?136659367Don't know why it is not passing testcases. •  » » 12 days 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(). •  » » » 12 days ago, # ^ | 0 Thanks a lot for finding out the problem.Don't you think it was compiler's fault? •  » » » » 12 days ago, # ^ | +1 Emm, no. It's just that == compares by object's reference, which is not what you expect when comparing integers. •  » » » » » 12 days ago, # ^ | 0 I don't think it's a valid point. The program ran successfully for so many testcases comparing integers with == •  » » » » » » 12 days ago, # ^ | +1 Read about java primitives/wrappers comparison and integer pool •  » » » » » » 12 days ago, # ^ | +1 This is not true. read here  » 12 days 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 •  » » 12 days 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. •  » » » 12 days ago, # ^ | 0 I completely agree,the reply given basically spoils the solution •  » » » » 12 days 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.  » 12 days ago, # | +99 Meme:  » 12 days 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? •  » » 12 days ago, # ^ | 0 well it will work very much the same you can do as you wish:P •  » » 12 days 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.  » 12 days ago, # | +1 This round not for beginners ....i am fullly depressed  » 12 days 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? •  » » 12 days 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. •  » » » 12 days ago, # ^ | +10 I'm low-key writing the comment to let more people discover it :P  » 12 days 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? •  » » 12 days 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...  » 12 days ago, # | +82 :D  » 12 days 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 •  » » 12 days ago, # ^ | +3 Your code should not pass because it's$O(n^2)\$.
 » 12 days ago, # |   +6 Problem A lacks the sense of clarification
 » 12 days ago, # |   0 Guys the problems are nice, but you should limit the red herring statements. also the visible pretest 1 was not containing more testcases and certain edge cases are hidden intentionally. it makes harder to visualize and think of the logic.overall it was a nice competition!! well done ...
 » 12 days ago, # |   -27 Thanks for this great contest!
 » 12 days ago, # |   +22 Author of problem A might not have survived in ancient greece
•  » » 11 days ago, # ^ |   0 Actually its the first time I appreciate living in Iran...
 » 12 days ago, # |   +4 Random works in problem F? 136677110
 » 12 days 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.
 » 11 days 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...
•  » » 7 days ago, # ^ |   0 I can relate
»
6 days 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 PipelinePunch
315 1610 315 arianfkh
330 1610 330 Zetr0
355 1610 355 guperman
470 1610 470 tobias.glimmerfors
483 1610 483 CurB