### rsj's blog

By rsj, 2 months ago,

Greetings, CodeForces!

jiangtaizhe001, qzhwlzy and I rsj are more than excited to invite you to participate in TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!), which starts on Jan/29/2023 17:35 (Moscow time).

The round is open and rated for everyone. You are given 9 problems, no subtasks or interactive problems, and you have 3 hours to solve them. It is recommended to read all problems. The statements were made as briefly and clearly as we could. Enjoy the contest!

UPD: Score distribution: $500-1000-1750-2000-2250-2500-3250-3500-3750$

Sincere thanks to:

Thanks to Vaticle's sponsership, winners will receive awesome prizes!

Cash and Swag Prizes

• 1st place: 500 Euros
• 2nd place: 250 Euros
• 3rd place: 100 Euros
• Top 50: TypeDB hoodie, t-shirt and stickers
• Random 50 of 51-250: TypeDB t-shirt and stickers

Vaticle is a team of people driven to empower engineers to solve complex problems. We are the creators of the strongly-typed database, TypeDB, and its query language, TypeQL. You can find out more about our work from another announcement post, interview post, our website and GitHub pages. You can also apply directly to our team using the button below:

Apply →

UPD1: Editorial

UPD2: Congratulations to the winners:

• +209

 » 2 months ago, # |   -51 omg cyan roundGL to everyone
•  » » 2 months ago, # ^ |   -62 profile picture stealer :D
 » 2 months ago, # |   -52 As a tester, I hope that you will enjoy the round. The problem set seems much better than when I originally tested, which is a good thing.
•  » » 2 months ago, # ^ | ← Rev. 9 →   -17 maybe
•  » » 2 months ago, # ^ |   +6 I think you are lier
•  » » » 2 months ago, # ^ |   +33 I am not. You are not a tester, so you do not know what problems were in there originally.
•  » » » » 2 months ago, # ^ |   0 Many problems have changed. This is a new set of questions for me.
 » 2 months ago, # |   0 The announcement post redirects to a draft (not visible to general audience), not a blog.
 » 2 months ago, # | ← Rev. 2 →   +46 Another 500 Euros to tourist.
•  » » 2 months ago, # ^ |   +15 or benq!
•  » » » 2 months ago, # ^ |   -9 or tibinyte!
•  » » » » 2 months ago, # ^ |   +21 tibinyte will earn -500 Euro
•  » » » 2 months ago, # ^ |   -8 the tourist caught up with the bank in the ratings
•  » » 2 months ago, # ^ |   +14 or jiangly (◠‿◠)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 or you too(◠‿◠)
•  » » » 2 months ago, # ^ |   0 or God Um_nik!
•  » » 2 months ago, # ^ | ← Rev. 2 →   +19 NOoBODy thinking about maroonrk or Radewoosh
•  » » 2 months ago, # ^ |   0 the prizes are incredible!
•  » » 2 months ago, # ^ |   +3 Again 500 Euros to tourist.
•  » » 2 months ago, # ^ | ← Rev. 2 →   -7 How can you say before the contest? Anybody can win it.
•  » » 2 months ago, # ^ |   -7 Or ko_osaga ._.
 » 2 months ago, # |   +11 omg recruitment round
•  » » 2 months ago, # ^ |   0 omg recruitment round
 » 2 months ago, # |   +74 One more NP task with 74TrAkToR ?))
 » 2 months ago, # |   +15 Wow! 9 problems with 0 subtasks
 » 2 months ago, # |   -22 500 euros? yall are broke :clown:
 » 2 months ago, # |   -74 E code directly available in internet . Contest should be unrated. https://www.geeksforgeeks.org/equal-sum-xor/
•  » » 2 months ago, # ^ |   +115 Are you from future?
•  » » » 2 months ago, # ^ |   +1 they have a vision of the future
•  » » » 2 months ago, # ^ |   0 maybe
•  » » 2 months ago, # ^ |   -48 Problem F is also somewhat copied from Xenia and Tree, you can ask query 2 v just after querying 1 v.
•  » » 2 months ago, # ^ |   +3 How did you get to E as a specialist? I only solved ABC
•  » » » 2 months ago, # ^ |   +11 He is referring to this Div3 contest held yesterday https://codeforces.com/contest/1790
 » 2 months ago, # |   +30 As a tester, I think rsj has a really cool profile picture!
•  » » 2 months ago, # ^ |   +8 As a not-participant (USACO :clown:) I thought you wrote this round before this comment and changed handle for new years.
 » 2 months ago, # | ← Rev. 11 →   +4 Prizes ,goodies, direct interview chances :),tourist vs benq :),3 hours to solve that amazing for everyone to put extra efforts.everyone is excited imo.
•  » » 2 months ago, # ^ |   0 Of course it's with a prize t-shirt and stickers, 100, 250, 500 Euros
 » 2 months ago, # |   +5 Congratulations Tourist for winning yet another 500 euros in cf rounds.
•  » » 2 months ago, # ^ |   +3 How can you say before the contest?anybody can win it.
•  » » » 2 months ago, # ^ |   -25 Are you new to codeforces ?? Because everyone knows who has undefeated legacy this whole time. It's The Tourist. 
•  » » » » 2 months ago, # ^ |   +36 undefeated legacy indeed...
•  » » » » 2 months ago, # ^ |   +19 Don't you physically cringe at yourself when you sit down and type stuff like this?
 » 2 months ago, # |   0 E_huan orz
 » 2 months ago, # |   0 I can only solve 1-2 problems in div 2.. Can anyone give me some advice to improve myself... please
• »
»
2 months ago, # ^ |
+22

Yeah Sure i will give you 7 most useful tips

# 7 Practice

