### vaaven's blog

By vaaven, history, 6 weeks ago, translation,

Hi everybody,

This Sunday there will be a Moscow Olympiad for Young Students. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Team Olympiad and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727, 751, 775, 802, 829).

The round will be held at Feb/12/2023 11:35 (Moscow time) and will last for 2 hours. Note the unusual time of the round. The round will be held according to the Codeforces rules and will be rated.

Problems of this competition were prepared by Tikhon228, TheEvilBird, Ormlis, vaaven, Gornak40, Honey_Badger guided by vaaven, grphil and Helen Andreeva.

Thanks to Artyom123 for the round coordination, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Thanks to BucketPotato, KseniaShk, NemanjaSo2005, MagentaCobra, kuertov, prvocislo, 4qqqq, vsinitsynav, FynjyBath, qualdoom, ivanlarin, didedoshka, petyb, PBBx0, MIKHANGO, charlyk, RP-1, talant, ak2006 for testing.

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

Good luck everybody!

UPD: Score distribution: 500 — 1000 — 1250 — 1750 — 2500 — 3250

UPD2: Еditorial

• -485

 » 6 weeks ago, # |   +52 The round will be held according to the Codeforces rules and will be rated for both divisions. Shouldn't it be rated for Division 2 only?
•  » » 6 weeks ago, # ^ |   +99 Shhh, I’m desperate for a rated contest
•  » » » 5 weeks ago, # ^ |   +4 Like me!
•  » » » 5 weeks ago, # ^ |   0 The feeling when you get a negative in recent contest and want to bounce back.
 » 6 weeks ago, # | ← Rev. 2 →   +44 As a tester I can say that I am a tester (again). Don't hurt me, I hope this time everything will be fine.
•  » » 5 weeks ago, # ^ |   +14 testers are so cool!
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +6 Thanks, hope we don't let you down!
•  » » 5 weeks ago, # ^ |   -46 if FynjyBath = tester, round = bad
 » 6 weeks ago, # |   +116 o.O
•  » » 5 weeks ago, # ^ |   0 Nice avatar
•  » » » 5 weeks ago, # ^ |   -24 thanks(
•  » » » » 5 weeks ago, # ^ |   +26 Forgot to switch the account back?
•  » » » 5 weeks ago, # ^ |   0 thank you for -20(((
 » 6 weeks ago, # |   +30 As a tester, I enjoyed the problem set.
•  » » 5 weeks ago, # ^ |   0 What will be the distribution of points?
•  » » » 5 weeks ago, # ^ |   +4 Sorry, saw your message late. It is not testers who decide that. As you can probably see, the author made an update to the blog, the distribution is: 500 — 1000 — 1250 — 1750 — 2500 — 3250
•  » » » » 5 weeks ago, # ^ |   0 Aiming for first 3 problems then!Let's see how it goes :)
•  » » » » » 5 weeks ago, # ^ |   -8 I just could not figure out what was wrong with problem A.This was my solution: #include #define ll long long using namespace std; void solution() { ll a = 0, b = 0, n = 0, m = 0, result = 0; cin >> a >> b; cin >> n >> m; ll promotions_available = (n * m / (m + 1)); if ((promotions_available + promotions_available / m) * b > (promotions_available * a)) { result += promotions_available * a; n -= (promotions_available + promotions_available / m); } // Buy the rest from the cheapest without the promotion if (n > 0) { result += min(a, b) * n; } cout << result << "\n"; } int32_t main() { int t; cin >> t; while (t--) solution(); } 
•  » » » » » » 5 weeks ago, # ^ |   +8 ll promotions_available = (n * m / (m + 1)); should be ll promotions_available = (n / (m + 1)) * m;
•  » » » » » » » 5 weeks ago, # ^ |   0 can you explain it?
•  » » » » » » » » 5 weeks ago, # ^ |   0 I have been thinking about it and when drawn out on paper, it is correct.But we want to get the number of (m+1) groups that can be fitted inside n. That is (n / (m + 1)). Then I multiplied by m to get (n * m / (m + 1)). But we use integers and we want to multiply the number of groups with the cost!As it is now (n * m / (m + 1)) would be rounded down which is not what we want! That is what helped me to understand why this failed when I retried it multiple times.TLDR; Math checks out but we deal with integers and roundings. (Correct me if I'm wrong @nor)
•  » » » » » » 5 weeks ago, # ^ |   +2 I found some errant cases for you.TL; DR -> a = 6, b = 5, n = 9, m = 4, expected output = 44; your output = 45You can use the following code for the same. Testcase Generatorpublic class Main { public static void main(String[] args) { java.util.concurrent.ThreadLocalRandom rand = java.util.concurrent.ThreadLocalRandom.current(); final int TEST_CASE_COUNT = 10; System.out.println(TEST_CASE_COUNT); for (int i = 0; i < TEST_CASE_COUNT; i++) { int a = rand.nextInt(1, 10); int b = rand.nextInt(1, 10); int n = rand.nextInt(4, 10); int m = rand.nextInt(3, 10); System.out.println(a + " " + b + " " + n + " " + m); } } }  AC Code (you can use any other as well)public class Main { public static void main(String[] args) { java.util.Scanner in = new java.util.Scanner(System.in); int testCaseCount = in.nextInt(); for (int testCase = 0; testCase < testCaseCount; testCase++) { long a = in.nextLong(); long b = in.nextLong(); int n = in.nextInt(); int m = in.nextInt(); long better = Math.min(a, b); long cost = better * n; int extra = n / (m + 1); boolean extraHelps = a * m < better * (m + 1); if (extraHelps) { cost -= extra * (m + 1) * better; cost += extra * m * a; } System.out.println(cost); } System.out.close(); } }  Debugging ProcedureRun the generator and save the input in a text file. Use that input to get output from your code, as well as AC code.Compare the two and debug. Note that this can be done efficiently with scripts. I don't have windows scripts on hand right now, but it's easy with Linux.
•  » » » » » » » 5 weeks ago, # ^ |   0 Thanks!
•  » » » » 5 weeks ago, # ^ |   0 Very Good!
 » 6 weeks ago, # |   +15 As a tester I can say that problems are very interesting. Have a good luck on this round:D
