### ch_egor's blog

By ch_egor, 20 months ago, translation,

Hi everybody,

This Sunday there will be a XVIII Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657).

The round will be held at Nov/01/2020 14:05 (Moscow time) and will last for 2 hours. Each division will have 5-6 problems. The round will be held according to the Codeforces rules and will be rated for both divisions.

Problems are prepared by vintage_Vlad_Makeev, NiceClock, ismagilov.code, vintage_Vlad_Makeev, KiKoS, wrg0ababd, ch_egor, Roms, voidmax, DebNatkh, Nebuchadnezzar, Endagorion, craborac, 300iq, cdkrot, LHiC, vintage_Vlad_Makeev, V--o_o--V, grphil under my supervision with great help of GlebsHP, meshanya, Endagorion, Zlobober and Helen Andreeva.

Thanks to adedalic and KAN for the round coordination and verifying statement of original olympiad, meshanya and cdkrot for statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1: Thanks to Um_nik, satashun, mraron, ustze, Karavaiev, KKiYeer for testing.

UPD2: Scoring distribution:

Div.1: 500 — 1000 — 1500 — 2000 — 3000

Div.2: 500 — 1000 — 1500 — 2000 — 2500

UPD3: Editorial

UPD4: Winners!

Div. 1:

Div. 2:

• +186

 » 20 months ago, # |   +101 Friendly time for Chinese again!
 » 20 months ago, # |   +93 Clashes with ABC 181 :(
 » 20 months ago, # | ← Rev. 2 →   +9 This round directly clashes with Atcoder Beginner's round 181 which starts after 1 hour of the start of this round. I request authors to please check once.
 » 20 months ago, # |   -36 Too early
•  » » 20 months ago, # ^ |   +90 This round is based on onsite olympiad and they can't change time of start.
 » 20 months ago, # |   +56 It's gonna be another Div.1.5-like Div.2 contest, and Div-0.5 like Div.1 contest
 » 20 months ago, # |   +67 Most div1 people complain because there are few div1 rounds. Maybe proposing more rounds based on Olympiads can be an improvement. There are a lot of rounds based on Russian Olympiads, so I think that it can be extended to other nations.
•  » » 20 months ago, # ^ |   +7 Do you really think this is few?
•  » » » 20 months ago, # ^ |   +77 It's an exception to the rule. In the average graph of div1 people, the number of dots (contests) is significantly lower where the rating is $\geq 2100$.
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   -27 Why is it a 'rule'? It's just the result of 'Div.2 only' exist but 'Div.1 only' doesn't. And because creating good harder problems usually takes more time than creating good easier problems, it would be inevitable there are fewer Div.1. If I can choose more lower-quality Div.1 or less higher-quality Div.1, I will choose the latter.
•  » » » » » 20 months ago, # ^ |   +17 But Olympiads from countries other than Russia also contain good problems, so why there are only Russian Olympiads on codeforces?
•  » » » » » » 20 months ago, # ^ |   +23 That might be because codeforces is originally a Russian website, so the olympiad organisers may feel good if it is organised in a Russian platform too. Codeforces is growing as a more international platform, so we can see other countries' olympiads in the future maybe.
 » 20 months ago, # |   +10 where are testers ???
•  » » 20 months ago, # ^ |   +71 I think 20 authors is enough for testing
•  » » 20 months ago, # ^ | ← Rev. 2 →   +57 Well, I'm one of the testers of this round. Seems that they haven't put the testers in the announcement yet.Upd: It’s updated now.
•  » » » 20 months ago, # ^ |   +11 Yes, I will add all testers after testing is over
 » 20 months ago, # | ← Rev. 2 →   +40 The amount of red people in problemsetters scares me..
•  » » 20 months ago, # ^ |   +290 As a red, they scare me too.
•  » » » 20 months ago, # ^ |   +39 I was literally searching for your comments to upvote them xD.
•  » » » » 20 months ago, # ^ |   +26 Well you found them, Sherlock Holmes.
•  » » » » 20 months ago, # ^ |   +100 They still haven't added the tester list, so I suppose there's no one to stop me from claiming I'm a tester for contribution farming purposes.
•  » » » » » 20 months ago, # ^ |   +11 Here comes the post hijacker Monogon xD
•  » » » 20 months ago, # ^ |   0 Your this kind words motivate me
 » 20 months ago, # | ← Rev. 5 →   -63 Is it Rated?
