### Cirno_9baka's blog

By Cirno_9baka, 3 years ago,

Hello, Codeforces!

I'd like to invite you to take part in Codeforces Round #593 (Div. 2). It will held on Oct/17/2019 16:35 (Moscow time). The round will be rated for the participants with rating lower than 2100.

You will be given 6 problems and 2 hours to solve them.

Scoring distribution: 500—1000—1000—1750—2000—2500.

The problems of this round were developed by me. Thanks a lot to isaf27 for his excellent coordination, to Mike MikeMirzayanov Mirzayanov for Codeforces and Polygon platform, and to mnaeraxr, antontrygubO_o, NIWIS, win11905 for testing.

This is my first round ever. I hope everyone will enjoy it.

Good luck!

UPD: The round is over! Congratulations to the winners:

Div.1 + Div.2 participants:

Official participants:

UPD: Now the Editorial is available.

• +183

 » 3 years ago, # |   +54 It's the contest season again :D
•  » » 3 years ago, # ^ |   -38 Is it rated?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +19 The round will be rated for the participants with rating lower than 2100
 » 3 years ago, # |   +12 PS. I hope anyone record the process of preparing one problem with commentary, will publish it on Youtube after the contest. It's useful.
•  » » 3 years ago, # ^ |   +17
 » 3 years ago, # |   +69 Who else is going to make this contest a priority to gain back the rating points that we lost in Tourist's contest ?
•  » » 3 years ago, # ^ |   +18 I have a suspicion that contenst was just a measure to target rating inflation at Codeforces.
•  » » 3 years ago, # ^ |   +19 I hope I can do that. Good luck!
•  » » 3 years ago, # ^ | ← Rev. 3 →   +1 well,I did too badly on tourist's contest I don't think one contest is enough to make it up. Anyway,I wish you all good luck and high rating.
 » 3 years ago, # |   +25 Best of luck for your first contest
 » 3 years ago, # |   +20 How short the announcement is!However, hope your first round will be successful!
 » 3 years ago, # |   -44 Request for This contest :: Please make large inputs downloadable
 » 3 years ago, # |   0 Hope for a great contest as it’s your first time !
 » 3 years ago, # | ← Rev. 3 →   0 i wish it be safe from any hacker attack .. Cirno_9baka
 » 3 years ago, # |   +39 Do you think this round will be the strongest?
 » 3 years ago, # |   +3 I will try to wake up on time to participate. Now, I have a challenge: For every rating point lost, I will do one pull-up. For every point won I will do three pushups. Everyone is welcome to join the fitness challenge. Write what you'll do if you lose or win rating.
•  » » 3 years ago, # ^ |   0 I'll tag along! :D
•  » » 3 years ago, # ^ |   0 I'll die
•  » » 3 years ago, # ^ |   +19 I screwed up badly. This is gonna hurt.
•  » » 3 years ago, # ^ |   0 I owe you people 81 pull ups.
 » 3 years ago, # |   -30 Hope this contest increase my rating from 990 to 2100+. All the best.
 » 3 years ago, # | ← Rev. 4 →   +44 A bus left the Scarlet Devil Mansion; $a$ people boarded at the start.At Hakugyokurou, $b$ people left and $\frac{b}2$ people boarded. (It is guaranteed that $b$ is odd.)At Yakumo-san's house, $d$ people left, where $d$ is the imaginary solution to $ad^2 + bd + \sin c\pi = 0$.How many passengers remain? Print the answer modulo $993\ 244\ 853$.
 » 3 years ago, # |   +4 According to the writer's name, I bet this round may include some Touhou-themed problems.
 » 3 years ago, # |   +16 Good luck with your first contest!
 » 3 years ago, # |   +3 I smell math problems O_o
 » 3 years ago, # |   +2 UwU
 » 3 years ago, # |   -6 I hope the round contains some basic graphs problems
•  » » 3 years ago, # ^ |   +7 I hope this round does not contain strings problems
•  » » » 3 years ago, # ^ |   0 yeah seriously
•  » » » 3 years ago, # ^ |   0 Why?
•  » » » » 3 years ago, # ^ |   0 By strings I meant strings related some advanced DS or KMP etc. for a stupid and mean reason because I don't know about them. Though I should not worry about them because even if they are present, they will be in later half of the set.
•  » » » » 3 years ago, # ^ |   0 Btw since you are tester and your reply to this particular comment gives a hint that there will be some sort of strings related problems.
 » 3 years ago, # |   -9 Thanks for the contest :)
 » 3 years ago, # |   -9 Oh, maybe I'll become green after this round.
 » 3 years ago, # | ← Rev. 2 →   -6 [Deleted]
 » 3 years ago, # |   -11 i hope statements wiil be without anime
 » 3 years ago, # |   0 wish short problem not hard code good pretests and high ratings :)
 » 3 years ago, # |   -36 The comment removed because of Codeforces rules violation
 » 3 years ago, # |   +18 A speed typing test?
 » 3 years ago, # |   +71
 » 3 years ago, # |   +5 Speed Test :/
 » 3 years ago, # |   0 Was B meant to use OEIS???? How come B is on B? 1000???