•  » » 5 weeks ago, # ^ |   0 i can say problems are very hard LOL :)
 » 5 weeks ago, # |   0 Note the unusual time i.e. 6hrs before general time.
 » 5 weeks ago, # | ← Rev. 2 →   +3 is score distribution going to be announced before the contest? also can it be delayed ? it clashes with Innopolis finals time
•  » » 5 weeks ago, # ^ |   +3 It can't be delayed since it has to be held during Moscow Olympiad for Young Students.
 » 5 weeks ago, # |   0 The name of the writers had not been updated yet in the Contest Section.
 » 5 weeks ago, # |   -31 Note the unusual time of the round.
 » 5 weeks ago, # |   +8 Fingers Crossed for +delta (◠‿◠)
•  » » 5 weeks ago, # ^ |   +52 Don't cross your fingers, it will be difficult for you to type during contest. (◠‿◠)
•  » » » 5 weeks ago, # ^ |   0 lol
 » 5 weeks ago, # |   +11 I will solve this olympiad. Good luck to everyone at the round and the olympics!
 » 5 weeks ago, # |   +15 Friendly time for Vietnamese like me
•  » » 5 weeks ago, # ^ |   +10 And Chinese like me
•  » » 5 weeks ago, # ^ |   0 I'm also Vietnamese!!!
 » 5 weeks ago, # |   0 eagerly waiting for a rated contest . Good luck everyone !!
 » 5 weeks ago, # |   +8 is this china mathforces round or am i safe?
 » 5 weeks ago, # |   0 I am looking forward to the problems of this contest, hoping to surprise me.
 » 5 weeks ago, # |   +3 I hope we can enjoy ourselves in this contest.Make it Sunday, February 12, 2023 at 16:35(UTC+8)
 » 5 weeks ago, # |   0 This is at midnight for me. Hopefully I don't brick it :/
 » 5 weeks ago, # |   +5 I have classes T_T... But still good luck awa
 » 5 weeks ago, # |   0 i guess it will be speedforces round
 » 5 weeks ago, # |   0 Hoping to have a great round with great learnings!
 » 5 weeks ago, # | ← Rev. 2 →   +1 hope the best for all and to get my cyan color today :)Edited okay I think I will wait for my cyan for another day :D
•  » » 5 weeks ago, # ^ |   0 same. cant wait to demote to newbie bro
 » 5 weeks ago, # |   0 Good luck everybody, hope problems will be interesting!
 » 5 weeks ago, # |   0 Is the other contest still ongoing?
 » 5 weeks ago, # |   -14 Such a permutationforces.
 » 5 weeks ago, # | ← Rev. 7 →   +30 The problem F is the same as 765F.My code was copied from https://www.luogu.com.cn/problem/solution/CF765F. Edit: Please don't upvote this comment.
•  » » 5 weeks ago, # ^ |   +4 I don't understand why you upvote this. Firstly,if you notice that a problem is similar with another one in the past,keep it for yourself and don't spoil the contest. Second of all,saying that you copied your code from a solution source is against the values imposed by codeforces(ig).
 » 5 weeks ago, # |   +4 A funnily embarassing contest for me -- A >> B > C for me. I solved the problems in the order C, B, A and got 5 WA on A before getting it. My math solution had a bug I couldn't find, so I tried to binary search the amount potatoes to buy for 'a' coins, which obviously didn't work. Then I thought the function was unimodal, so I tried ternary search on the potatoes, which still didn't work! Finally, I decided to scrap my mess of a code and prove a solution on paper and then implement it. It was less stressful after the 4th WA anyways, since I already hit the maximum penalty for a problem... Finally I solved Problem A, 76 minutes into the contest! I am proud of my persistence and disgusted at my stupidity.