•  » » 20 months ago, # ^ |   +1 Yes
•  » » 20 months ago, # ^ |   0 when I ask this question , this answer not mentioned in blog.
•  » » » 20 months ago, # ^ |   +3 When it is mentioned that it is a div2 / div1 round its anyways rated. It would be specified if it is some external contest. :)
 » 20 months ago, # | ← Rev. 2 →   +59 There’re only 32 Legendary Grandmasters at all, and 4 of them took part in preparing the problems!
•  » » 20 months ago, # ^ |   +63 That's the number of LGMs who competed in the last 6 months. There are inactive LGMs too.
•  » » » 20 months ago, # ^ | ← Rev. 2 →   +8 Yes, you are right, but then what is rating(all)?
•  » » » » 20 months ago, # ^ |   +43 Rating (all) lists all users, but it lists all the active users before all the inactive users.
•  » » » » » 20 months ago, # ^ |   +34 Thanks a bunch, but this doesn't change how cool people were involved)
•  » » 20 months ago, # ^ |   +30 actually 5 LGM's were involved(Um_nik as a tester)someone tell Codeforces Halloween was yesterday!!:|I don't know about you people but actually I prefer contests with harder problems because speed matters less :)
 » 20 months ago, # |   -13 Will the round be rated? Also will it be codeforces rules or something like ACM ICPC?
•  » » 20 months ago, # ^ |   0 It is mentioned in the post that It is rated
•  » » » 20 months ago, # ^ |   +38 Clarifications to both my questions were added in bold after I posted my comment
 » 20 months ago, # |   -49 moscow team olympiad aight imma skip this one
•  » » 20 months ago, # ^ |   -18 No-one Cares ! about your participation.
 » 20 months ago, # |   0 there is atcoder beginner contest 181. so, it is tough to attend 2 contest at a time
 » 20 months ago, # |   +47
•  » » 20 months ago, # ^ |   -7 Codeforces contest is more standard , imo . But i believe that atcoder contest time will be changed. ..
•  » » » 20 months ago, # ^ |   0 Yes, it would be good for everyone if they cooperate.
•  » » » 20 months ago, # ^ | ← Rev. 2 →   +8 [deleted]
•  » » » 20 months ago, # ^ |   +6 https://twitter.com/chokudai/status/1322557968651415553AtCoder's president said "We can't change the time of tomorrow's atcoder contest".
•  » » » » 20 months ago, # ^ |   0 And this makes me sad :(
•  » » » 20 months ago, # ^ | ← Rev. 2 →   0 Yes,both atcoder and codeforces will definitely see into it and change the timings to remove any possible overlaps.
 » 20 months ago, # |   +3 Note that the start time is unusual. :(
 » 20 months ago, # |   +82 Clashes with OpenCup :( (apparently)
•  » » 20 months ago, # ^ |   0 Fortunately managed to solve all my problems, including first solution to Geo3D, in 2:47 and left teammates with optimizing code to last one :D
 » 20 months ago, # |   +1 We will face one of the hardest contests. Let's see what happens.
 » 20 months ago, # |   +16 hopefully we will see score distribution before the contest..
 » 20 months ago, # |   +1 How will tie be resolved? Sorry I am new to cf so that's y asked
 » 20 months ago, # |   +5 How can 20 authors propose 10 problems? Isn't it like one problem is completely written by a single writer?
•  » » 20 months ago, # ^ |   +46 Seems like showing the name of movie makers before starting a horror movie!!
 » 20 months ago, # | ← Rev. 2 →   +40 For those in US, note the clock change. On Nov 1st at 2 a.m. most US states will fall back one hour to 1 a.m.Those who didn't know this happens... sounds stupid uh!? :)