•  » » 3 years ago, # ^ | ← Rev. 4 →   +7 PROBLEM B is (2^m-1)^nI TYPED THIS FOR SO LONG OK SO PLEASE READ https://pastebin.com/Qjr3h8Ui
•  » » » 3 years ago, # ^ |   +1 care to explain ?
•  » » » » 3 years ago, # ^ |   0 The number of ways to include the ith kind of item is the number of ways to pick k boxes out of the m boxes. Also, the number of ways of picking the ith kind of item is independent of the number of ways of picking the jth kind of item.
•  » » » » 3 years ago, # ^ |   +9 For each type you need to choose subset of boxes. And subset must be non-empty
•  » » » » 3 years ago, # ^ |   0 I have added explanation sorry it took me long time
•  » » » » 3 years ago, # ^ |   +2 The idea es the following: If we only focus on a certain number, we have clearly (2^m)-1 possible options. This is because any box can be either "full" or "not full", this is, with the number on it or without it. We substract 1 because we don´t consider the case in which every box is "not full". Then, as we have n possible numbers, for every number we have (2^m)-1 combinations, resulting in ((2^m)-1)^n.
•  » » 3 years ago, # ^ |   0 My answer is (2^m — 1)^n
•  » » » 3 years ago, # ^ |   0 How did you come up with this solution?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +3 We need to distribute every present to at least one box ie (2^m — 1) (-1 because you remove the case where all boxes dont have this present)We do this for every present... hence: (2^m — 1)^n
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 correct, click here for the solution
 » 3 years ago, # |   +13 How to solve F ????????????????????????????????????????????????????????????????
 » 3 years ago, # |   0 How to solve D?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +7 Seems like the doll's trajectory is a spiral from $(1,1)$ to the center, therefore the obstacles must only be in the end of the spiral (or form complete rows / columns on the bounds of the grid).If this is the case, I don't know how to code it neatly and concisely.
•  » » 3 years ago, # ^ |   0 The path must be a spiral... somehow. "Simply" check if one can run that way.
•  » » » 3 years ago, # ^ |   0 Isn't that O(nm) which is 10^10?
•  » » » » 3 years ago, # ^ |   0 You don't actually visit each cell. On each row (or column), you just move to the end of the row, which means finding the first obstacle hit, or the last column not yet hit. This is O(lg k) time (binary search the obstacles on the row). So, each row or column is O(lg k) time, and each row/column is done only once, so total time is (m+n)(lg k).
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   0 No. You run from (1,1) to (1,n-1), then to (m-1,n-1), then (m-1, 1)... And so on.It loops 1e5 * 2 times.One can use two sorted lists of the obstacles to optimze the search.Sort one list by colums, one by rows. Ie use vector>, onc sorted by first, one sorted by second, then first.To check if all fields where visited, count them. Fieldcount + k == n*m
 » 3 years ago, # |   0 How to solve D ?
•  » » 3 years ago, # ^ |   0 The first observation would be that if there is a solution, then the path will look like a clockwise spiral. The second observation would be that we don't have to simulate each step. Instead we should simulate all the steps in one direction in one move.Let's initialize the variables n1 = 1, n2 = n, m1 = 1, m2 = 2 the borders of submatrix we should be able to visit. Also let's keep sets on each line/ column in order to store the obstacles on those lines/ columns. Now let's say we're at position (i, j) and just changed direction to move to the right. If there is an obstacle in our way at position (i, k), with k from [j + 1, m2]), then we can only ever reach column k — 1. Thus m2 will become k — 1. Moreover, a solution exists only if the submatrix ((i, k), (n2, m2)) is filled with obstacles, else there is no solution. We can easily check this using our COLUMN sets (i.e. if a column k -> m2 has exactly n2 — n1 + 1 elements then it is filled with obstacles, else not). To be able to make correct checks in the future, we will remove all these obstacles found in the said submatrix from their corresponding LINE sets. Now we can update n1 to n1 + 1 (since we will never return to this line), update the doll's position from (i, j) to (i, k — 1) and change the direction to moving downwards. Everything works in a similar way for the other directions.We know we reached the end if the number of steps taken + the number of elements removed == n * m.
•  » » » 3 years ago, # ^ |   0 yaa, right. the problem was full of simulation and implementation.
 » 3 years ago, # |   +162 Perfectly imbalanced.
•  » » 3 years ago, # ^ |   0 Did you find what is test case 4?
•  » » » 3 years ago, # ^ |   0 There was a problem in the logic of my solution, and I found that the actual solution will require much heavier implementation, so I couldn't make it in time.
 » 3 years ago, # |   +91 This was perfectly imbalanced round.I really hope the problem D has some pretty and easy to implement solution.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 Yeah I agree; the one I was thinking of was really nasty to implement (lots of if cases and room for error) so i figured it wasn't worth it given how much time I had left. Watch there be some 5 line mathematical solution lol ;P.