If you follow these religiously then Boooomm you are performing well xD

 » 2 months ago, # |   -13 Knock-knock!Who?Knapsack.
•  » » 2 months ago, # ^ |   0 Knock-knock!Who?DP!
•  » » » 2 months ago, # ^ |   0 Haha.
 » 2 months ago, # |   0 Actually I am Enthusiastic for this round hope the best for everyone :D
 » 2 months ago, # |   0 it will be going between tourist VS Benq
 » 2 months ago, # | ← Rev. 2 →   +10 Ez 500 Bucks for meInteresting clash for 2nd place awaits between tourist and Benq ;)
•  » » 2 months ago, # ^ |   0 whoever gets 500 euros is lucky
 » 2 months ago, # |   0 Being awarded gives coders motivation .Hope we will enjoy it)
 » 2 months ago, # |   -56 omg unrated round!!!
•  » » 2 months ago, # ^ |   +5 Rated
•  » » » 2 months ago, # ^ |   -14 nooooo, it's unrated round
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   0 Ok. Provide evidence for your opinion
 » 2 months ago, # |   -68 I anticipate that this will be a trash chinese round.
 » 2 months ago, # | ← Rev. 2 →   +8 OMG China round. Hopefully I'll gain back my color.
 » 2 months ago, # |   +6 Score distribution looks scary
 » 2 months ago, # |   +7 I hope this is not a typical Chinese mathforces round ...
•  » » 2 months ago, # ^ |   +14 Mathematics is the queen of the sciences.
•  » » 2 months ago, # ^ |   +13 Mathspeedforces,GOD!
 » 2 months ago, # |   0 Eye charming score distribution for problems: A, B, C; I think it would be tough for <1200 to score "C".
•  » » 2 months ago, # ^ |   0 it should be tough for 1200 to solve C anyways..
 » 2 months ago, # |   +28 IsaacMoris wants to participate can you delay the round 15 minutes
 » 2 months ago, # |   +5 Hoping I can solve the preblom C. cheers! :D
 » 2 months ago, # |   +2 My Prediction: The round will be pretty hard.I will just look the standing. Competition between GODs _/_.
 » 2 months ago, # | ← Rev. 2 →   -6 How bad will this affect for participants from division 3, 4?
 » 2 months ago, # |   -32 lmao it's completely a Mathforces Round.
 » 2 months ago, # |   0 OMG，Math Round! I can't do it at all.Go to bed. Good night...qwq
 » 2 months ago, # |   +5 Math contest is the most boring contest.
 » 2 months ago, # |   +2 Classic chinese round making me realise how bad I'm at maths xD
 » 2 months ago, # |   +2 Math forces
 » 2 months ago, # | ← Rev. 2 →   -38 Solved A in 10 minutes but I will submit after the contest to preserve my rating... The round is very hard.
•  » » 2 months ago, # ^ |   -34 Possibly a great decision
 » 2 months ago, # |   +33 problem B and C are horrible imo, very annoying
•  » » 2 months ago, # ^ |   -28 nah B was fine. Even C is nice once you figure out the actual observation needed. Rest is standard stuff you know what i mean (Can't tell contest is still ongoing.).
•  » » » 2 months ago, # ^ |   -9 Math_is_NOT_Good
 » 2 months ago, # |   +5 How can someone do problem H in 14 minutes.
•  » » 2 months ago, # ^ |   0 It's totally possible. They have must seen this concept or similar problem before and now just copy pasted some template from previous og chinese round.It's quite common . The other day i saw someone solved div2 E in 5 min.
 » 2 months ago, # | ← Rev. 2 →   0 How did they solve A in 1 minutes? At least, you need time to think, and then to code, right? Unless they have seen similar problems before...
•  » » 2 months ago, # ^ |   -21 They are quite fast at both typing and thinking.While typing i guess they were thinking too. The prefect combo makes them do everything within 1min.
•  » » 2 months ago, # ^ |   0 arpandesai0 sir tell us
 » 2 months ago, # |   0 Confuse about Problem B's time limit. There is no guaranteed statement.
 » 2 months ago, # |   -21 LMAO Classic MathforcesDisappointing contest
•  » » 2 months ago, # ^ |   +2 Pairforces indeed.
•  » » » 2 months ago, # ^ |   -8 more like Painforces (T＿T)
•  » » 2 months ago, # ^ |   +19 What is wrong with a contest which is "math-y"? You still need to use your brain to solve the problems
•  » » » 2 months ago, # ^ | ← Rev. 2 →   -14 It doesnt feels good to me to solve these problems which doesnt include DSA
•  » » » 2 months ago, # ^ |   -10 Such people don't like to actually solve problems, they like to copypaste/sligthly modify standard DSA to get AC.
•  » » 2 months ago, # ^ |   0 I love Maths. Because (my_username).
 » 2 months ago, # |   +2 Watching the GODS chasing is interesting!
 » 2 months ago, # |   +16 Scractched my head over C for 2 hours and still at 0.I hope C is a 1800+ problem
•  » » 2 months ago, # ^ |   0 Same man
•  » » 2 months ago, # ^ |   -11 Come one you can do it. I am the same colour you are.It's atmost 1700.
•  » » » 2 months ago, # ^ |   0 I'll try just one more time... Wish me luck.
•  » » » » 2 months ago, # ^ |   0 Wish you luck.
•  » » » » » 2 months ago, # ^ |   0 I failed man!
•  » » » » » » 2 months ago, # ^ |   +2 No problem. You never fail. Either you win or you learn.
 » 2 months ago, # |   +219 Use this comment as dislike for problem C. What a mess...