•  » » 20 months ago, # ^ |   +18 Thank you, I did not notice this! It seems the time zone adjustment on Codeforces is different from the one if you click the link to timeanddate.com
•  » » 20 months ago, # ^ |   +8 Yeah, I was confused about this too.
•  » » 20 months ago, # ^ |   0 The daylight saving time
 » 20 months ago, # |   +5 Last time when I saw this many reds, I saw an accident.
 » 20 months ago, # |   0 Reminds me of Codeforces Round #659
 » 20 months ago, # |   +2 Can't we have rounds in codeforces based on other olympiads? This would increase the rate of contests for both divisions and you would not need that much of co-ordination cause these problems appeared in Olympiads so it must be good. We only see rounds based on Russian Olympiads in codeforces unfortunately.
 » 20 months ago, # |   +15 This competition is friendly for Chinese competitor!Thanks ch_egor
 » 20 months ago, # |   0 The amount of red people in problem setters scares me.
 » 20 months ago, # |   0 Why so many authors this time??
•  » » 20 months ago, # ^ |   0 do you have any problem??
 » 20 months ago, # |   +4 All the best for everyone who are giving the contest !!!
 » 20 months ago, # |   0 A huge number of setters.
 » 20 months ago, # | ← Rev. 2 →   0 .
 » 20 months ago, # |   0 Gap between D and E is huge.
•  » » 20 months ago, # ^ |   +28 I'd say the gap between C (your E) and D is the huge one.I think the gap always seems biggest near the limit of your abilities.
 » 20 months ago, # |   0 Am i the only newbie stuck in C??
 » 20 months ago, # |   0 Friendly time for Chinese again!
 » 20 months ago, # |   0 What is test case 2 of Div 2 C :(((
 » 20 months ago, # |   0 How do you do Div2E/Div1C? I think the problem reduces to "Find number of pairs of groups $G_1$ and $G_2$ such that $G_1 \cup G_2$ is bipartite", but I can't think of anything better than brute force.
•  » » 20 months ago, # ^ |   +23 There are only $O(m)$ pairs $(G_1, G_2)$ such that $G_1$ and $G_2$ are bipartite but $G_1 \cup G_2$ might not be.
•  » » » 20 months ago, # ^ |   0 Ohhhhh that's actually pretty obvious, thanks!
•  » » 20 months ago, # ^ |   0 Efficiently perform bipartite checks for each pair of groups that have an edge between them. You can look at the graph formed by edges within groups, find its components, throw away bipartite ones (along with whole groups), compress the 0/1 parts of remaining components into single vertices and on that graph, bipartite search takes O(number of edges between groups).
•  » » 20 months ago, # ^ |   +10 checking if a graph is bipartite with DSU + restorable DSUthe number of pairs you have to check is bounded by the number of edges, so for each pair, add in all of it's edges, check if it's bipartite, and then rollback.
•  » » 20 months ago, # ^ |   +20 You can check if a graph is bipartite using a modification of the union-find data structure: for each vertex, we keep a bit indicating whether it has the same color as its parent in the union-find data structure. When inserting an edge between $u$ and $v$, if $u$ is already in the same component as $v$, we check if they have the same color. Otherwise, we merge the components of $u$ of $v$.Then we can simply check whether a pair $(G_1, G_2)$ is good by inserting the edges between $G_1$ and $G_2$ in that data structure, and we do a rollback after each check.
 » 20 months ago, # |   +105 Please, why didn't you bold non-increasing and non-decreasing in D1B? Of course it's my fault, but I was solving wrong version for $40$ minutes.Also, it's duplicate of SRM 781 Med