•  » » 3 years ago, # ^ |   +5 Indeed, I've figured the spiral logic, had 140+ lines of code but I was still writing code 5 minutes before the time ended.
•  » » 3 years ago, # ^ |   +3 Basically we have to check the frame and blocked and one central blocked component.Heavy implementation !!!
•  » » » 3 years ago, # ^ |   +2 If it was so easy then why didn't you submit it? Oh, I understood...
 » 3 years ago, # | ← Rev. 6 →   0 Greedy solution for $D$:Keep going in the direction you are facing until you have to change it. When you can't move anymore, see if you covered all squares, if you did, answer is yes otherwise answer is no.Try to prove this.Implementation: 62820909Edit: Why the downvotes?
•  » » 3 years ago, # ^ |   0 Correct. But hard to implement, as N, M <= 10^5, which makes it impossible to mimic every step.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 I implemented the simulation by C++ upper_bound but I am missing some cases.Edit: I just realized that I had just forgotten to replace a $x$ by $y$ after copy-paste. Got AC now. :(
•  » » » » 3 years ago, # ^ |   0 I also implemented using upper_bound but got TLE on case 4
•  » » » » » 3 years ago, # ^ |   0 Cool. It's the first time I've heard of this method... Silly me implemented a sort of binary searches.
•  » » » 3 years ago, # ^ |   +3 It was indeed a pain to implement. But, you don't have to visit every cell. Just determine how far you can travel on that row/column.I used binary search to find the next obstacle on that row/column, and then just moved that many spaces (or, until I had reached a previously hit row/column). So, total time is just (N+M)lg(K).Still this was very annoying, and I ended up just copying sets of code 4 times to handle the different directions; not at all elegant.
•  » » » » 3 years ago, # ^ |   0 And you check whether you cover all cells by (N*M — K — cells_visited)?Nice move! I even write a function to confirm a rect is filled by obstacles and proved the overall complexity is O(klogk)...
 » 3 years ago, # |   +87 problem C feels like "dont know why does it work but gonna send it anyway"
•  » » 3 years ago, # ^ | ← Rev. 3 →   +2 The problem C reminds me of printing snake print of a given matrix. If n is 3, then insert elements till n**2 (i.e. 9) in spiral order in a 2D matrix: 1 6 72 5 83 4 9Finally, print it. As simple as that
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 in problem C , if n = 2 then x = { 1,3 } y = { 2 , 4 }f( y , x ) = { 2->1 , 4->1 , 4->3 } then ans should be 3 , why ans is 2 ? i am stuck in that please help me out
•  » » » » 3 years ago, # ^ |   0 If n = 2 then x = {1,4} y = {2,3}. If n = 2, then n**2 = 4. Try inserting 1 to 4 elements in a 2X2 matrix in top to bottom snake pattern. 1 42 3Check snake pattern
•  » » » » » 3 years ago, # ^ |   0 Thanks :-)
•  » » 3 years ago, # ^ |   +1 Yeah the problem was too wordy so I skipped straight to the example, figured out a weird pattern, coded it up super fast, and watched it get passed pretest with disbelief. I was fully expecting a WA but I got lucky o_o.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +10 So, i can prove it. Let's explore f(X,Y) and f(Y,X). Of course, f(X,Y)+f(Y,X)=n^2. so max value of min(f(X,Y),f(Y,X)) is (n^2)/2. So, (n^2)/2 is our top estimate.Let's try to reach it. Let's build an example, where min(f(X,Y),f(Y,X))=(n^2)/2. (for any X,Y) This way, I divided n^2 labs at n sequential sectors. Let every sector is a permutation of {1,2,3,4..n}. So we have sequence A, A.size = n^2. This sequence means that lab with index i has group number A[i]. Let's take two random groups X,Y. Understand, that for each sector water can go from A[x] = X to every A[y] = Y where (sector of index y)<(sector of index x). So, f(X,Y)>=n*(n-1)/2 Likewise, f(Y,X)>=n*(n-1)/2. (observe that n*(n-1)/2 + n*(n-1)/2 = n^2-n, that is we lost n pairs). ok, we didn't explore such A[x]=X, A[y]=Y, where (sector of index y)=(sector of index x) Here is n pairs. And we need to distribute them roughly in half between f(X,Y) and f(Y,X) to maximize min(f(X,Y),f(Y,X)). So, in roughly half sectors $xy$. My solution is to make sectors such way: sector1 = {1,2,3,...n}. sector2 = {n,n-1,...,2,1}. sector3 = {1,2,3,...n}. sector4 = {n,n-1,...,2,1}. ...Easy to see that we reached our purpose: in roughly half sectors $xy$, for every groups X,Y, where A[x]=X, A[y]=Y. After writing this solution you can see that it will be a number-snake in answer table.
 » 3 years ago, # |   0 How to solve B? I've used b*(2**a)+1 formula but getting TLE