•  » » 5 weeks ago, # ^ |   +3 I used binary search for A and it worked. Have no idea how to solve it normally though...
•  » » » 5 weeks ago, # ^ |   0 I did the case work on paper: let mx be the most multiples of (m+1) that we can buy without overbuying. Then the answer is the minimum of {n*b, (mx+1)*(a*m), (a*m*mx)+(n-(m+1)*mx)). I wish my binary search solution worked so I could have solved it earlier.
 » 5 weeks ago, # |   +5 OMG, B is so hard, can anyone explain the solution problem B for me :((
•  » » 5 weeks ago, # ^ |   +4 I didn't prove it, but I solved it in a few minutes by greedily going max_sum, max_sum-1, max_sum-2... min_sum, min_sum+1, min_sum+2.. max_sum-1. I was surprised it worked.
•  » » » 5 weeks ago, # ^ |   +3 Thank you so much. The sad contest, I can't solve B.
•  » » » » 5 weeks ago, # ^ |   +6 Same. I'm beginning to question my ability to make observations :(
•  » » 5 weeks ago, # ^ |   0 Note the length of the array is always (x-y)*2 .
•  » » » 5 weeks ago, # ^ |   0 I couldn't figure that out, I just had a counter and incremented it by 1 every time I outputted a number lol
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 if x>y -> x, x-1, x-2, ... , y+1, y, y+1, ... , x-1 there is only one higher and lower point and always difference 1
•  » » » 5 weeks ago, # ^ |   0 what if x = 3 and y = 2? 3 2 ??
•  » » 5 weeks ago, # ^ |   0 Just start from max sum, go down to min sum and then go up to max sum -1. The reason it works is that, only the max/min sum will be local maxima/minima so, all others are unimportant.
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   +3 n = (x — y) * 2. That's because local minimum and local maximum are alternating(x1, y1, x2, y2, x3, y3, ...(that's quite easy to prove)) which means that the quantities of minimums and maximums are equal(that's unimportant to the solution, it's just an interesting fact). So with this information we can easily count n. Lets look at slice [x1...y1..x2). We can easily count the quantity of all elements in the slice [x1...y1...x2): n = x1 — y1 + x2 — y1. Then add n to answer and do such thing till you return to your first slice. We can see that the final result will be ans = 2 * x1 + 2 * x2 + ... + 2 * xm — 2 * y1 — 2 * y2 — ... — 2 * ym = 2 * (x1 + .. xm — y1 — ... — ym) = 2 * (x — y). Finally, we can easily create an appropriate array with only 1 maximum and minimum which are equal x and y.
 » 5 weeks ago, # |   +42 How to solve F? I tried Mo's algorithm, but it won't pass the time-limit. Any nice optimization required in Mo's algo?
•  » » 5 weeks ago, # ^ |   0 Idk if it will pass or not but anyways you should try this optimization: Optimization with Hilbert curve
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I've tried F with Mo's algo + multisets, TLE4 My multiset solution had high constant factor(10 operations per index) so I decided to come up with a segtree solution(2 calls to update per index) but it still TLEs. I tried with some different block sizes too like N/logN, N/sqrt(q) etc. Also added that zig zag sort. They all TLE lol. Hilbert curve optimization works better with small q, so it's not going to change anything
 » 5 weeks ago, # |   +10 Bricked B and then couldn't submit D in time.
 » 5 weeks ago, # | ← Rev. 2 →   +5 Seems that last problem is very popular.
•  » » 5 weeks ago, # ^ |   +17 last problem is a copy of 765F - Souvenirs
 » 5 weeks ago, # |   0 the n = 2 case in B is very stupid
•  » » 5 weeks ago, # ^ |   0 agreed i am surprised that the answer for the case when x — y = 1 is just an array of {x , y} :((statement so unclear and stupid
 » 5 weeks ago, # |   +30 Make it unrated, unless you play too much genshin.
•  » » 5 weeks ago, # ^ |   0 Why Genshin out of nowhere...
•  » » » 5 weeks ago, # ^ |   0 it's just a joke hhh
 » 5 weeks ago, # |   -26 Best contest I have ever seen!..
 » 5 weeks ago, # | ← Rev. 2 →   0 what even is pretest 6 for problem D? i tried to use segment tree type of answer and i still don't know the corner case (that or i somehow fluked the 4th and 5th pretest lol). Also tricky problem A ;)