•  » » 20 months ago, # ^ |   +18 Same here, but didn't see it till the very end :((
•  » » » 20 months ago, # ^ |   0 same here :((
•  » » » » 20 months ago, # ^ |   0 same here for 20 minutes. :(
•  » » 20 months ago, # ^ |   0 I count myself very lucky for spotting it.
•  » » 20 months ago, # ^ | ← Rev. 2 →   +35 I also misread the problem. I saw the sample test cases before solving the problem and couldn't understand why the answer is 12. After around 10 minutes, I finally realized that I misread the problem.
•  » » 20 months ago, # ^ |   +8 Similarly, please bold "teams may have different sizes" in C. I made a mistake at first, and then spent lots of time wondering if it is even possible to do knapsack this fast.
•  » » 20 months ago, # ^ |   +11 Same feelings.
•  » » 20 months ago, # ^ |   +8 Same here, take my upvote. Spent ~30 minutes trying to solve the wrong version until I tried to run the samples.
•  » » 20 months ago, # ^ |   +64 Nevermind. I FSTed it anyways!
•  » » » 20 months ago, # ^ | ← Rev. 2 →   -9 2 FST? I would have died if it happened to me.
•  » » 20 months ago, # ^ |   0 saw it right now, was solving the wrong version until the end :(
•  » » 20 months ago, # ^ |   0 Same here. BTW I thought the wrong version was a nice problem.
•  » » 20 months ago, # ^ |   +21 Same, but I reread the problem after my $N^2$ gave WA on the sample ...
•  » » 20 months ago, # ^ |   0 Same here :(. I think the answer in that case was related to Catalan numbers. Can someone verify?
•  » » 20 months ago, # ^ | ← Rev. 2 →   +18 Hello, I am here to complain about yet another problem statement again. After seeing editorial of Div1D, I was confused as to why $h=v$ was given, since drawing the following polyline works: $(0,1) -> (1,1) -> (1,-1) -> (-1,-1) -> (-1,1) -> (0,1)$. It isn't clarified in statement that they have to cyclically alternate, I think. Please, please, have more testers (who are perhaps non-native speakers) read and test the round so that such issues do not happen.
•  » » » 20 months ago, # ^ | ← Rev. 3 →   -18 I don't think that many people misunderstood the statement. Even if they had more testers, it's not certain that some of them would think that a closed alternating polyline may satisfy $h = v + 1$.
•  » » » » 20 months ago, # ^ |   0 I specifically asked for a clarification there because it's not given.
•  » » » » » 20 months ago, # ^ |   0 It seems I didn't express myself clearly. I tried to say the probability of misunderstanding is low to begin with. It's just my speculation, though.Closed polylines don't really have a beginning nor an end.
•  » » » » » » 20 months ago, # ^ |   0 The statement says "One drew a closed polyline...". What isn't clear to me is if the alternating was just for the drawing, or for the actual diagram. I didn't get to asking clarifications as I was too busy misreading C, and thought that this problem would be hard (based on what I thought the problem was — might need to handle annoying cases). Turns out it was very clean.
•  » » » » » » » 20 months ago, # ^ |   +8 Oh, I see. Yeah if you think that way it's quite possible to be confused.Probably it would have been better if they simply gave two equal length arrays (it could ruin your results in some unexpected ways even if you interpreted the statement correctly).
 » 20 months ago, # |   0 How to solve div2E, I am struck for 1 hour and haven't got a single hint
•  » » 20 months ago, # ^ |   -12 i mean you're not supposed to get hints during the contest...
•  » » » 20 months ago, # ^ | ← Rev. 2 →   0 Sorry, I haven't got your words. If I understand what you said, I commented after contest.
•  » » » » 20 months ago, # ^ |   0 ah mb, i thought you meant something different
•  » » » » » 20 months ago, # ^ |   0 Anyway, how to do this problem?
•  » » » » » » 20 months ago, # ^ |   +10
 » 20 months ago, # |   0 this is first time i have ever solved 4 questions in div2,just hoping not to fail system test
 » 20 months ago, # |   0 How to solve C? (ِDiv 2)
 » 20 months ago, # | ← Rev. 3 →   +10 In Div2D or Div1B , I was getting some double summation. For optimizing that i need to calculate summation of the form ${n\choose n-k}$ + ${n+1\choose n-k+1}$ + ${n+2\choose n-k+2}$ .... ${n+k\choose n}$ faster. Can some one tell O(1) formula for that (or some log(n) method will also work)
•  » » 20 months ago, # ^ |   0 Sort the array and then find the sum of the absolute difference of elements at index 0 and n,1 and n+1 and so on.... then simply multiply it by 2nCn.
•  » » » 20 months ago, # ^ | ← Rev. 2 →   0 Can you please elaborate the multiply it by 2nCn part ? I guess you are trying to pair up element $i$ with elements at indices greater than or equal to $i+n$ and multiplying difference by number of times they can occur in two sequences such that they face each other. My approach was similar .Edit : Got it by comments below .
 » 20 months ago, # |   0 How do you find two subsets of equal sum fast enough in D?I tried to do it with iterative NTTs, which should be $O(MN \log M \log N)$ (where $M = 1000$ is the maximum value) and then some loops to check which pair actually makes the target value, but this TLEd.