•  » » 3 years ago, # ^ |   0 (2^m-1)^n remember to use fastpow
•  » » » 3 years ago, # ^ |   0 Can you exaplain how did you reach this equation ?
•  » » » » 3 years ago, # ^ |   0 Sum of binomial coefficients i.e. nC0 + nC1 + ... + nCn is equal to 2^n. This is a common property of binomial coefficients.
•  » » » » 3 years ago, # ^ |   +1 for the situation of n=1 obviously the answer is 2^m-1(all have 2^m situations, but the situation of all of m is none is incorrect) So when n is greater than 1, the answer is multiplication of n numbers which is 2^m-1.
•  » » » » 3 years ago, # ^ |   0 It's like suppose there is a ball. Now for every box, I have 2 choices to make whether to put that ball in it or not. So 2^m for m boxes. Now this includes a way where we haven't put that ball in any box. Hence, allowed ways — 2^m — 1. Now,since there are n such balls therefore ( 2^m — 1) ^n
•  » » » 3 years ago, # ^ |   0 i used the same thing but wrong answer on pretest 3
•  » » » » 3 years ago, # ^ |   0 Maybe your fastpow is error
•  » » » » » 3 years ago, # ^ |   0 i changed long to long long and it worked .Can u explain whats the need of long long?
•  » » » » » » 3 years ago, # ^ |   0 emmm, In fact,long has the same range as int while the answer which mod 1e9+7 may be large（near by 1e9). So your data may overflow in your code of fastpow. Check your code and you will find there will be some multiplication which makes your data overflow
•  » » 3 years ago, # ^ | ← Rev. 8 →   0 you were close, i also did the same at first but got WA on test case 3.after that i realize that, for 1 item the probability is 2^m — 1, what about 2 item? just multiply both of it (2^m-1) * (2^m-1). since n = 2^19, iterate it would be TLE.so the solution is (2^m-1)^n and don't forget to use Modular Exponentiation
•  » » » 3 years ago, # ^ |   0 Did same thing, still got a WA on pretest 3 https://codeforces.com/contest/1236/submission/62811911
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 it's on here 8th line mul = ((mul%mod)*(base%mod))%mod it should be mul= mul*mul not mul = mul*base
•  » » » » » 3 years ago, # ^ |   0 Thats a really novice mistake :( . Thanks for pointing out
 » 3 years ago, # | ← Rev. 3 →   +1 I submitted my solution just before the contest ended and I got an idleness limit exceeded. What does this mean? Link 62815630
•  » » 3 years ago, # ^ |   -7 lol
•  » » 3 years ago, # ^ |   0 Turns out the cerr in my code caused it. Weird..... 62821549
 » 3 years ago, # | ← Rev. 2 →   +11 How to solve E?I tried to solve it with DP, but my table dimensions were too big, which was something I couldn't reduce ...Even though I agree the problems were not really balanced in terms of difficulty, I liked them a lot (especially D and E seem to be very interesting and I'm looking forward to read the editorials).
 » 3 years ago, # |   +15 After a perfectly balanced round, comes a perfectly unbalanced round.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +25 N(balanced)== N(imbalanced) -> perfectly balanced
 » 3 years ago, # |   +3 It took me 15min to undertand statements of Problem E...
•  » » 3 years ago, # ^ |   0 Quite amazing I took 25 mins.
•  » » 3 years ago, # ^ |   +13 It took me 0 minutes to understand E coz I didnt even read it
 » 3 years ago, # |   +15 I think this round is very imbalanced, because tester's team mainly consists of div1 persons
•  » » 3 years ago, # ^ |   0 That's why more people solved C than B
 » 3 years ago, # |   +42 Me after solving A,B,C:This round doesn't seem to hard. Promblem D:I'm going to end this man whole carrer.
 » 3 years ago, # |   0 touhou round so hard q.q What is test 7 in D?
•  » » 3 years ago, # ^ |   0 Really hard :/
 » 3 years ago, # |   +60 D is a debugging nightmare...
•  » » 3 years ago, # ^ |   0 It would be worse if pretests is weak..I submited 4 times to pass the pretests...
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +14 Nonetheless, LayCurse managed to pull off 5 hacks in a room of yellows and reds, with only 9 submits for D..
•  » » » » 3 years ago, # ^ |   0 And I just found my submission failed at m = 1, n > 1....
 » 3 years ago, # | ← Rev. 2 →   0 Why is this code getting TLE in problem D? Code I used binary search for the current location and changed the location accordingly.
•  » » 3 years ago, # ^ |   0 Do you have an infinite loop for most grids? That's the mistake I made and this looks similar. Try input 5 5 0, for example.
•  » » » 3 years ago, # ^ |   0 Infinite loop for this case :/ Thanks!
 » 3 years ago, # |   0 Can someone please explain how did you come up with (2^m -1 ) ^ n for B?