•  » » 5 weeks ago, # ^ |   0 I mistyped min to max when initializing prefix min of positions. However it also squeezed into the first 5 pretests:(
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Segment Tree seems pretty overkill for D. My strategy was to count the #of subsegments such that they share a common MEX by iterating over the MEX value and using 2 pointers to handle everything. I got it to pass the example cases too. Wish I could have submitted it :(Edit: It got accepted. Here's the code if anyone's curious: 193333734
•  » » 5 weeks ago, # ^ |   0 One tip is to write a brute force solution for D and compare your submission with the brute force solution.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 SolutionI started by counting solutions with subsegments not including ones, then includeing 1s and not including 2s then includeing 2s and 1s not including 3s ... I used combination for counting this stuff which you can make O(1) easily, so my approach is O(n) which passes(and passed). Code// time-limit: 2000 // problem-url: https://codeforces.cc/contest/1793/problem/D #include using namespace std; #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,tune=native") #define int int64_t #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define txtio(s) freopen((string(s)+string(".in")).c_str(),"r",stdin);freopen((string(s)+string(".out")).c_str(),"w",stdout); #define F first #define S second #define MP make_pair #define PB push_back #define sqr(a) (a)*(a) #define endl '\n' #define I insert const int mod=1000000007; int binpow(int a, int b) { int res=1; while (b>0) { if (b&1) res=res*a; a=a*a; b>>=1; } return res; } void solve(int wasd){ //cout<<"Case "<>n; vector p(n,0),q(n,0); for(int i=0; i>tmp; p[tmp-1]=i; } for(int i=0; i>tmp; q[tmp-1]=i; } int ans=(abs(p[0]-q[0])-1)*(abs(p[0]-q[0])-2)/2+min(p[0],q[0])*(min(p[0],q[0])-1)/2+(n-max(p[0],q[0])-1)*(n-2-max(p[0],q[0]))/2+n-max(p[0],q[0])-1+min(p[0],q[0])+abs(p[0]-q[0])-1; int curl=min(p[0],q[0]),curr=max(p[0],q[0]); for(int i=1; i=curl&&p[i]<=curr)||(q[i]>=curl&&q[i]<=curr)){ curl=min(curl,min(p[i],q[i]));curr=max(curr,max(p[i],q[i])); continue; } if(min(p[i],q[i])>curr){ ans+=(curl+1)*(min(p[i],q[i])-curr); } else if(max(p[i],q[i])>t; for(int i=0; i
•  » » 5 weeks ago, # ^ |   0 did u find what is pretest 6? mine is also failing
 » 5 weeks ago, # |   +15 How to do F ? I tried using Mo's algo with sets, but that doesn't feel to squeeze in the TL
•  » » 5 weeks ago, # ^ |   +36 just go to https://codeforces.cc/problemset/problem/765/F and read editorial
•  » » » 5 weeks ago, # ^ |   +5 Anyway, is it possible with MO? I have TL too.
•  » » » » 5 weeks ago, # ^ |   +9 Yes, it is possible with MO. To pass time limit, you need super fast set for integers and super fast IO. Check out my code.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Can you copy-paste your code into somewhere else, because currently we're not allowed to look into other's submissions.
•  » » » » » » 5 weeks ago, # ^ |   +8 Oh, didn't notice that. Code
•  » » » » 5 weeks ago, # ^ |   0 I solved https://codeforces.cc/problemset/problem/765/F with Mo's algorithm: https://codeforces.cc/contest/765/submission/164782195.However, I'm sure my solution won't pass TL in today's problem.
 » 5 weeks ago, # | ← Rev. 2 →   +16 is it sure that F isn't https://codeforces.cc/problemset/problem/765/F?
 » 5 weeks ago, # |   0 yayy I was able to attempt D this time.. hoping system test pass
•  » » 5 weeks ago, # ^ |   0 accepted :)
 » 5 weeks ago, # |   0 My solution to $C$.For every element $l$ as left position, there is minimal $k$, such that it is required to $r \ge k$ for $l$ not to be minimum or maximum. Find all these $k$ in linear time using stack (note, there can be no such $k$). Let it be $left[i]$. Then do the same in other direction: $right[i]$ is rightmost position, at which $i$ is neither max nor min.Now we have to find $l$ and $r$ such that $l \le right[r]$ and $r \ge left[l]$. Fix $l$. We have to check, if there is $r \ge left[l]$, such that $right[r] \ge l$. We can do this using segment tree for maximum and position of maximum.Whose solution is longer?
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 I used two pointers -- while(l < r && flag), flag = false, if a[l] or a[r] = min or max, increment l or decrement r, increment min or decrement max, and set flag to true. Then output l and r as the answer,
•  » » » 5 weeks ago, # ^ |   0 Same
•  » » 5 weeks ago, # ^ |   +5 I did the exact same thing, even the same variable names.But it feels like there is a better sol
•  » » 5 weeks ago, # ^ |   0 As i understand you try to find l and r for every element in array, so it is O(n^2). There is no requirement that length of subsequence should be minimal, so we could just check that left and right elements aren't current minimal or maximum
•  » » 5 weeks ago, # ^ |   0 I loved problem C! My solution is even simpler. I solved with also two pointers, but instead of the segment tree, I used 2 RMQs. Starting from the first and last element, check whether the range is good or not with RMQ; if it is good, print and stop. Else, update left and right by equality conditions, respectively. The segment tree method is another solution, but I think RMQ is even shorter and simpler. Btw used the sparse table method, so it gives min and max in O(1).
•  » » » 5 weeks ago, # ^ |   0 I got AC without segment tree or sparse table. Just notice that at the beggining you have all values from 1 to n in your segment, so when you move your pointers you can just update min and max.
•  » » » » 5 weeks ago, # ^ |   0 Yeah, that is also correct and even simpler xD. Congrats :)
•  » » » » » 5 weeks ago, # ^ |   0 It was a guess though. I wasn't 100% sure if it would work.
•  » » » » 5 weeks ago, # ^ |   0 Wow! So simple approach! Thanks for this :)
•  » » 5 weeks ago, # ^ |   0 I have also overkilled! same idea and used 3 sparse table :)
 » 5 weeks ago, # |   +6 Why is C easier than A and B?