•  » » 20 months ago, # ^ |   +20 bitset works better than FFT :)
•  » » » 20 months ago, # ^ |   0 Yeah, bitsets indeed gave AC :(97358236
•  » » 20 months ago, # ^ |   0 If you just want to find two subsets of equal sum, can't you just do normal knapsack with bitsets? (in O(NW/32) ish time?)
•  » » » 20 months ago, # ^ |   0 Isn't that $O(N^2 W / 32)$?Too bad I didn't have time to try bitsets after getting TLE :(
•  » » 20 months ago, # ^ |   +10 Something like this: codebitset dp; bitset tmp; int pr[MAX_N * MAX_C / 4]; ... bool make_groups(int sz, int sm, int arr[], pair, vector>& ans) { assert(!(sm & 1)); int h_sm = (sm >> 1); assert(h_sm < (int)dp.size()); dp.reset(); dp[0] = true; for (int i = 0; i <= h_sm; ++i) { pr[i] = -1; } for (int i = 0; i < sz; ++i) { tmp = (dp | (dp << arr[i])); tmp ^= dp; for (int j = tmp._Find_first(); j < (int)tmp.size(); j = tmp._Find_next(j)) { pr[j] = i; } dp ^= tmp; } if (!dp[h_sm]) { return false; } memset(used, 0, sizeof(bool) * sz); ans.first.clear(); for (int i = h_sm; pr[i] != -1; i -= arr[pr[i]]) { used[pr[i]] = true; ans.first.push_back(arr[pr[i]]); } ans.second.clear(); for (int i = 0; i < sz; ++i) { if (!used[i]) { ans.second.push_back(arr[i]); } } return true; } 
•  » » 20 months ago, # ^ |   +10 I haven't got AC but I think this might work: you want to assign "+" and "-" to elements of the sets such that the set sums to 0. Shuffle the input and use a dp table $\mathrm{dp}[i][j]$ where $0 \le i \le n$ and $-B \le j \le B$ for sufficiently large $B$ (you can cut down a lot from $10^6$ here). Because the input is randomized, if there exists a solution there exists one where $j$ is not too large.
•  » » » 20 months ago, # ^ |   0 I tried just adding the "+" segments from the largest one and then subtracting the "-" segments from the largest (absolute) one, but got WA...
•  » » » 20 months ago, # ^ |   0 That won't work, what if we have $n-1$ copies of $1$ and one $n-1$. Then no matter the order we need $j$ at least $(n-1)/2$ or so.
•  » » » » 20 months ago, # ^ |   +30 Huh? $j$ being around $n$ is totally fine, the complexity here is $O(nB)$.
•  » » » » » 20 months ago, # ^ |   +10 Oh, right, of course. That should work.
 » 20 months ago, # |   0 how to solve div2C?
 » 20 months ago, # | ← Rev. 2 →   +32 Div2D/1B is same as the topcoder problem I set.Fun fact: You can perform a magic trick based on this problem in front of your friends too. :D
 » 20 months ago, # |   0 how to solve div2 C? O(n^1/2) is too slow...
•  » » 20 months ago, # ^ |   0 my solution passed pretests with $O(q^{1/2})$.
•  » » » 20 months ago, # ^ |   0 Yeah what was you solution?
•  » » » » 20 months ago, # ^ |   +5 The idea is that $ans$ will be largest divisor of $p$ for which the following holds: for at least one prime divisor $i$ of $q$, the exponent of $i$ in $ans$ will be less than that in $q$ (so that $q$ does not divide $ans$). My solution: link
•  » » » » » 20 months ago, # ^ |   0 Dude yes I just read the editorial as well. The problem was that even if I have thought of this solution I discarded it immediately because I was like "Oh the prime factorization of q will take a lot of time" and now I just realized that no! it would not since I have to find the primes up until the sqrt(q).. smh. I will never ever become a master unless I sit down and solve all math tagged problems until 2000 rank.
•  » » » » » 20 months ago, # ^ |   0 can you clarify what you mean by exponent of i?
•  » » » » » » 20 months ago, # ^ |   0 the power of a prime in prime-factorisation
 » 20 months ago, # | ← Rev. 2 →   +5 Problem B: Am I the only one who thought that both $p$ and $q$ are sorted in the same order for 30 minutes?EDIT: Just read https://codeforces.com/blog/entry/84198?#comment-717476. Seems like I am not the only one.
 » 20 months ago, # | ← Rev. 3 →   0 How the hell the answer to the example in D2E (D1C) is 3? 4 3 3 1 1 2 2 1 2 2 3 3 4 The number of possible combinations cnk(3, 2) = 3 and one combination is wrong, we cannot chose first and second group, because there is not way to split four students according to the rulesThe answer should 2Do I miss something?