•  » » 3 years ago, # ^ |   -8 Sum of binomial coefficients i.e. nC0 + nC1 + ... + nCn is equal to 2^n. This is a common property of binomial coefficients.
•  » » 3 years ago, # ^ |   +3 From input explanation you can see that there is 2^m — 1 ways to divide one present to m people. All n presents have the same amount of combinations so from here answer is (2 ^ m — 1) ^ n
•  » » 3 years ago, # ^ |   0 consider present type x: you have 2 options for each box to put present in it or not. so in total you have 2^m options but one of the at least should not be empty so 2^m-1.and each of present types are independent from each other (do same procedure for all types) so (2^m-1)^n.
 » 3 years ago, # |   +13 fot problem E it takes me almost 60 minutes to find the trap it turns out to be the situation that n=1.
 » 3 years ago, # |   0 didn't like problem c so tried to solve D. tried for 70 mins solved it 5 min after contest was already over smh . should have just sticked to C.
 » 3 years ago, # |   +8 For E is it correct that for any x the pairs (x, y) that satisfy will be such that all the possible y's for that x will be continuous integers ? Like (3, 1), (3, 2), (3, 3) where x is 3 and y belongs to [1,3]?
•  » » 3 years ago, # ^ |   0 Yes, since after reaching a position y you can always stay there by moving right if ai = y, and moving back after the last one, stay there for the rest of the cases. However I got stuck on finding maximum and minimum y
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 Ya, I realised my solution failed on pretest 15 since I didn't consider N = 1 case.Anyways here's the solution to find the maximum and minimum:The brute method is to increase/decrease whenever possible. Brute Code for(int i = 1; i <= n; i++){ int X = i; for(int j = 0; j < m; j++){ if(a[j] != X + 1) X++; } X++; maxi[i - 1] = min(n, X); X = i; for(int j = 0; j < m; j++){ if(a[j] != X - 1) X--; } X--; mini[i - 1] = max(1LL, X); } To optimise this we can create an array of size M that says for each position p if we have a number equal to A[p] at that point what's the max or min I can get at the end. This can be calculated in M log M. We can use the same array to find for each number what's the max/min I can get if i start with it. code that fails on pretest 15#include using namespace std; #define int long long #define MAXN 100005 int n, m; vector a(MAXN); int maxi[MAXN], mini[MAXN]; int X[MAXN], Y[MAXN]; unordered_map > mxpos, mnpos; int MX(int P){ if(X[P] != -1) return X[P]; int num = a[P] - 2 - P; // at -1 -> a[p] - 1 - p - 1 int posi = upper_bound(mxpos[num].begin(), mxpos[num].end(), P) - mxpos[num].begin(); if(posi == mxpos[num].size()){ // cout << P << '\n'; return X[P] = a[P] + m - P - 1; } return X[P] = MX(mxpos[num][posi]); } int MN(int P){ if(Y[P] != -1) return Y[P]; int num = a[P] + 2 + P; // at -1 -> a[p] - 1 - p - 1 int posi = upper_bound(mnpos[num].begin(), mnpos[num].end(), P) - mnpos[num].begin(); if(posi == mnpos[num].size()) return Y[P] = a[P] + 1 - m + P; // cout << P << '\n'; return Y[P] = MN(mnpos[num][posi]); } signed main(){ cin >> n >> m; for(int i = 0; i < m; i++){ cin >> a[i]; X[i] = Y[i] = -1; mxpos[a[i] - 1 - i].push_back(i); mnpos[a[i] + 1 + i].push_back(i); } for(int i = 0; i < m; i++){ MX(i); MN(i); // cout << X[i] << ' '<< Y[i]<< '\n'; } // cout <<"MXMN\n"; for(int i = 1; i <= n; i++){ if(mnpos[i].size() == 0) mini[i - 1] = max(1LL, i - m - 1); else mini[i - 1] = max(Y[mnpos[i][0]], i - m - 1); if(mxpos[i].size() == 0) maxi[i - 1] = min(n, i + m + 1); else maxi[i - 1] = min(i + m + 1, X[mxpos[i][0]]); mini[i - 1] = max(1LL, mini[i - 1]); maxi[i - 1] = min(n, maxi[i - 1]); // cout << mini[i-1] << ' '<
•  » » » » 3 years ago, # ^ |   0 Man I thought an array like so might not be able to transition but after reading your idea I wrote it on paper and yes it can be calculated in M * logM. Thanks.
 » 3 years ago, # | ← Rev. 2 →   +113 Disgusting problem D
 » 3 years ago, # |   +20 For everyone waiting for system tests: there's a new twice mv out now https://www.youtube.com/watch?v=zQELp93xxfo
 » 3 years ago, # |   -46 Amazing Round .
•  » » 3 years ago, # ^ |   +26 is this a joke?
 » 3 years ago, # | ← Rev. 2 →   +40 Although deriving formula for B is not that hard (just in my opinion), I think it was not appropriate to put such problem in Div2B since it requires fast exponentiation.