•  » » 5 weeks ago, # ^ |   +1 no it isn't
 » 5 weeks ago, # |   +29 Problem E is just beautiful! Solution sketch:First sort array $a$. Henceforth I assume $a$ is sorted.We can prove by greedy exchange that the set of satisfied people form a prefix of $a$. Now, let's fix the prefix of satisfied people. Let's maximize the number of distinct books that this fixed set of satisfied people can be assigned such that all have to be read by at-least one personWe can prove again, that: if the set of satisfied people lie in more than $1$ group, then it is never more optimal to take any unsatisfied person in a group of satisfied people otherwise the set of satisfied people lie in a single group, and the answer (maximum number of distinct books that can be assigned such that all are read) is trivial to compute. So for each prefix, we have found the maximum number of distinct books. But the number of books that can be assigned to a prefix is monotonic: if you can assign $k$ books, you can also assign $k-1$ books. So if answer for a prefix of size $j$ is $k$, update answer for each $i<=k$ with $j$. This can be done trivially by maintaining suffix maximums.193328416
 » 5 weeks ago, # |   +3 brought a permutation p of length n to the zoo This sentence lol!
 » 5 weeks ago, # | ← Rev. 2 →   +4 What will happen if you try to hack someone's solution with this test x = 1e9 ,y = -1e9 in problem B ?
•  » » 5 weeks ago, # ^ |   0 solution exist only for n<1e5 (given) so above case will not have any solution
•  » » » 5 weeks ago, # ^ |   +18 Yes, absolutely. I think they should have written that the sum of the differences between x and y would not exceed 1e5
•  » » 5 weeks ago, # ^ |   0 First line of the question For his birthday recently Fedya was given an array a of n integers arranged in a circleLast line of the question It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5
 » 5 weeks ago, # |   +4 Im extremely sad. I just solved question D 5 minutes after contest ended. And the even sadder part is that I joined the contest 30 mins late :((. You can tell because I only solved first question after 35 mins. And solved the next two questions almost immediately.
 » 5 weeks ago, # |   +6 Problem C just feels lot easier than Problem B.
 » 5 weeks ago, # |   +10 bad problem F
 » 5 weeks ago, # |   +2 Difficulty order according to me: B>A>D>C
•  » » 5 weeks ago, # ^ |   +7 I would swap A and D around, but I agree with this lol. Wasted a ridiculous amount of time on B
•  » » 5 weeks ago, # ^ |   0 what was your idea for D that you put is so low on difficulty?
 » 5 weeks ago, # |   0 can we solve question e using binary search like our predicate function will be greedily picking smallest k number of people and satisfying their needs. here I am applying binary search on number of peoples we can satisfy tle solution also works
 » 5 weeks ago, # | ← Rev. 2 →   -10 .
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 my submissionbasic idea is with 3 conditionsprice on first day is a and price on second day is bthen if (a < b) ... you should alway buy on first day if (a > b BUT you can save with a discount ) then you should get discounted items on first day and remaining on second day else buy everything on second day
 » 5 weeks ago, # |   +68 Why is problem B such a troll? It says that $-10^9 < y < x < 10^9$ and the answer has length $2 \cdot(x-y)$. In my opinion, you should not put this kind of "traps" in Div2 problems, especially in A and B.
•  » » 5 weeks ago, # ^ |   +16 First line of the question For his birthday recently Fedya was given an array a of n integers arranged in a circleLast line of the question It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5
•  » » » 5 weeks ago, # ^ |   +21 This is a wrong use of the phrase it is guaranteed.See thisMeaning 2: Make it clear that this ‘guarantee’ is an additional constraint on the input. Input is only allowed if X. In the example above: “Only input for which some C exists is legal input.”
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 oh, thanks for sharing this. Something for me to think about
•  » » 5 weeks ago, # ^ |   0 Exactly , I was wondering how would i even print such a huge sequence even if i get one :/
•  » » 5 weeks ago, # ^ |   +10 Exactly, It had took my lot of time for optimizing number of operations, and I checked constraints on x and y more than 5 times, Also problem statement of A is not well written, it could be written in 2-3 lines. Even F is taken according to me.
•  » » 5 weeks ago, # ^ |   +19 Agreed, perhaps the worst Div. 2 B of all time, or at least in recent memory.
•  » » 5 weeks ago, # ^ |   +1 I totally agree with this, just this line alone $-10^{9} \le y < x \le 10^{9}$ can mislead people to think that $x = 10^{9}$ and $y = 10^{-9}$ is a valid input, even though the next line says that the sum of $n \le 2 * 10^{-5}$And as such leaving their head scratching that there is a better answer than $2*(x-y)$ for $x = 10^{9}$ and $y = 10^{-9}$ that can fit into the given constraint on $n$, which can possibly cause them to get stuck forever
 » 5 weeks ago, # |   +10 The problem A is just way too annoying!!