•  » » 2 months ago, # ^ |   -45 Was it really bad ?? I am the only one enjoying it ??
•  » » » 2 months ago, # ^ |   +23 The solution Idea was good, but it could have been framed in a much better way
•  » » » » 2 months ago, # ^ |   0 Are you going to upload solution video ?If no, then please atleast upload for C. It was one hell of a problem..
•  » » » 2 months ago, # ^ |   -8 YES.
 » 2 months ago, # | ← Rev. 2 →   +40 Quite bad experience. After wasting 2 hours I still have no idea about problem C, even some useful observations...
•  » » 2 months ago, # ^ |   0 Same. However, I skipped C and solved D. Not too bad for me.
•  » » 2 months ago, # ^ |   +37 SpoilerYou can see that for every $i$, either $x_i$ is minimum possible and $y_i$ is maximum possible or vice versa. And now you can dynamically program the solution.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 Wait! Wouldn't greedy work, i.e if $x_i$ is minimum and $y_i$ is maximum till some point $k$, and from $k+1$, $x_{i+1}$ is maximum and $y_{i+1}$ is minimum. And the answer is minimum of all $k$ s.t $0<= k < n-1$?
•  » » » » 2 months ago, # ^ |   0 Opps! got it, they need not to be in that order, $x_i$ can take any of the extreme value and $y_i$ would take the other.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +12 Is there a proof of this?I wasted a lot of time on C and finally decided to guess this conclusion.upd: I can prove this now, just focus on $x_i,y_i$ and consider other unknowns as constants.
•  » » » » 2 months ago, # ^ |   +16 I calculated $\frac{\partial F}{\partial x_i} = a_{i - 1} - x_{i + 1}$, so that it is always optimal to select the upper or lower bound.
•  » » » » 2 months ago, # ^ |   +2 When $y_{i-1}$ and $x_{i+1}$ are fixed, we can see that if $y_{i-1}$ is smaller than $x_{i+1}$,$x_i$ should be maximum to lower the answer，vice versa.So we can determine $x_i$ and $y_i$ (one of them must be maximum)
 » 2 months ago, # |   0 Another Great Rated round! ^_^
 » 2 months ago, # |   0 Math round destroyed me. I was only able to get up to problem B and complete it with 3 mins left :(
•  » » 2 months ago, # ^ |   -7 yea, i agree too many math
•  » » » 2 months ago, # ^ |   0 is B supposed to factorize prime?
•  » » » » 2 months ago, # ^ |   0 yes
 » 2 months ago, # |   0 tourist will not able to sleep tonight.
•  » » 2 months ago, # ^ |   0 lol truee he'll upsolve second last problem
 » 2 months ago, # | ← Rev. 7 →   -57 lets me guess what would problem set looks like ? one Arabic question, one prune forces question, one brutally brute force question ?, one minimum of maximum of minimum of maximum of minimum of something , one reverse of reverse of reverse of reverse of something And then contest ends Winner Board Tourist,Benq Why even announce prize money lol ? Directly give to them All GM's come and say problem set is awesome After reading this comment people you are newbie you dont understand My contribution -Infinity and I don't give a damn about it 
•  » » 2 months ago, # ^ |   +66 Oh fuck, not again...
 » 2 months ago, # |   +50 Worst C problem I have ever seen
•  » » 2 months ago, # ^ |   +6 how to solve c?
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 I did it with prime factorizationupdate: sry mistake prblem B, not that
•  » » » 2 months ago, # ^ |   +8 HintDynamic Programming
 » 2 months ago, # |   0 how to solve D?
•  » » 2 months ago, # ^ |   0 Cyclic counting (Brent's algorithm)
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 SpoilerLet $s_x$ be the number of nodes that can reach $x$ (including $x$) and $c$ be the number of nodes that doesn't end up in a cycle. Iterate through graph starting from node 1. Let $i$ be the current node. If node $i$ ends in cycle, then $a_i$ can take $c + n + 1$ values. Else, $a_i$ can take $c - s_i + n + 1$ values. Finally if path starting from $0$ doesn't end up in cycle then all the nodes that are not reachable from $0$ can take $(2*n+1)$ values.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 solutionYou have a functional graph, and for each vertex v you want to ask for a number of vertices u, that if can connectu with v, the vertex 1 will not be on cycle. You can compute by dfs which vertices are not on any cycle, and just connect all vertices on path from '1' to those. However, there are some edgecases i.e. you can't connect a vertex that is on path from '1', to another vertex that was before on path from '1', or vertex that leads to a vertex that was before on path, or you can't connect a vertex to itself, or you can't connect a vertex that is. But the main idea is just counting vertices that are not on any cycle.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +4 i did exactly the same but my code isn't working.. I feel like i've done everything right in my solution But still thank you
 » 2 months ago, # |   +46 It is so annoying that F asks for initial permutation rather than the minimal value :(
•  » » 2 months ago, # ^ | ← Rev. 2 →   +3 If it asks for the minimal value, it would be easier than C (just in my opinion)
 » 2 months ago, # | ← Rev. 2 →   +15 Any idea for C? It's always better to let the difference of xi and yi be greater, but I didn't come up with how to determine whether we let xi be the larger or the smaller one.Update: Now I've come up the idea (right after the contest ends) (see comments below).