•  » » 3 years ago, # ^ |   +8 correct. B should have been easier than this one. C should be D. D = E.
•  » » 3 years ago, # ^ |   0 How about python? Time to learn a new language
•  » » » 3 years ago, # ^ |   0 python does binexp?? I just wasted 15 minutes debugging my bin exp in python3 X(
•  » » » » 3 years ago, # ^ |   +3 pow(a,b,m) returns a^b mod m :D
•  » » 3 years ago, # ^ |   0 I think the formular is unreachable if one has to figure it out by himself.I tried to come up with a solution for n=1, and did not found it. After seeing the formular here in the comments it is fairly simple to implement it.
 » 3 years ago, # |   +12 I meet a strange bug when using m2.codeforces.com:The statement of A says 'The statement is not available'.So I think there're some technical issues and throw A away...I didn't realize the problem until I looked at the standings after one hour!
•  » » 3 years ago, # ^ |   0 I faced the same then i thought that this contest might not be available at m2 .
•  » » 3 years ago, # ^ |   +3 The same here. However, this is a lesson for you to open every problem before solving any of them.
•  » » 3 years ago, # ^ |   0 Always have both the main site and a light version open. Main site gets attacked, light site has bugs.
•  » » » 3 years ago, # ^ |   +14 Main site gets attacked, light site has bugs balanced?
•  » » » 3 years ago, # ^ |   +9 Main site gets attacked, light site has bugs. However if both happen, it's imbalanced. (I used the light site because I can't get connected to the main site during the contest, at least in the first 5 minutes...
 » 3 years ago, # |   +113 Who else forgot n=1? :)
•  » » 3 years ago, # ^ |   +23 It is glad to see that the author determined to make the $n=1$ case in the pretests. Or there will be plenty of FSTs, for example, me.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Totally agree. :) I'm glad that pretest 15 was there to block me early.(And pretest 14 reminded me to use a long for the answer, lol).
•  » » » » 3 years ago, # ^ |   -25 Your D failed in 218 case. Its disgusting
•  » » » » » 3 years ago, # ^ |   0 D is Disgusting anyway
 » 3 years ago, # | ← Rev. 2 →   0 WHEN I SAW problem B ![ (https://images.app.goo.gl/H9q9HbBeTSCQTjVS8)]WHEN I SAW PROBLEM C ![ (https://images.app.goo.gl/P7HnpmTw4LKifK2J8)]
 » 3 years ago, # |   0 Waiting for the editorial!!
 » 3 years ago, # |   0 Red coders should stop making Div2 only contest. Their contests are so inbalanced. :(
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 In my opinion the imbalance matters because solving a harder problem differentiates the people who are skilled and not skilled. For example, tmwilliamlin168 is extremely skilled so he always solves more problems than me. tmw OFZ.
 » 3 years ago, # |   +19 I missed the DDOS attack this round :(
 » 3 years ago, # | ← Rev. 2 →   +7 Upvote if you got the solution to C from sample
•  » » 3 years ago, # ^ |   0 I believe everyone did lol
 » 3 years ago, # |   0 If I get to 1400 rating I change colour right? OMG I might get there plz
•  » » 3 years ago, # ^ |   0 good luck bro :D
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +1 testREEE LETS GO YEEEE MINECRAFT
 » 3 years ago, # | ← Rev. 2 →   0 Deleted
 » 3 years ago, # | ← Rev. 5 →   0 62815596Can somebody explain (TASK D) why this is not correct?First I remove full lines with block (right and bottom)Next I check that all remaining blocks in tail of snake-filled arrayfor example if left 3x3 array and two blocks, I check that this blocks in 8 and 9?Is it correct? Or idea was wrong1 2 38 9 47 6 5upd. I think I understand, I need to delete all left vertical lines with all blocks except 1 row...
 » 3 years ago, # |   +22 Aaaaaaaannndddd.... WA218!
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   -39 Congratulations with your first contest! Congratulations with your last contest too!
 » 3 years ago, # |   0 Can you explain your thought process for B?Like from when you saw the problemIMO C was easier than B
•  » » 3 years ago, # ^ |   0 I tested with examples, noticed that we needed to assign one present to someone for each type and listed out the ways for the rest.My kinda messy (not the smartest but i guess easy to understand) explanation https://pastebin.com/Qjr3h8Ui
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 B is quite clearly a math problem (very large input parameters, O(n) fails, reads like combinatorics), so the idea would be to try and derive a formula to solve B.My solution used inclusion-exclusion and was very messy, but the expression simplifies quite nicely to the simple formula.Edit: So you count all the ways to distribute the gifts without considering whether every gift is used, to get 2^NM ways, and then you consider the case where at least one gift is not used, and then the case where at least two gifts are not used, et cetera. The result is a well-known expression (binomial theorem), so you can get (2 ^ M — 1) ^ N.
 » 3 years ago, # |   -14 problems are very interesting. I really like it!
 » 3 years ago, # |   0 Can someone verify if the following logic is correct for D?If we just consider all obstacles, they're also going to form a spiral path. We can fix one obstacle and break this path down into two spirals: — a clockwise spiral path and an anticlockwise spiral path. So, we start from this obstacle and simulate the moves, the clockwise starting from direction 1, while the anticlockwise starting from direction 3. If we can cover all the K obstacles in either of the 2 (disjoint) spiral paths, it's a valid input.