•  » » 5 weeks ago, # ^ |   0 yaa !did u solved it ? i thought it's easy but took lot of efforts but still didn't got accepeted '~'
•  » » 5 weeks ago, # ^ |   0 can you explain why my code is wrong? void solve(){ ll a,b; cin>>a>>b; ll n,m; cin>>n>>m; if(n <= m){ cout<
 » 5 weeks ago, # | ← Rev. 2 →   +13 A: Divide n potatoes into floor(n/(m+1)) groups and n%(m+1) single potatoes. The price for a group is min(m*a, (m+1)*b), and for a single potato is min(a,b).B: Go down from x to y by step -1, then go up from y to x by step +1.C: Recursion. First, check if [1,n] is a good segment. If not, then a[1] or a[n] will be the max or min value on this segment. If a[1]=1 or a[1]=n, then we need to solve recursively on [2,n], otherwise we solve on [1,n-1]. We do this recursively until we find an answer, or the length of the current segment is <4. Also we need to maintain the max and min value on the current segment.D: Consider for each possible MEX in [1,n+1]. For MEX=1, we need to find the position of 1 in p and q, and count the number of segments which doesn't contain these positions (which is a subsegment of 3 segments splited by positions of 1), and for MEX=n+1 it's trivial (only [1,n] will have MEX=n+1). For MEX in [2,n], we need to find the minimal segment containing numbers in [1,MEX-1] in both p and q (this segment can be updated by expanding previous segment to contain MEX-1), and find the positions of MEX, we can expand the minimal segment in both directions until it touch these position (also, if there's any occurrence of MEX in the minimal segment, the contribution of MEX is 0).
•  » » 5 weeks ago, # ^ |   +5 Can you prove B?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 Let the difference between the sum of local maxima and local minima be $d$, and let $n$ represent the optimal solution size (note that $n$ must be even). Assume that $d>1$ so that $n$ must be greater than 2.Consider a local maxima — it must occur as $\ldots,x,x+1,x,x\pm 1,\ldots$ and now, remove the centre two elements, and we have a new sequence $\ldots,x,x\pm 1,\ldots$ which has $d'=d-1$, and a solution with $n-2$ elements, and reduce.EDIT: (And a local maxima will always exist)
•  » » 5 weeks ago, # ^ |   0 yaa in first attempt in A i did exactly what u r saying but didn't get accepted so started thinking something else
•  » » 5 weeks ago, # ^ | ← Rev. 6 →   0 Great Explanations !! I managed to solve C using 2-Pointers as following: " Don't forget to move the pointer, and if we got "l==r" then -1 " if "l" or "r" is pointing at min then "new_min = min+1" if "l" or "r" is pointing at max then "new_max = max-1" if none of above then print (l, r) found = False l, r = 0, N — 1 MN, MX = 1, N while l < r: if A[l] == MN: MN += 1 l += 1 elif A[l] == MX: MX -= 1 l += 1 elif A[r] == MN: MN += 1 r -= 1 elif A[r] == MX: MX -= 1 r -= 1 else: found = True break if found: print(l + 1, r + 1) else: print(-1) 
•  » » 5 weeks ago, # ^ |   0 In A isn't it possible that if we buy x number of the potatoes out of n from a and remaining from b so now we vary this x How can we claim that it is best to divide all n in m+1 groups for a and remaining for b Can't there be any intermediate x out n for which we find the best possible minimum I tried this using binary search but W/A
•  » » » 5 weeks ago, # ^ |   0 It's not "divide all n in m+1 groups for a and remaining for b". In fact, there are at least n%(m+1) potatoes we can't buy them by favorable price (so we must buy them by price min(a,b), and we can by at most (m+1)*floor(n/(m+1)) potatoes by favorable price (which is min(a*m/(m+1),b)).
•  » » » » 5 weeks ago, # ^ |   0 Let c=intmax, l=0,r=n,mid what i am saying is that what if we take i=mid and j=n-mid then we can calculate 'a' for i and 'b' for jif this is less than equal to c we do r=mid-1 and else we do l=mid+1i have understood that we can give n%(m+1) to min(a,b), but now it is only applicable when we give (n-n/(m+1)) to 'a', so what i am thinking is if we find certain 'mid' which can give a better result by using same distribution formulae?
•  » » » » » 5 weeks ago, # ^ |   0 I can't understand why you think about binary search. But we can consider problem A atart anew:--Consider we want to buy only k potatoes where k= m+1 potatoes we need. So we can do 2nd operation repeatly until we can't do more operations (which means, there're <=m potatoes we need to buy). Then we need to use 1st operation for remaining potatoes.
 » 5 weeks ago, # |   +4 That B problem T_T
 » 5 weeks ago, # |   0 Is anyone able to tell me why in problem B, in the first test case where the local maximum = 3 and the local minimum = -2 the solution cant be just the numbers 3 and -2?It doesn't seem to break any of the requirements? Am i missing something?My submission to problem B