•  » » 20 months ago, # ^ |   +3 We can choose the first and second group. Make groups ${1, 3}$ and ${2, 4}$.
•  » » » 20 months ago, # ^ |   0 Oh, crap. Thx
 » 20 months ago, # | ← Rev. 3 →   0 How to solve DIV2D/DIV1B ? I thought ans is $\sum\limits_{i=1}^n a_i *(c_i - d_i)$But I was not able to fill $c_i$ and $d_i$
 » 20 months ago, # |   0 Problem c division 2 why my solution gives TLE ? its O(LOG P) https://ideone.com/fDlClB
•  » » 20 months ago, # ^ |   0 It's O(sqrt(p)) not log(p) and sqrt(10^18) is 10^9 which is too slow
•  » » » 20 months ago, # ^ |   +1 thanks didnt even realize
 » 20 months ago, # | ← Rev. 2 →   0 I have no idea what I missed in Div1B :|I mean... I had multiple n^2 solutions, but nothing close enough.For every element I tried to calculate how many times it will be with + and with -. (if a is sorted) a[i] will be +, as long as it is in the first i/2 elements if his array, and will be — otherwise.That amounted to a sum of binomial coefficients that I didn't know how to reach a formula for. By the amount of people who solved it, I assume the answer had a completely different approach...Edit: just as an example, a[0] will always (i.e. 2n choose n times) be with a minus, and a[2*n-1] will always be with a plus.
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 The trick isIt does not matter how you split the array, the cost is always the sameI noticed it accidentally while looking at different partitions
•  » » » 20 months ago, # ^ |   0 That is so cool damn it xD
•  » » 20 months ago, # ^ |   0 No matter which arrangement you take, cost of partition remains the same. So just find the cost for an arrangement and multiply by total possible arrangements i.e., 2nCn.
•  » » » 20 months ago, # ^ |   0 WitchOfTruth Yogi79 What do you mean by the cost of the partition is same ?
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   +1 Sum of all differencesLet's say the array is 1 2 3 4 5 6 1 2 3 6 5 4 Total cost is 5 + 3 + 1 = 9 1 3 5 6 4 2 Total cost 5 + 1 + 3 = 9No matter how you swap elements, it will always be 9
•  » » » » » 20 months ago, # ^ |   +3 Wow! that's an amazing observation, just curious how did you come up with it ?It is very difficult to arrive at it analytically.
•  » » » » » » 20 months ago, # ^ | ← Rev. 3 →   +1 I wrote down a couple of partitions for n = 3 and tried to figure out some non-quadratic formulae, then just observations
•  » » 20 months ago, # ^ |   0 Yup... I just noticed that even though I knew it was non-increasing and non-decreasing, I tried solving it for non-increasing and non-increasing....LOL
 » 20 months ago, # |   0 Can someone provide a testcase where this would fail ? It ofcourse seems the wrong solution looking at other peoples answers but I'd like to know why :/https://codeforces.com/contest/1445/submission/97349096
•  » » 20 months ago, # ^ |   +1 I believe you did not consider the case where q is prime (so then divs would be empty)
 » 20 months ago, # |   0 Is CF PREDICTOR not working ? I think it's showing wrong rating prediction .
•  » » 20 months ago, # ^ |   0 how can u say that u did't participated in the contest??
•  » » 20 months ago, # ^ |   0 Yeah I think it is broken because it has been showing wrong predictions for some time now. Maybe the ranking algorithm changed.
 » 20 months ago, # |   +7 Can anyone tell me how C was solved because I can't wait for editorial. I bet it needed some witchcraft of math to get it. My thoughts were that if p % q != 0 you print p otherwise you know that p is divided by q and I could do nothing from there. I guess math is the reason I will never rank up. I guess I just need to solve all math problems until 2000 to be able to rank up from expert.