•  » » 3 years ago, # ^ |   0 i do not think anti-clockwise path is a valid one....
•  » » 3 years ago, # ^ | ← Rev. 3 →   +4 No, I think the obstacle doesn't have to form a spiral path always. Consider the following grid: (1 = Obstacle, 0 = Empty)0 0 0 0 10 0 0 0 10 1 0 0 10 0 0 0 1
•  » » » 3 years ago, # ^ |   0 Got it, thanks!
 » 3 years ago, # |   +6 I guess that one Specialist tester wasn't enough. But I have to say, that I like these problems. F seems to be interesting.
 » 3 years ago, # |   -7 Why problem creators make such problems as C? there is no any logic just like guess output and get AC. I think at least 95 percent of participants solve it so. I dont like this round for me the tasks were uninteresting and disbalanced.
 » 3 years ago, # |   +135 Sorry for the difficult problem D.I thought it may be just a simulate problem and may not so hard, but the fact isn't. It contains many details and not so easy to write.Again I will say sorry. I will try to improve myself on controlling the difficulty of the problems.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +2 I submitted at last minute. So, I am scared of TC218.UPD: Accepted with 6 TLE attempts..XD
•  » » 3 years ago, # ^ |   0 So what is the content of test #218? Is it pre-determined or from hacking?
•  » » 3 years ago, # ^ |   +6 You will do better next time， keep it up
•  » » 3 years ago, # ^ |   0 I believe that the main problem with it was the weak pretests, if test 218 was in the pretests, maybe the percentage of AC would be way more different :/
•  » » 3 years ago, # ^ |   +39 I think the main issue of this round not problem D. It was pretty hard to implement but doable. But the problem C is not a good problem for such round. I'm pretty sure that 90% of AC on this are just "hm, I consider some pattern in the output, what will happen if I submit it? Oh, AC, great!". Almost nobody proved this solution during the contest and this turned out the problem to finding the pattern faster than others.
•  » » » 3 years ago, # ^ |   +72 Problem C rewarded people who were like "Let's try this non-sense first and then think more" and punished people who were like "Let's think first, if no ideas, try some non-sense".
•  » » » 3 years ago, # ^ |   0 Exactly my thought. Seemed to be a very Codechef-esque problem (at least for me). Every time in the Div 1 long challenge, they give one of the first 3 problems like this. But, at least, they give 10 days to think. Lol.
•  » » 3 years ago, # ^ |   0 My problem with D was that I didn't realise every cell can only be visited once until the clarification came.
 » 3 years ago, # | ← Rev. 2 →   0 Anyone got what pretest 4 is? Please share
 » 3 years ago, # |   0 How to solve E?
•  » » 3 years ago, # ^ |   0 Observe that the reachable points for each starting point form a continous interval. Say that for each starting point, we want to know the farthest point to the left it can reach, which can be done by each time make one move to the left if possible. We can simulate the process in $O(n)$ by maintaining the number of starting points at each current position.
•  » » » 3 years ago, # ^ |   0 Is true, you just need to calculate the most away reachable point to the left and right of each position. But how can you make it in O(n) time. I think about using ST to simulate it, but it turns into a complicated implementation, can you explain me how to solve the problem using your idea?
•  » » » » 3 years ago, # ^ |   +10 Process every position in parallel. Each time every position should move to the left except one. This should lead to an $O(n)$ implementation.
 » 3 years ago, # |   +26 If anyone is curious, I suspect test 218 for problem D is something along the lines of:3 1 1 3 1The correct answer is Yes, but many solutions are printing No, because on your first step you can't make any steps to the right. However, that's not an issue here because you can immediately turn right (so you're now facing down) and move down one step. I tested a few WA218 solutions on this case and found that they all printed No here.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Yeah, my solution fails on 218 and fails locally for 5 1 0. :(Edit: resubmitted with a fix for this and got AC.