•  » » 5 weeks ago, # ^ |   0 Am i missing something? : Yesconsecutive numbers should have a difference of 1 :)
•  » » » 5 weeks ago, # ^ |   0 The problem says absolute difference and the numbers 3 and -2 seem to have an absolute difference of 1 right?Or is it that abs(3-(-2)) = abs(3 + 2) = 5 ?
•  » » » » 5 weeks ago, # ^ |   0 Absolute difference doesn't mean the difference between the absolute values of the numbers.It is the absolute value of the difference
•  » » » » » 5 weeks ago, # ^ |   0 Ok thank you, it was my mistake and makes sense now :D
•  » » » » 5 weeks ago, # ^ |   0 it's the latter one sadly
 » 5 weeks ago, # |   +1 Can someone show testcase 6 in D?
•  » » 5 weeks ago, # ^ |   0 Check this case: 4 2 3 1 4 2 3 1 4 answer = 10
•  » » » 5 weeks ago, # ^ |   0 my answer is 10, but thanks
•  » » » 5 weeks ago, # ^ |   0 my code passes this and the samples but fails tc 6 lol
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Check this case:64 1 2 3 5 65 6 4 1 2 3answer = 6
•  » » » 5 weeks ago, # ^ |   0 also correct, Im waiting for open submissions ;d
 » 5 weeks ago, # |   0 OMG,D is so hard,can anyone explain the solution of problem D for me :(
•  » » 5 weeks ago, # ^ |   0 FOR（MEX，1，n+1） { Find Range of L in this MEX Find Range of R in this MEX answer += len of Range_L * len of Range_R } you can solve MEX=i by MEX=i-1
 » 5 weeks ago, # |   0 The fact that there are people who failed to solve D, but were able to solve F in under 30 minutes :)
 » 5 weeks ago, # |   +23 Why is this getting downvoted, the round was pretty nice?
•  » » 5 weeks ago, # ^ |   0 Cause F problem was present in previous contests. Most probably round gonna get unrated
•  » » » 5 weeks ago, # ^ |   0 This round will not get unrated, Mike did a very good blog post as to why it won't get unrated.
•  » » » 5 weeks ago, # ^ |   0 where can I see check it? :) , I need the editorial
 » 5 weeks ago, # |   0 I managed to solve A-D and I have to say I quite liked all the problems. Sadly, I did not look at E.
 » 5 weeks ago, # | ← Rev. 2 →   +2 Problem B give me [-1e9;1e9] and so I say: Nani? How I can minus one with range 1e9 LOL? Finally, I solved it by subtracting the value by 1 and it worked XD! Sorry for my english !
 » 5 weeks ago, # |   +7 I spent nearly an hour on problem F but now it coincided with another problem in the old round. I don't have time to solve D and E. /kk
 » 5 weeks ago, # | ← Rev. 5 →   +5 you can check the video editorial for
 » 5 weeks ago, # |   -11 Even without considering that the problem F has appeared in the past round, I think the problems in this round is simpler than usual.
 » 5 weeks ago, # |   0 Last two rounds max only maths problems
 » 5 weeks ago, # | ← Rev. 2 →   +9 I spent almost 40 mins for solving the problem B for the given constraints. Finally left the contest. One of the worst contests in recent times.
 » 5 weeks ago, # |   0 two-pointer forces :).
 » 5 weeks ago, # |   +3 The objective of the last problem is fairly simple, (not the solution, just the objective), so it makes sense that a similar problem has already been proposed before. Imo, this coincidence wasn't the only issue with this round, Speedforces rounds are becoming increasingly common these days; though it was indicated beforehand by the problem ratings, still this isn't ideal.
 » 5 weeks ago, # |   +17 When will the submissions and testcases open?
 » 5 weeks ago, # |   +11 When can we see the source codes of others? I'm DESPERATE to see where did I get wrong
•  » » 5 weeks ago, # ^ |   0 In the standings page you can double-click on their scores
•  » » » 5 weeks ago, # ^ |   0 I don't think that this one is open yet.
•  » » 5 weeks ago, # ^ |   0 be patient for the sys test and hacking session to be done
 » 5 weeks ago, # |   0 How to solve A? I have tried deperately in contest math, binary search but everytime something got wronged