•  » » 2 months ago, # ^ |   +32 dynamic programming !
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 Is it's something like this: first let all of xi be the smaller value, and let dp[i][flag]= the minimum result we can get if we don't flip xj,yj for j>i, where flag= (whether we've fliped x_j-1,y_j-1)?
•  » » » » 2 months ago, # ^ |   0 Exactly. now to update dp[i][flag] it is really easy to update it from dp[i-1][flag] and dp[i-1][flag ^ 1]
•  » » » » » 2 months ago, # ^ |   0 basically just check if the previous one is flipped or not
•  » » » » » » 2 months ago, # ^ |   0 OHHH it so easy that I've not some up with it for half an hour
•  » » » » » » » 2 months ago, # ^ |   +8 i feel u ! i was soooo frustrated with D that it took me a while too. I almost lost my mind on D coz of the numerous bugs my initial solution had
•  » » » » 2 months ago, # ^ |   0 use dp you have x+y=a[i] and (x-s)*(y-s)>=0 so if a[i]>s then it's better to choose x=s and y=a[i]-s(or vice versa). or if a[i]
•  » » 2 months ago, # ^ |   0 Theme: Dynamic programming
•  » » 2 months ago, # ^ | ← Rev. 2 →   +14 Probably, it is possible to use dp, but I came to it after finishing of contest.Note, that there is a countertest for "prefix is max/min and suffix is min/max": 1 10 3 6 7 10 4 3 2 9 5 1 8 Upd. answer is 52
•  » » 2 months ago, # ^ |   0 DP will do the job.
•  » » 2 months ago, # ^ |   +5 You can use DP to determine it. Let $dp_{i, 0}$ be the answer if we put $min$ first and then $max$ and $dp_{i, 1}$ be the answer if we put $max$ first and then $min$. Transitions are simple but hard to write. The answer is $min(dp_{i, 0}, dp_{i, 1})$.
•  » » » 2 months ago, # ^ |   +2 I've not come up with this idea and tried for some wrong approaches for half an hour... and I gave up and solved D instead
 » 2 months ago, # | ← Rev. 2 →   0 what is the actual sol to C? i tried to partition every number into s and the number minus s, but second test case in the example is a thing which i didn't see
•  » » 2 months ago, # ^ |   0 if ai >= s: (ai-s, s), else (0, ai), but I couldn't figure out which is x and y.
•  » » » 2 months ago, # ^ |   0 yeah i forgot to mention that i already did that for ai < s, but i think i have the wrong sol, since everybody said that it's dp, but idk how to implement it ;-;
 » 2 months ago, # |   -40 Horrible problemset, wacky unclear statements
 » 2 months ago, # |   +3 Hint for C please!
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 Dynamic Programming and Math Spoilerll minA(vector> & dp, vector &x, vector & y, ll prev, ll i, ll last, ll j) { if(i == x.size() - 1) return last * prev; if(dp[i][j] != -1) return dp[i][j]; ll v1 = x[i] * prev + minA(dp, x, y, y[i], i + 1, last, 1); ll v2 = y[i] * prev + minA(dp, x, y, x[i], i + 1, last, 0); return dp[i][j] = min(v1, v2); } void solve() { ll n, s; cin >> n >> s; vector v(n); for(ll i = 0; i < n; i ++) { cin >> v[i]; } vector x(n), y(n); for(ll i = 1; i < n - 1; i ++) { if(v[i] < s) { x[i] = 0; y[i] = v[i]; } else { x[i] = s; y[i] = v[i] - s; } } vector> dp(n, vector(2, -1)); cout << minA(dp, x, y, v[0], 1LL, v[n - 1], 0LL) << endl; } 
•  » » 2 months ago, # ^ |   0 Dynamic Programming...
•  » » 2 months ago, # ^ |   0 It's dp after including possible choices. 0, s, a[i] — s, a[i]
 » 2 months ago, # | ← Rev. 2 →   +22 I is the same as https://ac.nowcoder.com/acm/contest/9328/B
•  » » 2 months ago, # ^ |   +5 Is there a way to solve it using some sets and priority queues? I was unable to do so and used bst.
•  » » » 2 months ago, # ^ |   +1 Kind of, you can implement a simple segment tree. Check my comments below.
 » 2 months ago, # | ← Rev. 2 →   +101 I can be reduced to this problem.H can be reduced to this problem. This was in New Year Prime Contest, I guess 2017. There is a good solution using kinetic segment tree. You can find my article (Korean) here.Anyway I enjoyed the ratings problems, thanks!
•  » » 2 months ago, # ^ |   0 Wow, I actually remember this problem from polish competition (but didn't realize it during the contest ;_;) and almost all solutions (including model one) used bst.
•  » » 2 months ago, # ^ |   0
 » 2 months ago, # |   0 This youtube channel upload vedio on problem A & B solution at contest time.. report this channel..
•  » » 2 months ago, # ^ |   +12 how did you know?????
•  » » » 2 months ago, # ^ |   +1 First of all I didn't participate the contest...After the end of the contest I was searching for solution of problem C..And Youtube suggest(As you know) some of the related vedios...after clicking the vedio I saw the uploading time was in the middle of the contest .. Note: You can Check
 » 2 months ago, # |   +10 Unlock the submissions.
 » 2 months ago, # |   +50 The implementation of F is so tough that I cannot finish F during the contest. Is there lighter way?C and E are awesome, but D feels just heavy for me.
•  » » 2 months ago, # ^ |   0 For F, I was considering cases, and for one of the cases I had to find x such that , (2^k — 1) % x == (x-1). And then I had to minimize number of xs. Did you have this case as well ? How to minimize number of xs ?
 » 2 months ago, # | ← Rev. 2 →   +42 A=B
•  » » 2 months ago, # ^ |   +8 E hint pls
•  » » » 2 months ago, # ^ | ← Rev. 3 →   -8 hintm-1(or m-2) pairs
•  » » » 2 months ago, # ^ |   +5 SpoilerLeave all the pairs with xor value $x$. What can you do with the remaining numbers?
•  » » » » 2 months ago, # ^ | ← Rev. 5 →   0 Spoiler...their xor will be (xor of [1..n]) ^ (0 if no pairs is even else x) Aha! Gut problem
•  » » 2 months ago, # ^ |   0 I think D is the easiest, while C and E are both hard for me :(
•  » » 2 months ago, # ^ |   0 Actually, C is quite easy to find the key observation if you have some Math skills, while D is easy but hard to implement.It seems easy to solve E, but I have some problem with the proof. Can anyone prove the strategy in E?
•  » » » 2 months ago, # ^ |   +8 Consider sequence of p-th bits of numbers 1...n, where p is position of most significant bit in x. It is basically something like that : 00001111000011.. For each subsequence that you create you need to take at least one number with "1" lit in p-th position. So this is upper bound for number of groups and at the same time you can achieve it — you can match together consecutive blocks of zeros and ones (so the sequence above you split to [00001111] + [000011] to obtain 4 + 2 = 6 subsequences and this is maximum (I find it a little bit hard to write more formally but you should see that works).
 » 2 months ago, # |   0 Enter contest. Solve A,B,C . watch last 1 hour top standings page, well it got intense in last 15mins ...
 » 2 months ago, # |   +93 Welp, once again I'm obliterated by single observation/guessing problems (C and E) :(Very frustrating.
 » 2 months ago, # |   0 how to solve B?
 » 2 months ago, # |   -32 One day i will pass you tourist
 » 2 months ago, # |   +22 Anyone who is annoyed by C, join me and watch Errichto solve it live :)Errichto vs C hehe
•  » » 2 months ago, # ^ |   0 after 5 minutes ;-;
 » 2 months ago, # |   0 Direct solutions are available on youtube and ideone. I hope to see restrictions on judging and this kind of malpractice. [C solution on Youtube]: https://www.youtube.com/watch?v=4sVV35vlBQQ I have found most of the solution ideas are from the above source.
•  » » 2 months ago, # ^ |   +1 Imagine spending 2.5 hrs on a question trying your best and failing to solve it and then some "pro" person uploads the solution on youtube...
 » 2 months ago, # | ← Rev. 2 →   +5 I think C can be solved using DP because whenever we partition ith number into smaller one then we can only take all the possibilities at i+1 number and we will take minimum of all possibilities of i+1th because we want minimum.
 » 2 months ago, # |   +21 Immediate thoughts on the problems after the contest: A: Pretty fair starting problem. Ended up over complicating my solution for a while until I remembered what 1 to the exponent anything is. B: sieve of erathosenses being here intrigues me since it feels like this would be more common in C problems, but it's a pretty basic use here and I actually liked this problem, also since it had some implementation challenge without being too tedious. C: Probably inted the whole contest because I could not spot what the idea behind the solution is here, thus I can't really judge this problem too accurately. I will say that the fact this felt more difficult than it normally would be compared to B means that the point scaling for the earlier questions (500-1000-1750-2000) feels accurate. D: Graph based problem that don't explicitly state graphs in the problem. I liked this problem; felt around appropriate difficulty and its solution imo is pretty elegant. It did feel implementation heavy but this is more likely because I was running short on time and just went full spaghetti mode. Everything else: ran out of time after solving D, didn't have time to look at tl;dr contest is good, diff spike from B to C is reflected in scoring, I personally liked D the most. A fitting meme for me after I inted this contest:
 » 2 months ago, # |   0 Problem C seemed more difficult to me. But the issue is very well structured
 » 2 months ago, # |   +3 Why can't I look at someone else's code yet?
 » 2 months ago, # |   +3 i thought E was cool even though it was guessable
 » 2 months ago, # |   0 Problem D was nice.
 » 2 months ago, # |   +4 Going to be CM!:)
•  » » 2 months ago, # ^ | ← Rev. 2 →   +20 As someone who has also had 1899 long time before i've reached CM, I congratulate you from the bottom of my heart ^_^, you've probably felt quite a lot of pain before becoming CM, and now you will finally be able to enjoy it!! wish you all the best
•  » » » 2 months ago, # ^ |   0 Thank you! And hope you to be M soon :)
•  » » » » 2 months ago, # ^ |   0 Thanks, same to you! :)
 » 2 months ago, # |   +5 For problem C, why is it optimal to always choose the values of $x_i$ and $y_i$ so that they have the maximum difference?
•  » » 2 months ago, # ^ |   +1 assume $x_{i} \le y_{i}$, therefore it must be $\dots y_{i-1})(x_{i},y_{i})(x_{i+1} \dots$ and $y_{i-1} \ge x_{i+1}$. Therefore, if $x_{i}$ decrease and $y_{i}$ increase, the answer will be smaller.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Suppose that you have an optimal solution. Let's say that in the final sum $x_i$ is mulitplied by some $a$ and $y_i$ is multiplied by some $b$.Suppose $a •  » » 2 months ago, # ^ | +5 if y[i-1]=x[i+1], the values of x[i] and y[i] don't matter, so we can assume they have the maximun difference (which will not let the answer become worse), and if not, WLOG assume y[i-1]>x[i+1], if abs(x[i]-y[i]) is not the maximum, we can do x[i]--, y[i]++ to get a better answer. •  » » » 2 months ago, # ^ | +5 Thanks!I actually noticed that for$n=3$and the intuition from there seems so simple now. But instead of getting to the final observation I filled pages with useless stuff haha.  » 2 months ago, # | 0 the system test has finished, but my solution on C did not judge, what happened?  » 2 months ago, # | ← Rev. 2 → +23 system test has finished, but I can't submit why?  » 2 months ago, # | +80 I believe the initial statement of problem C was incorrect as usual mathematical notations, and I cannot believe that many people could read it (super brilliant people would guess it from the title so I can believe there exist such people, but...). So I felt this contest was unfair, sad.  » 2 months ago, # | +58 I dislike A to F. They are all boring guessing or implementation problems. All of them have quite obvious solutions.Problem G is really great. I gain lots of rating thanks to this problem :D  » 2 months ago, # | ← Rev. 2 → +21 Radewoosh E failed system testing. Unlucko  » 2 months ago, # | +23 tourist back on top  » 2 months ago, # | -85 lets me guess what would problem set looks like ? one Arabic question, one prune forces question, one brutally brute force question ?, one minimum of maximum of minimum of maximum of minimum of something , one reverse of reverse of reverse of reverse of something And then contest endsWinner Board Tourist,BenqWhy even announce prize money lol ? Directly give to them All GM's come and say problem set is awesome After reading this comment people you are newbie you dont understand My contribution -Infinity and I don't give a damn about it  » 2 months ago, # | ← Rev. 5 → +54 The problem F is a typical problem with easy idea and painful implementation. If we only need to find the minimal value it would be like about div2D.It's obvious that the target function (sum(1/f(i))) is the number of cycles in a permutation, and on each day, an even cycle is decomposited into 2 cycles with half size, and an odd cycle is changed order (but size remain the same). Thus if there's some even cycles with size n on the last day, there must be a cycle with size 2^k*n initially, therefore if the count of n-size cycle <2^k, there's no solution. If there's any solution, we need to merge 2^j cycles with same size (for even cycles j=k, and for odd cycles j=the maximum value that j<=k and 2^j<=count of cycles with same size) into one cycle, and before merging, we need to backstep these cycles to the day their size became odd (by raising them to the mod power of k-j).Update: Now my submission:191169251 has got AC. I can't remember how many times I've fixed a solution right after the contest ends, which didn't get AC in contest since some minor bugs.Implementation notes: The 2 major tasks for F are "merge 2^j cycles into one" and "backstep an odd cycle to k-j days before". For the first task, we can write the cycles by rows and read them by columns, like this:cycle #1: 1->2->3 (->1)cycle #2: 4->5->6 (->4)cycle #3: 7->8->9 (->7)cycle #4: 10->11->12 (->10)cycle merged: 1->4->7->10->2->5->8->11->3->6->9->12 (->1)This cycle will be decomposited into cycle #1, #2, #3, #4 in 2 days. And for the second task, let the size of cycle be n, if we backstep it by one day, it will become the (n+1)/2-th power of itself, where (n+1)/2 is the inverse of 2 modulo n. So we can backstep each cycle by (k-j) days using fast power.  » 2 months ago, # | 0 Can someone verify my logic? Thanks in advanceProblem CConsidering x[i] > y[i](x[i] < y[i] can be done symmetrically),for every i from 2 to n-1(1 based indexing), we must pick the maximum x[i] and the respective y[i]Proof Let in the optimal answer we multiply x[i] with p and y[i] with q with cost x[i]*p + y[i]*qLet p <= q(p > q can be done symmetrically)Now, if we don't multiply the max possible x[i] with p then their exists an answer where cost will be (x[i]+1)*p + (y[i]-1)*q => x[i]*p + y[i]*q + p — q. But since p <= q, this scenario will give a lower or same answerSo we just need to work on extreme values with 4 cases which can be done with DPIs this correct?  » 2 months ago, # | 0 there are some bugs with system testing hope you fix them  » 2 months ago, # | 0 I solved problem A but I cannot prove why there is no solution when$n$is odd, what is the proof of that? •  » » 2 months ago, # ^ | 0 Let's say any of x,y is even then y*x^y+x*y^x is also even, and if both are odd then also it's even so whatever you choose x,y the parity of y*x^y+x*y^x is even. •  » » 2 months ago, # ^ | +23 Since$x$and$y$are positive integers,$x^y$has the same parity as$x$, so$x^y \cdot y + x \cdot y^x$has the same parity as$2 \cdot x \cdot y$, which is always even. •  » » » 2 months ago, # ^ | 0 well the logic seems quite easy now , but at the time of the contest it was very hard to decipher , had to guess it . •  » » » » 2 months ago, # ^ | 0 Or you could alternatively check for all possible values of (x % 2, y % 2) •  » » 2 months ago, # ^ | 0 To get an odd$n$such that$a+b = n$either$a$is even and$b$is odd, or$a$is odd and$b$is even.So, with$x^y \cdot y + y^x \cdot x = n$with$n$being odd, either$x^y \cdot y$or$y^x \cdot x$have to be even, and if either of them is even, that means that either$x$or$y$are even, and if that's the case,$x^y \cdot y$and$y^x \cdot x$would both be even. So it's impossible for one of them to be even and the other to be odd at the same time.  » 2 months ago, # | 0 When can we submit and upsolve problems, like I am unable to submit even after system testing. •  » » 2 months ago, # ^ | ← Rev. 2 → 0  » 2 months ago, # | ← Rev. 4 → +61 Awesome contest! Can't say anything about A, common problem. Greedy in B, I didn't prove, judged by the fact it's B that there wouldn't be any difficult idea. I didn't like it though. Very interesting problem. The first thought when I read it was "It is real garbage, I need to guess somehow$x_i$and$y_i$and print the answer". I thought about it a little and went on. After solving other problems, I returned to it and suddenly understood that the idea is okish. I now have no idea why many (me too) disliked it too much. Seems like good C. Good (or average) problem, has an obvious solution (when you solve it on paper), but is difficult to implement, to gather the general thoughts. Handling cornercases and doing something similar to finding SCCs is a bit tricky, but I coped with it fast enough. I felt like E is too easy for its place. The idea (subsequences with length 1 or 2 are required) was probably good, but for some reason I didn't struggle with coming up with it and didn't get much excitement. Problem F was the most difficult one I solved during the contest. The idea is probably a bit straightforward, the problem requires some unwrapping (the part$\sum\limits_{i = 1}^{n}\frac{1}{f(i)}$was really fun). Maybe it's a bit technical, but I liked it. It was absolutely mindbreaking that G could be handled with centroids, but it seems it does. Then it's quite easy (not to implement though), but the idea was really unexpected. I feel like I fixed the last bug 1,5 minutes after the contest end :( UPD: Well, ok, it didn't work. Sad :( Didn't think much about H or I. Liked the H statement, though: it's very natural! Interestingly enough, it seems I like implementation problems more that the idea ones. Wouldn't say it if asked, though. Anyway, the contest was great. •  » » 2 months ago, # ^ | 0 How to solve G with centroids? •  » » » 2 months ago, # ^ | 0 It's nothing, just use the solution in the editorial and add centroids there) (Store paths not by lca of their ends, but by the lowest centroid of them and when updating a vertex, walk all the path-to-root in centroid decomposition,$O(n\log^2{n})\$).
•  » » » » 2 months ago, # ^ |   +11 Thank you for making me read the editorial, see that it made no sense only to then realize that I didn't read that a good path must have all edges of that color.
 » 2 months ago, # |   +8 191126284 is still in "Pretests passed" status, is there are something wrong of the judge system?
 » 2 months ago, # |   +1 i can not send a solution even though the contest is over rsj
 » 2 months ago, # |   -20 To hard Contest More Like Problem Based on Math's Concept
 » 2 months ago, # | ← Rev. 2 →   0 B has weak test cases. https://codeforces.com/contest/1787/submission/191170706Test Case:-14194304Should output 44. Outputs — 40.
•  » » 2 months ago, # ^ |   0 Ok
 » 2 months ago, # | ← Rev. 2 →   +208 Meh, with GNU C++20 (64), GNU C++17 (64) and GNU C++14 (so all other compilers) my solution gets RE on pretests, but with GNU C++17 (chosen by me during the contest) it somehow keeps working and passes (and UB shows up on systests).
•  » » 2 months ago, # ^ |   0 Unlucko
•  » » 2 months ago, # ^ | ← Rev. 2 →   +13 The most interesting is that you get Accepted on main tests when contest was running. You are so unluckily!I see your code. You got RE because you visit the wyn[0] when it is empty. It is UB. Notice std::vector::clear() do not free memory. So it will only get RE when it is the first case sometimes.So following codes can run successfully and print 2 0 (GNU G++14 6.4.0 on Custom invocation of CodeForces): #include using namespace std; int main(){ vector a; a.push_back(1); a.clear(); a[0]=2; printf("%d %d",a[0],a.size()); return 0; } I recommend to use vector().swap(a) to clear the vector a with freeing memory. However, it spends more time because it frees memory.
 » 2 months ago, # |   0 Lucky I reached blue even after being ranked 1800+
 » 2 months ago, # |   0 is this vaticle job remote or onsite.
 » 2 months ago, # |   0 what will be rating of D?
•  » » 2 months ago, # ^ |   0 0
 » 2 months ago, # |   +14 F is just stupid implementation.
 » 2 months ago, # |   +3 500 Euros to ko_osaga.
 » 2 months ago, # |   +3 When will the prize distribution for 51-250 places be published?
•  » » 2 months ago, # ^ |   +39 After I process cheaters. At most 1 day.
•  » » » 2 months ago, # ^ |   +12 its been 4 days dude
•  » » 7 weeks ago, # ^ |   0 So the rarings are back, when will we have prize distribution (for 51-250 places)?
 » 2 months ago, # |   -56 Hi I'm new you are all suckers
 » 2 months ago, # | ← Rev. 3 →   0 Good contest.
 » 2 months ago, # |   +5 I'm sorry
 » 2 months ago, # |   0 Thanks to the authors for balanced set of interesting problems and accurate score distribution! C is my favorite one, rare combination of greedy and DP concepts in the same problem, perfect mix for casework lovers!
•  » » 2 months ago, # ^ |   0 C was annoying af
•  » » » 2 months ago, # ^ |   0 Thinking in general is annoying but some people like it. That's the reason we have platforms like Codeforces.
 » 2 months ago, # | ← Rev. 2 →   +11 Hey, the system says my submission 191137200 matches 191132505 while that guy just used my template and nothing else. If you check the solution carefully, you'll see I wrote a 3*n state dp while that guy wrote 2*n state dp. There is no way we copied each other. How and where do I proved this? Infact, all my solutions from that round got skipped due to this. Please help me someone :'( MikeMirzayanov
•  » » 2 months ago, # ^ |   +2 Moreover, the ArPiT_ErrOr is a dummy/fake handle who has just solved 6 problems and all his submissions are after mine for this contest. As you can see I use the same template for every problem which can be seen from all my submissions. Also, that user has used different templates for different contests which clearly seems suspicious. Please look in this issue and every other issues like this in general MikeMirzayanov.
•  » » » 2 months ago, # ^ |   0 Totally agree with your points.
•  » » » 2 months ago, # ^ |   0 190535543 is one submission that I made before the contest. You can see I have been using the same template from quite a while.
•  » » 2 months ago, # ^ |   0 Agreed, MikeMirzayanov please fix this issue.
 » 2 months ago, # |   0 Why did this contest get unrated?
•  » » 2 months ago, # ^ |   +6 it is not unrated, it just rating roll backs for checking of cheating.
 » 2 months ago, # |   0 Has this round become unrated?? Ratings have not been updated yet. If yes then please also tell me the reason.
 » 2 months ago, # |   0 Hey, I participated in this contest and made 2 successful submissions. But it is not being shown on my contests list and my ratings didn't change after this. But it is showing my submissions.
 » 2 months ago, # |   +5 The ratings for this round were rolled back, but there is no yellow alert which used to be there. The round hasn't been declared unrated, has it?
•  » » 2 months ago, # ^ |   0 same question
 » 2 months ago, # |   +1 Is it rated?
•  » » 2 months ago, # ^ |   +8 Yes, after skipping the cheatersI'm waiting too
•  » » » 2 months ago, # ^ |   0 thx
 » 2 months ago, # |   0 Correct me if I am missing something. This round is yet to release its rating. The round followed by this one was a Div. 2 exclusively. Suppose someone rated <2100 attempts this round has reaches Div 1. category. As the rating were rolled back, they will have the chance to also compete in the Div 2. round followed by it. It might even be possible that they surpass this division again, but ideally, the round should have been unrated for them.Can someone please explain how a case like this is handled, or provide me a blog where this is already answered?
•  » » 2 months ago, # ^ |   0 This has happened in Round 829/830, except that was a kind of weird contest because 830 (for Div. 2 only) started only 15 minutes after 829 ended. The result that time is quite a few masters were rated in a contest meant for Div. 2. But I don't know if they're going to handle it the same for this.
•  » » » 2 months ago, # ^ |   0 Thanks a lot, this explains a possible solution.
 » 2 months ago, # |   0 why was my rating increased first, and then removed, and not only from me, but from everyone?
 » 2 months ago, # |   +3 Meanwhile, me waiting till eternity to see my updated rating lol :)
 » 2 months ago, # |   0 Why my rating of this contest is rolled back? :'''''( When will it come back? :''''(
 » 2 months ago, # |   +1 is the rating of this contest visible in your profile?
 » 2 months ago, # |   -10 Why is it unrated?
 » 2 months ago, # |   0 Something is going on?... Is it related to those strange submission timings of H from those high ranking contestants? According to editorial, H is a original problem, and the authors "Have to declare that we built up Problem H from zero. ;)"...... Well, I never identify high-rankers with high moral standards and I can take whatever would happend next...... (Hope it is just some tech issue, and I would keep my +22 delta ^_^)
•  » » 2 months ago, # ^ |   0 your picture looks familiar,I may have seen you on bilibili :)
 » 2 months ago, # |   +3 I just want my +63 :(
 » 2 months ago, # |   0 Why I am not rated for this round?
•  » » 7 weeks ago, # ^ |   0 All are rated for this contest but codeforces is busy to catch the cheaters.
»
7 weeks ago, # |
+40

Congratulations to the hoodie and t-shirt 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

### TypeDB hoodie, t-shirt and stickers

List place Contest Rank Name
1 1787 1 ko_osaga
2 1787 2 tourist
4 1787 4 Benq
5 1787 5 ecnerwala
6 1787 6 Um_nik
7 1787 7 Rebelz
8 1787 8 orzdevinwang
9 1787 9 zihouzhong
10 1787 10 feecle6418
11 1787 11 noimi
12 1787 12 IOMO
13 1787 13 ksun48
14 1787 14 ainta
15 1787 15 inaFSTream
16 1787 16 maroonrk
17 1787 17 jiangly
18 1787 18 WYZFL
19 1787 19 SSRS_
20 1787 20 Ormlis
21 1787 21 dl720125
22 1787 22 Golovanov399
23 1787 23 fsy_jiaxun_when
24 1787 24 ugly2333
25 1787 25 hank55663
26 1787 26 Xylenox
27 1787 27 emptyhope
28 1787 28 BurnedChicken
29 1787 29 hos.lyric
30 1787 30 Kubic
31 1787 31 Rubikun
32 1787 32 Vercingetorix
33 1787 33 tatyam
34 1787 34 yarik_mutltiacc
35 1787 35 PinkieRabbit
36 1787 36 blackbori
37 1787 37 Tlatoani
38 1787 38 Endagorion
39 1787 39 Allvik06
40 1787 40 Merkurev
41 1787 41 QAQAutoMaton
42 1787 42 NoPotato
43 1787 43 mango_lassi
44 1787 44 K-H
45 1787 45 oleh1421
46 1787 46 Mr_Solution
47 1787 47 244mhq
48 1787 48 Xellos
49 1787 49 nantf
50 1787 50 kotatsugame

### TypeDB t-shirt and stickers

List place Contest Rank Name
60 1787 60 A_G
61 1787 61 tute7627
63 1787 63 Pyqe
67 1787 67 Toxel
70 1787 70 alexxela12345
73 1787 73 A-SOUL_Bella
75 1787 75 Maksim1744
76 1787 76 huangzirui
77 1787 77 jdurie
85 1787 85 HollwoQ_Pelw
89 1787 89 satashun
91 1787 91 Nyaan
98 1787 98 KevinWan
100 1787 100 qiuzx
106 1787 106 Hyperbolic
107 1787 107 torisasami
108 1787 108 fireskydd
109 1787 109 -14
110 1787 110 KroosTheKeenGlint
125 1787 125 Fysty
131 1787 131 w.omais
132 1787 132 zsyzsy
133 1787 133 ai_dev_master
144 1787 144 Arraiter
157 1787 157 Sulfox
162 1787 162 olmrgcsi
165 1787 165 kshitij_sodani
173 1787 173 wyzwyz
178 1787 178 Kevin114514
183 1787 183 Gheal
184 1787 184 18Michael
187 1787 187 chen_zexing
190 1787 190 duality
193 1787 193 natofp
196 1787 196 LipArcanjo
199 1787 199 frokaikan
209 1787 209 Amanda_LWA
212 1787 212 CJ-zhuyifan
213 1787 213 DoorhandleMahoushoujo
214 1787 214 ComPhyPark
216 1787 216 eunlin
217 1787 217 Amtek
222 1787 222 HugeWide
229 1787 229 lilvan
233 1787 233 glebustim
238 1787 238 Alexdat2000
241 1787 241 pooty
245 1787 245 zqyyy
 » 7 weeks ago, # |   -10 Another 600 Euros to tourist.