•  » » 3 years ago, # ^ |   0 Yes, it has to be the case where you are expected to take a turn at the starting cell itself.
•  » » » 3 years ago, # ^ |   0 Yeah. My code also failed this test case. Although they should have added this test in pretests itself.
•  » » 3 years ago, # ^ |   +139 The person who hacked someone with this test is Thanos of our generation. With one click he killed half of AC solutions on D.
•  » » » 3 years ago, # ^ |   +1 I got hacked with this during the round, so they were someone in my room. Only andrew and neko_nyaaaaaaaaaaaaaaaaa had hacks in my room, so it was one of them :P
 » 3 years ago, # |   +8 Hard code for D and Good test 218
 » 3 years ago, # | ← Rev. 2 →   +8 The absent of test case 218 in pretest seems to f**k participants up deliberately, right?edit/ I didn't get that 218 was hack data. It seems that it was not deliberation, just failure to consider corner case
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 me too. 0 1 1 1 1 \n 0 1 1 1 1 \n 0 1 1 1 1 \n 1 1 1 1 1 \n 1 1 1 1 1 \n it should be moving from {1, 0}
 » 3 years ago, # |   +59 After the contest ended, I received an e-mail from noreply@codeforces.com saying that my solution for problem A 'significantly coincides' with a solution from other user. I entered his profile that was on the e-mail and checked his solution. It is quite similar, it uses the same idea, but this is a simple ad-hoc problem, and I'm pretty sure a lot of other people must have made similar solutions. Anyway, the email said "If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details". Well, there obviously was no source published before the competition, and I just solved it by myself, and considering it was an easy problem I'd not be surprised that many similar solutions exists. What can I do? I'm from Brazil and that profile is from a random guy in China, and as it was the easiest problem and most people solved it pretty quickly there's no way we would have gotten the same code on purpose. The e-mail says "Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.". But it wasn't a violation, obviously a problem that occured, what could I do to remove this violation?
 » 3 years ago, # |   +31 The round was quite unbalanced. My friend has got only 72 points more than me, but he's 500 places higher. Guess the author should learn from tourist how to make BaLaNceD contests.
 » 3 years ago, # |   +17 There is no test case against int overflow in D...
 » 3 years ago, # |   0 Can someone explain problem B pls?
•  » » 3 years ago, # ^ |   0 We can take every present into account separately. There are totally 2^m ways to place. Obviously, we can not take the way of "all the box is empty", so there are (2^m-1) reasonable ways. Every present is irrelevant. So we can get the answer : (2^m-1)^n
 » 3 years ago, # |   -21 C was patheticShouldnt have given the example. Everyone got it correct.
 » 3 years ago, # | ← Rev. 2 →   +4 i solved B using,total ways — invalid ways, i calculated invalid ways using inclusion-exclusion principle, which is sum r=1 to n ( nCr * 2^((n-r)*m) — 1)* (-1)^(r+1) which reduces to (2^(m*n) — (2^m-1)^n — 1) also total ways = 2^(m*n) — 1 .......substracting 1 for empty sequence hence valid ways = total ways — invalid ways = (2^m-1)^n.
 » 3 years ago, # |   0 Hey, can any of you guys help me with problem C ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 first thing to notice that is highest numbers must be in one column,then as first row gets bigger number then put lowest in it, this is the most optimal way to put numbers.do it column by column.
 » 3 years ago, # |   -8 Java BigInteger became useful for problem B. I used the same formula (2^m-1)^n. Here's my JAVA code: 62824862
•  » » 3 years ago, # ^ |   +3 "Quick Pow with Mod" may be useful for you.
 » 3 years ago, # |   0 Aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa(found a mistake in D after 50 min debugging during the contest and 2 hours after the end)
 » 3 years ago, # |   +3 Sorry to bother you. Today (yesterday?) At the contest, someone coder_aditya copied my decisions from the open (I confess, it's my fault) source in ideone. So, this unscrupulous user completely copied my decisions on Problem A (62787915 and 62785873) and on Problem C (62803225 and 62803022). For an unclear reason, he first sent out full copies (why ???) and then edited the original code with trivial changes, receiving OK for tasks A (62813924) and C (62814398). In addition, task B was also counted as accomplished from him, so I won’t be surprised if he stole it from someone. I ask you to take action, because in the end I was left without a rating, and after editing other people's decisions he got a little rating.
 » 3 years ago, # |   0 Finally back to purple!!!
 » 3 years ago, # | ← Rev. 2 →   0 I want to ask a question, why the testcase's answer is no? 4 7 8 2 2 2 3 3 2 3 3 2 5 2 6 3 5 3 6 It starts from (1,1) and turn right at (1,7).After walking across the big circle, it returns to the original point (1,1). then it goes on and turn right at (1,4) and end at (4,7).All points has been visited. And at every point it turns right at most once.Do I misunderstand the problem?
•  » » 3 years ago, # ^ |   0 The announcement specifies that you can only visit each cell once."The doll should visit all cells without obstacles exactly once"
•  » » » 3 years ago, # ^ |   0 Thanks for your answer!But If the problem becomes what I said, what's the answer?I have an idea, but I don't know whether it works / how to prove it. check how many components it has, it must equals to 1 check how many points with one degree, (1,1) is not included. If there are two or more. We get "no"
 » 3 years ago, # |   +10 Congratulations to you and me both for our first contest.
 » 3 years ago, # | ← Rev. 2 →   +4 Great conto
 » 3 years ago, # |   -10 Hello MikeMirzayanov and Cirno_9baka. So my friend dewitast got an issue that her rating was changed when she participated in this contest. You can see that, she is not eligible for div 2 rated contest (she already master when joining this contest, of course you can check it by yourself in the last contest in her profile). She already contacted both of you and she haven't hear any good news from you. Well she is not a vocal person, so I'm here to help her. Thanks :)
 » 3 years ago, # |   +3 I was checking the solution for problem D of some people and I found that one of the accepted solution fails the following input. Input:2 2 11 2This input should give an output "No", as I have checked with some other accepted solutions. But the following AC submission gives "Yes" :|