•  » » 5 weeks ago, # ^ |   0 my submissionbasic idea is with 3 conditionsprice on first day is a and price on second day is bthen if (a < b) ... you should alway buy on first day if (a > b BUT you can save with a discount ) then you should get discounted items on first day and remaining on second day else buy everything on second day
•  » » » 5 weeks ago, # ^ |   0 cost1 = (n/(m+1))*m*a + min((n%(m+1))*a, (n%(m+1))*b) cost2 = n*bans = min(cost1, cost2)Explaination : cost1 will be generated from first day buying potatoes on with set of m+1 at the cost of m and rest will be bought either at price of a or b whatever is min. Cost 2 will be generated from buying all the potatoes second day and min of these two will be your answer.
•  » » 5 weeks ago, # ^ |   0 Bro there will be three cases 1) The purchaser will buy all the potatoes on day 1 without the offer. 2) The purchaser will buy all of it on day2. 3) The purchaser will buy the potatoes on day1 n/(m+1) times and the remaining either on day1 or day2.Here is my submission. 193334956
•  » » » 5 weeks ago, # ^ |   0 Yes your approach is correct but your 1st case is redundant because it's going to be checked in 3 case. but nothing harm in it
 » 5 weeks ago, # |   0 193350417why getting WA? what is wrong with my code can anyone tell please?
•  » » 5 weeks ago, # ^ |   0 got it! i was minimizing two indexes each time but i had to check every index; sad though
 » 5 weeks ago, # |   0 when will u update editorial please :o
 » 5 weeks ago, # |   0 Hi! this is my first competition.. I was wondering when my rating will be updated ?
 » 5 weeks ago, # |   +3 Is this round Unrated?
 » 5 weeks ago, # |   0 Problem C : Dora and Search video Editorial Link : https://youtu.be/l5GgWZmsZ98 Happy Coding
 » 5 weeks ago, # |   0 Good Contest.
 » 5 weeks ago, # |   0 Approach for D: For MEX 1: we have to find no. of common subarrays which dont include 1. So lets say of the 2 arrays leftmost 1 is at i, and rightmost 1 is at j then all subarrays forming less than index i, in b/n i and j , greater than j will give MEX=1.Now for MEX=2 : We have to fix the subarray where 1 is present in both so i to j is fixed. Now check how many common subarrays we can form excluding 2. Here 2 can lie in the opposite direction of i,j or at the same direction. If it lies in b/n i,j so MEX=2, doesnt exist. also expand i,j which will include 2 for next MEX calc
 » 5 weeks ago, # |   0 In todays contest i swear to god i done problem C by myself but the system is showing that "Your solution 193304701 for the problem 1793C significantly coincides with solutions....." .For the first time i solved 3 problems, and i was very much happy to be able to do that, but this happend :( .Please can anyone tell me whome i should reach for this issue . This is my first comment on cf so please forgive me for my mistakes if any.
•  » » 5 weeks ago, # ^ |   0 You can do nothing my bro.
•  » » » 5 weeks ago, # ^ |   0 isn't it unfair for those who did not copied ?
•  » » » » 5 weeks ago, # ^ |   0 You are Pupil my bro Congrats!!
•  » » » » » 5 weeks ago, # ^ |   0 Thanks bro :)
 » 5 weeks ago, # |   0 In my opinion, C is easier than B.
•  » » 5 weeks ago, # ^ |   0 todays order was a > b > c literally reverse
 » 5 weeks ago, # |   0 #include #include #include #define ordered_set tree, rb_tree_tag, tree_order_statistics_node_update> #define vll vector #define pll pair #define vpll vector #define rep(a, b, c) for (int a = b; a < c; a++) #define ff first #define ss second #define ll long long #define mod 1000000007; using namespace __gnu_pbds; using namespace std; void solve(){ ll a,b; cin>>a>>b; ll n,m; cin>>n>>m; if(n <= m){ cout<> t; do { solve(); } while (--t); return 0; } why is this not working for A? can someone help please
 » 5 weeks ago, # |   0 is this contest unrated ?
 » 5 weeks ago, # |   0 unfair contest
•  » » 5 weeks ago, # ^ |   0 unfair contest
 » 5 weeks ago, # | ← Rev. 3 →   +25 In problem B, the statement "It is guaranteed that the sum of $n$ over all test cases does not exceed $2⋅10^5$" is misleading since it made me believe that for all possible inputs $x$ and $y$ \$(−10^9≤y
 » 5 weeks ago, # | ← Rev. 2 →   0 I don't understand what's wrong in my implementation of ternary search for the problem ASubmission — 193300171
 » 5 weeks ago, # | ← Rev. 2 →   +1 For me this is an inspiring contest with excellent B&E.And F itself is just a good problem at the wrong time.None of you done it on purpose,that's enough.I hope that it will not destroy your confidence and courage.