•  » » 20 months ago, # ^ |   +1 you can read tutorial it is out now.
•  » » 20 months ago, # ^ |   +1
 » 20 months ago, # |   +19 So many people got FST in D1C...
 » 20 months ago, # | ← Rev. 2 →   0 I was solving D1B in math all through the contest, but not until last five minutes did I find the pattern to solve the problem. I had no time to complete my code. It was the worst thing I met today...
•  » » 20 months ago, # ^ |   0 I was also trying to solve some double summation formula in fast way to solve this problem.
 » 20 months ago, # |   +28 E is very close to what I do in my uni research. In short it is computing treedepth of a line graph of a tree. I was even reviewing one paper about problem which was related to that one, but I didn't inquire on how to do that specifically and papers I've found were too long too read. There is a fair share of papers tackling this problem and in fact it is possible to solve it in linear time as proved here https://sci-hub.se/10.1007/s004530010076
 » 20 months ago, # |   +46 Pretests for Div1C are soooooooooooooooooooooo weak!!!!!!!!!!!!!!!!!!!!!!
 » 20 months ago, # | ← Rev. 6 →   0 I failed sys tests in DIV2 C because of precision issues in python!! urghh! So stupid of me writing int(x/i) instead of x//i 
 » 20 months ago, # |   +151 Thanks for strong pretests!
 » 20 months ago, # |   +52 Tfw I FSTed on C because I read the input wrongly. How did I pass pretests :thinking:(My code uses 0-indexed group numbers but I read group numbers in the input and forgot to subtract 1 from each of them oof)
 » 20 months ago, # |   +1 Obviously Codeforces is not to blame but I discovered something I didn't really know before. Thought it might be useful for others.So basically my approach was if the prime factorization of q exists in p such that for each prime factor and its respective power in q, there exists the same prime factor with >= power in p and this is true for all prime factors of q then I would have to try and set one power less of one of the prime factors of q in p and find the largest such number. This obviously works in theory but what I didn't account for was that pow() in C++ takes only double as arguments, converts everything down to double due to which for larger bases and exponents which were still in long long reach, there was inaccuracy in the result. Implemented with custom pow() it works perfectly.Very interesting, thought I'd share. Here are my two submissions :PS: RIP Rating :/
•  » » 20 months ago, # ^ |   +2 Everyone learns not to use pow() the hard way xD
 » 20 months ago, # |   0 Anyone faced issues in Div2 C question with PyPy3 submission where sys.maxsize was potentially used. My submission for the 2nd set of test cases, the 4 test case is giving the correct result 1 locally but on submission, it's showing participant output as some other 10 digit number. Then I used 10**20 instead of sys.maxsize it worked (but logically this change is not required).
•  » » 20 months ago, # ^ |   0 sys.maxsize depends upon the 32bit vs 64bit OS being used. Codeforces uses 32 bits thus my answer was coming wrong online.
 » 20 months ago, # | ← Rev. 2 →   0 Fastest Rating Updation : )
•  » » 20 months ago, # ^ | ← Rev. 2 →   +23 But with wrong name color.(It seems that CodeForces predicted my future.)
•  » » » 20 months ago, # ^ |   +4 Same happened with me also but between Expert and Specialist
 » 20 months ago, # | ← Rev. 3 →   +21 Hello,FST forces! :)This round is successful,but...We all passed during the contest time,but all failed in the system testing.Although our wrong solutions were hacked in the end,I think this is still one of the shortcomings of this round — pretests are too weak, leading to the wrong solutions must rely on the data submitted by users.I think you can strengthen pretests the next time.If we can get the WA result during the contest time,perhaps we will pass it.That's a pity for us.
•  » » 20 months ago, # ^ |   +37 Wrong solutions are wrong because contestants don't test them properly, not because the pretests are weak. It is completely in the contestant's power to test more thoroughly, and thus not depend on the whims of fate, authors, pretests, or whatever else.
•  » » » 20 months ago, # ^ |   +15 Why even have pretests then?
•  » » » » 20 months ago, # ^ |   +14 There are three test groups: samples, pretests, and final tests. Ideally: Samples help to understand the problem statement. Pretests catch obvious flaws in a solution. Final tests let only the correct solutions pass. As you can see, each group has its distinct purpose.The formal rules regarding pretests can be found here, and the contest format overview with a section on pretests is here. I think the question is vague, and tried to not imply any specific interpretation, as it would most probably be wrong. If the answer turns out to be unsatisfactory, please be more specific.
•  » » » » » 20 months ago, # ^ |   0 What can't be an obvious flaw?
 » 20 months ago, # |   +8 Thanks for this great contest!
 » 20 months ago, # |   +86 There are only one test in pretests of problem C except samples whose answer is not C(k,2). (I guess all of the tests in pretests are random graphs with fixed number of nodes and edges)Thanks for strong pretests!
 » 20 months ago, # |   +66 To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
 » 20 months ago, # | ← Rev. 2 →   +1 Can someone tell what is the minimum constant rank someone should keep, to become expert?Edit, I mean in Div 2
•  » » 20 months ago, # ^ |   +24 since u asked minimum, i would say 1, be careful you might become red
•  » » » 20 months ago, # ^ |   0 I don't know if you can become red, if you come 1 in Div2
•  » » 20 months ago, # ^ |   +4 A consistent 1000 should be a low-to-mid expert, although I'm not very sure.However, this is probably pretty useless, since you can't just say "I will be rank 987 for round #X". Just aim to solve more problems and learn more about solving problems :)
•  » » 20 months ago, # ^ |   +1 Just look in the standings table the rating changes of participants on that level.
•  » » 20 months ago, # ^ |   +1 I'd say you need to be around top1500 in contests like that and around top2500 in isolated div2 (because there is higher rating threshold)
 » 20 months ago, # | ← Rev. 3 →   +51 I usually dislike the usage of mod $998244353$ and favour $10^9+7$, but this time it was hilarious because input in B was up to $10^9$ and it allowed me to hack a solution which assumed the input is less than mod. Nice.P. S. Thanks for cool pretests in C! Admire that.
•  » » 20 months ago, # ^ |   +10 Oops
•  » » 20 months ago, # ^ | ← Rev. 3 →   +3 orz, thank you for your hack, you saved me from FST.
 » 20 months ago, # | ← Rev. 3 →   0 please explain why my code is not passing all the test case.My logic is — Both the array is already sorted so i reverse the array b and calculate the sum of a[1]+b[1] and a[n-1]+b[n-1]. This will give the possible range of sum of all corresponding indexs .so check the condition only these two will give the answer. Code link-https://ide.geeksforgeeks.org/aPAZIrNwTO
•  » » 20 months ago, # ^ | ← Rev. 3 →   -10 Are you dumb? Can't you provide the link to your submission instead of copy pasting the whole code, can't you see how ugly it looks!
•  » » » 20 months ago, # ^ | ← Rev. 5 →   0 Thanks for your advice ,sure i will take care of that .
 » 20 months ago, # | ← Rev. 2 →   0 Are there somebody know the feature of test 29 on Div.1 C, which I FSTed on it.
 » 20 months ago, # |   0 Idk if it's normal or not but I'm specialist with 1300 rating
 » 20 months ago, # |   +11 After this contest, my rating has increases by 159. And now my rating is 1328. But yet it shows that I am newbie. Has the rating system changed or it is a system problem?
 » 20 months ago, # |   +31 Thanks for the nice problems! My Div1C failed system test because I literally forgot to write a part of the solution. Surprisingly, pretests didn't catch that.Contrary to some other expressed opinions, I think it's a Good Thing. It's good when the contests teach us to actually test our solutions, instead of being given an instant and omniscient check on a silver platter.Solving problems, as a general skill, shouldn't depend on an oracle instantly telling you whether your solution is completely right, or has flaws. Some of the skill is to be able to gain confidence that you actually solved the problem, all by yourself.
 » 20 months ago, # |   0
 » 20 months ago, # |   +18 Easy way to avoid a lot of C FSTs: just make a lot of small test cases and, since the graph in the input doesn't have to be connected, you can just merge them all into 1 test case.
 » 20 months ago, # |   +11
 » 20 months ago, # |   +1 Anyone knows why rating changes of this round are rolled back?
•  » » 20 months ago, # ^ |   0 Never mind. It's rolled back now :D
 » 20 months ago, # |   +18 Dreams come true ;)
•  » » 20 months ago, # ^ |   +10 Congratulations!
•  » » » 20 months ago, # ^ |   0 Thanks!
 » 6 weeks ago, # |   0 can anyone tell me my mistake in problem div 2 C please ?158344415