### djm03178's blog

By djm03178, 2 months ago, ,

안녕하세요, 코드포스! (Hello, Codeforces!)

We're glad to introduce you to Codeforces Round #578 (Div. 2), which will start at Aug/11/2019 15:35 (Moscow time). The round is rated for Div. 2 participants.

You will be given 6 problems and 2 hours to solve them. The score distribution will be announced later.

The problems are prepared by hyunuk and me.

Thanks to pllk, Learner99, Rox, mohammedehab2002, cheetose, jh05013, rkm0959, edenooo, and alex9801 for testing the round. We would also like to specially thank to KAN and arsijo for coordinating the round, and of course, MikeMirzayanov for Codeforces and Polygon platform.

This is our very first round, so I hope you enjoy it a lot!

UPD: The scoring distribution is 500 — 1000 — 1250 — 2000 — 2000 — 2500

UPD2: The contest is finished. Thanks for joining us! Here's the editorial.

UPD3: Congratulations to the winners!

Div. 2

3: ccf_n0i

4: 2om_neek

Unofficial Div. 1

1: kcm1700

2: uwi

4: kmjp

5: KrK

• +583

 » 2 months ago, # |   -6 Waiting for a good round.
•  » » 2 months ago, # ^ |   +40 You are also waiting for some upvotes, aren't you
•  » » 2 months ago, # ^ |   +81 You definitely should participate, every contest coordinated by arsijo is an ACE (absolutely cool event).
•  » » » 2 months ago, # ^ |   +35 that's true, there are so many Supreme Hilarious Ideal Triumphant contests coordinated by him.
•  » » » » 2 months ago, # ^ |   0 You’re just another hater. All you can do is to write hateful comments.
 » 2 months ago, # |   -44 Why can a user with rating $-40$ be the tester of a round? That's totally unfair! I don't want to take part in this round!!!!!!
•  » » 2 months ago, # ^ |   0 If you think it's unfair, you shall try to get your rating to -40. You'll find it very difficult.
•  » » 2 months ago, # ^ |   +53
•  » » » 2 months ago, # ^ |   0 Mean no offence, but does this kind of behaviour give any joy
•  » » 2 months ago, # ^ |   +26
 » 2 months ago, # |   +35 BTS bring me here!!
•  » » 2 months ago, # ^ |   +2 lol
 » 2 months ago, # |   +36 I'm your fan
 » 2 months ago, # |   +35 It's a friendly contest time for us Chinese :)
•  » » 2 months ago, # ^ |   -22 agree，同意同意
•  » » » 2 months ago, # ^ |   -25 don't agree，不同意不同意
•  » » » 2 months ago, # ^ |   0 Yeah , Not too late
•  » » 2 months ago, # ^ |   +1 Haha, I also think so. I hope we can enjoy the contest.
•  » » 2 months ago, # ^ |   -8 I can't agree more!
•  » » » 2 months ago, # ^ |   -9 Absolutely Correct.
•  » » 2 months ago, # ^ |   -7 agree
•  » » 2 months ago, # ^ |   0 It's a human race.
•  » » » 2 months ago, # ^ |   0 But there aremany Chinese .
 » 2 months ago, # |   0 Wow! Korean Round!
 » 2 months ago, # |   +50 Since our hopes were shattered last time, we hope that this time is different.
•  » » 2 months ago, # ^ |   0 Shattered again :(
 » 2 months ago, # |   +1 Man, such a friendly time for us Chinese!
•  » » 2 months ago, # ^ |   0 agree
•  » » 2 months ago, # ^ |   0 Agree++
 » 2 months ago, # |   -20 the success key for this contest is to avoid "string" word.
 » 2 months ago, # |   +12 Hope the difficulty distribution is reasonable this time :)
 » 2 months ago, # |   0 I hope the problems are enjoyful.
 » 2 months ago, # |   +3 Winner Winner Korean round dinner!
 » 2 months ago, # |   +18 BST(Binary Search Tree) bring me here!
 » 2 months ago, # |   +30 I want to become purple！I've been waiting for it for a long time!
•  » » 2 months ago, # ^ |   +25 Good luck to you!
•  » » 2 months ago, # ^ |   -35 You'll never become purple!
•  » » 2 months ago, # ^ |   -80 Hey guy, stop dreaming, you become gray instead of purple.
•  » » » 2 months ago, # ^ |   +17 Hey unrated guy, stop dreaming, you'll never let others become gray.
•  » » » » 2 months ago, # ^ |   +12 Aren't you the same people?
•  » » » » » 2 months ago, # ^ |   0 yes, they are
•  » » 2 months ago, # ^ |   +6 Wish your high rating!
 » 2 months ago, # |   0 Too much new problem setter rounds recently.
 » 2 months ago, # |   +89 Good tester
•  » » 2 months ago, # ^ | ← Rev. 2 →   +48 It was all done intentionally ; look at his max rating (1700+) . some people dream to be 1700+ ,and he wasted all his hardwork just for fun ... really a inspirational guy :-D
•  » » » 2 months ago, # ^ |   +48 It was the opposite, sadly. Participating in short contests turned out to be too stressful for me, so I did this instead. Now I have changed and I don't really care about messing up a contest anymore, so I might start getting an actual rating someday using a different handle.I also wanted to see if the rating just goes down forever. It doesn't; at this point my rating goes up even if I don't solve anything.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   -28 So why do you use Codeforces? Almost all contests in Codeforces are short contests!!!!!!
•  » » » » 2 months ago, # ^ |   +23 You may have a big jump in some contest like vammadur did before you change your handle. Maybe you can beat him :)
•  » » » » 2 months ago, # ^ |   +6 you can still go lower by getting negative score from hacking, though I don't encourage you to do that.
•  » » » 2 months ago, # ^ |   -35 So Mike please block jh05013's account!
•  » » » 2 months ago, # ^ |   0 Seeing your rating graph, I think you might even dream to become pupil again after you participate in 2 or 3 more rounds.
•  » » 2 months ago, # ^ |   +23
•  » » 2 months ago, # ^ |   +25
 » 2 months ago, # |   +8 Waiting and still waiting...
 » 2 months ago, # |   +7 Good time for Asia programmers!
 » 2 months ago, # |   0 Thank you all ...
 » 2 months ago, # |   -30 Is it rated?
•  » » 2 months ago, # ^ |   -16 Seems not...
•  » » 2 months ago, # ^ |   -10 In the end of the second paragraph,The round is rated for Div. 2 participants.
 » 2 months ago, # |   +14 Another Korean Round! I think this round would be wonderful round.
•  » » 2 months ago, # ^ |   0 Me too! I can't wait for it!
 » 2 months ago, # |   +2 I don't need to stay up late for the contest.It's a nice time for Chinese users.Wish everybody(especially me) good luck!
 » 2 months ago, # |   -23 I love Korean people.
•  » » 2 months ago, # ^ |   +3 Such a perv
 » 2 months ago, # |   0 WOW! A very friendly time for Chinese and Korean!!! I won't worry about my sleeping!!!
 » 2 months ago, # |   0 Nice time!!!
•  » » 2 months ago, # ^ |   +4 Are you from China?
•  » » » 2 months ago, # ^ |   0 yep!
 » 2 months ago, # | ← Rev. 2 →   -41 Why arsijo? I definitely don't want to take part in this contest!!!!!!!
•  » » 2 months ago, # ^ |   +5 It sounds like a beggar saying "I won't take anything from this fellow". Nobody cares.
•  » » » 2 months ago, # ^ |   -38 So what? arsijo's rounds are commonly not welcomed.
•  » » » » 2 months ago, # ^ |   +42 So what? your comments are commonly not welcomed.
 » 2 months ago, # |   0 Good Luck for everyone who join this competition.
 » 2 months ago, # | ← Rev. 2 →   +2 I've been waiting for this round almost one year. so hyped!
 » 2 months ago, # |   +165 Wtf, where this dislike of arsijo is coming from? You haven't even seen this round yet, moreover, to my knowledge, most coordination work was done by KAN, and arsijo will just help to arrange the round as KAN may be busy at this time.Also, by saying this sort of things you express disrespect to authors of the round at the same time. They did so much work, hoping you to enjoy the round, and now you dislike the round even before it began just because of coordinator. All you guys saying "ohh round by arsijo again" are getting really annoying, not better than dumb "Is it rated" guys.
•  » » 2 months ago, # ^ |   +46 Why do you expect CF comments to make like any sense? People write random shit coz they are bored or just retarded.
 » 2 months ago, # |   +5 Wow!! I hope it would be great round ever!
•  » » 2 months ago, # ^ |   +5 I'm your fan
 » 2 months ago, # |   +3 good job！
 » 2 months ago, # |   0 I have the level to solve problem_A/B/C and more but my english level is so poor that I can not understand the meaning of problems QWQ
 » 2 months ago, # |   +18 Finally I can take part in a contest without staying out late!
 » 2 months ago, # |   +13 Korean-made problems and Korean-friendly contest time. It is perfect if the problems are very wonderful.
 » 2 months ago, # |   +15 Time to go blue
 » 2 months ago, # |   +3 Desire for becoming Candidate Master within 3 Div.2 Rounds!! :)
 » 2 months ago, # |   0 i think this round #778 very exciting. I hope my rank < 200 ^^
 » 2 months ago, # |   +17 I failed to solve problem B in previous 2 contests. I don't want to make a hat-trick.
 » 2 months ago, # |   +11 A good time.I'd like to become blue this time.kkkkk
 » 2 months ago, # |   -21 I don't like problems with long statment :/
 » 2 months ago, # |   0 Starting with harder problems is a bad idea because even if you solve them, you won't submit.
•  » » 2 months ago, # ^ |   0 I can feel you. More than half time passed, still stuck on D. :|
•  » » » 2 months ago, # ^ |   0 I solved D about 20 minutes ago :(
•  » » 2 months ago, # ^ |   0 do you mean e because I had the same problem with it that I wasn't able to implement my idea.
•  » » » 2 months ago, # ^ |   0 I was referring to D, because I was scared of entering the contest officially after 45 minutes have passed, and screwing up. I will stick to A->B->c->D->E from now on.
 » 2 months ago, # |   +23 hi gamegame do you think you will win ioi 2020
•  » » 2 months ago, # ^ |   +18 Of course he will, he is such a god!He still has 2 IOI attempts left, so it was nice of him to let Benq have his second win.
•  » » » 2 months ago, # ^ |   +10 then do you think gamegame will win IOI 2021??
 » 2 months ago, # |   +14 5:35 AM ON A SUNDAY MORNING on the US West Coast :(
•  » » 2 months ago, # ^ |   +5 Thinking the contest was at 7:35 PST, I freaking missed it. Sob with me.
 » 2 months ago, # |   +9 what is the pretest 4 in problem B ?
•  » » 2 months ago, # ^ |   +18 I changed if (a[i + 1] >= k)m += a[i] - (a[i + 1] - k); to if (a[i + 1] >= k)m += min(a[i], a[i] - (a[i + 1] - k)); and it passed pretest 4
•  » » 2 months ago, # ^ |   +5 I had the same problem. I did all I could but couldn't find what was wrong. Ruined the contest for me.
•  » » » 2 months ago, # ^ |   +5 Same for me...First I struggled with pretest 2 but then pretest 4 destroyed me cries
•  » » 2 months ago, # ^ |   +6 I think you should add this to your code QwQ
•  » » 2 months ago, # ^ |   +5 you can't dig under 0 so you have to judge it if the next one is less than k.
 » 2 months ago, # |   +9 How to solve D?
•  » » 2 months ago, # ^ |   +6 2D partial sums
•  » » » 2 months ago, # ^ |   0 Further explanation please :D I tried to use segment trees but I can't bring the complexity below $O(n^3\log n)$
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 code#include using namespace std; #define mod 1000000007 #define ll long long #define N 2005 #define all(v) v.begin(),v.end() #define pii pair #define piii pair #define print(x) cout << #x << "=" << x << "\t"; #define newline cout << endl; int n; int k; char s[N][N]; int tree[N][N]; int ans; void process(int flip) { for(int i=1;i<=n;i++) { vector v; int j; j = 1; while (j <= n && s[i][j] == 'W') j++; v.push_back(j - 1); j = n; while (j >= 1 && s[i][j] == 'W') j--; v.push_back(j + 1); if (v[0] > v[1]) { ans++; continue; } if (v[1] - v[0] - 1 > k) continue; int y = max(1, i - k + 1); int y2 = min(i, n - k + 1); int x = min(v[0] + 1, n - k + 1); int x2 = max(v[1] - k, 1); if (flip) { swap(x, y); swap(x2, y2); } tree[y][x]++; tree[y2 + 1][x]--; tree[y][x2 + 1]--; tree[y2 + 1][x2 + 1]++; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; for(int i=1;i<=n;i++) cin >> s[i] + 1; process(false); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) swap(s[i][j], s[j][i]); process(true); int res = 0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { tree[i][j] += tree[i-1][j] + tree[i][j-1] - tree[i-1][j-1]; res = max(res, tree[i][j]); } cout << ans + res; return 0; } 
•  » » » » » 2 months ago, # ^ |   0 Yeah... I thought about that but did not code it because I thought it must need to support modification... And then I began happily coding with segment trees for the rest of the contest... Thanks :D
•  » » » » » 2 months ago, # ^ |   0 can you explain your approach?
•  » » » » » » 2 months ago, # ^ |   +2 Consider a row. It will only be counted in answer if it's completely white, which means at least one subarray of the row of length k must have all the black cells of this row. So, we compute the longest white-only prefix and suffix of the row.Next, we find the rectangle of the possible upper left corners of a single k-square such that if the upper left corner of the square lies in this rectangle, the chosen row will become all white. We just update a 2D partial sum matrix, or 2D fenwick tree for this purpose.We repeat this for all rows, and then we transpose the matrix, and repeat for all rows again (but be careful that the rectangle is now flipped by 90 degrees). Then we find the max value in the matrix, at matrix[i][j], which corresponds to max rows + colums which can have all it's elements white if a k-square had upper left corner was at cell (i,j).However, some rows and columns are completely white in input, which means we can directly count them in our answer and ignore processing these rows and columns completely.
•  » » 2 months ago, # ^ | ← Rev. 4 →   0 here was incorrect solution :(
 » 2 months ago, # |   +8
•  » » 2 months ago, # ^ |   0 So how to solve it?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 I think one possible solution is rolling hash
•  » » » 2 months ago, # ^ |   0 Use hash and check for maximum length prefix by iterator. See my submission 58613971
•  » » » 2 months ago, # ^ |   +6 I myself solved it using Prefix function (KMP): 58619921
 » 2 months ago, # | ← Rev. 2 →   +1 What is the pretest 4 of problem C?
 » 2 months ago, # | ← Rev. 2 →   0 How to reach to solution of C ?
 » 2 months ago, # | ← Rev. 2 →   +1 WHat was pretest 2 of Problem B?
 » 2 months ago, # |   +9 I used long double in C, and I am afraid of precision problems now.
 » 2 months ago, # |   +102
•  » » 2 months ago, # ^ |   +3 DUDE SAME
•  » » 2 months ago, # ^ |   0 I don't get it ;( What does that forget about zero mean?
•  » » » 2 months ago, # ^ |   +2 assume that the heights could go negative
•  » » » » 2 months ago, # ^ |   +3 Yeah, I knew that was an edge case of the problem, but that meme picture just doesn't click to me. Shit, I am stupid =(
•  » » » » 2 months ago, # ^ |   0 I thought this was pretest 4; thanks to that I was able to correct it.
•  » » 2 months ago, # ^ |   0 +1
 » 2 months ago, # | ← Rev. 2 →   +6 Waiting for the editorial guys!
 » 2 months ago, # |   0 Expected time complexity for problem D?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 $\mathcal{O}(n^2)$.
•  » » » 2 months ago, # ^ |   0 Give me some ideals about this problem, bro.
•  » » 2 months ago, # ^ |   0 N^2
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 N*N or N*N*log(N)
 » 2 months ago, # | ← Rev. 3 →   0 Why I keep getting TLE on pretest 11 of problem E?I think it's O(|s|),Why?Code
•  » » 2 months ago, # ^ |   +3 if(P==L){ ojbk=i; OK=1; } This part makes it quadratic. You should use hash for this part
•  » » » 2 months ago, # ^ |   0 Oh my god ,it's only a if
•  » » » 2 months ago, # ^ |   0 But how to use hash for this part,please explain further,thank you very much
•  » » » 2 months ago, # ^ |   0 I nearly know nothing about hash...
•  » » » » 2 months ago, # ^ |   +3 You should read about Rabin-Karp algorithm. Hashing is quite useful in problem related to string comparison
•  » » » » » 2 months ago, # ^ |   0 OK,I get it,thanks :P
 » 2 months ago, # |   0 Can D be solved in O(n*n) time?
•  » » 2 months ago, # ^ |   +1 Yes, using 2D partial sum to find out how many new white lines are created for each cell being chosen as the top-left position of the eraser.
 » 2 months ago, # |   -8 I used divide and conquer and KMP in order to solve problem E . Though I was not quite sure if it would pass TL but my submission got the verdict WA. Can anyone help point out mistake in my solution : My submission for problem E Apologies for the poorly written KMP.
•  » » 2 months ago, # ^ |   +6 4sample e le pleThis test case should give output "sample"
•  » » » 2 months ago, # ^ |   0 Thanks I got it the divide and conquer was the wrong way
 » 2 months ago, # |   0 How to solve D ?
 » 2 months ago, # |   +3 Why wouldnt suffix automaton solution for E pass below the time limit? I couldnt use an array bcs of memory, so i switched to maps, but that gave me tle, but the complexity is O(n*log(alphabet_size)), is the map factor just too big?
•  » » 2 months ago, # ^ |   +8 Why don't you use String Hash to compare two strings? It can be fast and easy to write.(Though it is slower than KMP)And, the alphabet_size=26, I think you should use array to store the edge on the SAM. The factor of map is very big when the size of it is too small like this.
•  » » » 2 months ago, # ^ |   0 i jump straight to coding instead of thinkingof another solution, thats why i didnt use hash
•  » » 2 months ago, # ^ |   0 But the size of it is very big. I think you can think about the Suffix Array to solve the String Problem. When the alphabet_size or the size of string is very big, SAM is very slow.
•  » » 2 months ago, # ^ |   +8 Oh, I didn't find that the alphabet_size is 62...
•  » » 2 months ago, # ^ |   0 Is there any way to squeeze suffix automaton in the tl?
•  » » » 2 months ago, # ^ |   0 How are you using SAM? Constructing the terminal states after each new string takes too long and I can't see how to do it without
•  » » » » 2 months ago, # ^ |   0 If we assume that we have memory to hold an array for the transitions between states, that means our adding of a transition takes O(1), then our complexity of constructing SAM is O(n), when we query for the largest prefix that is a suffix of the first string, we just traverse the SAM and if we come to the node which is coresponding to the last character inserted into SAM, we found our longest prefix which is a suffix of the first string. By n we denote total sum of lengths of strings in the input, i dont see why this wouldnt pass(only cause of large constant for the map) , correct me if im wrong
•  » » » » » 2 months ago, # ^ |   0 You can have more nodes corresponding to suffixes in addition to the one corresponding to the entire string. For instance if the string is $abb\dots bb$ every node corresponding to a substring with only $b$ is a terminal state.
•  » » » » » » 2 months ago, # ^ |   0 Yea, sry, ur right, dont know where did i get that silly idea
•  » » » » » » 2 months ago, # ^ |   0 Then, next question, can somehow suffix tree be implemented to fit the tle? To implement a treap for the transitions? Would treap be faster than c++ map? Or is there some c++ built in way to speed up map? And why is map factor so big?
 » 2 months ago, # | ← Rev. 2 →   0 Really good contest, in my opinion, even though I wasted a lot of time in A B and C. Almost had enougth time to debug E. RIP Rating twice in a row 1-1
 » 2 months ago, # |   0 What is the hacking test case for E?
 » 2 months ago, # |   0 Spent 1 hour trying to read and understand the preprocessing part of KMP. Then figured out that it can be solved with Hashing. Managed to only get A and B after that.I still don't understand the preprocessing of KMP though.
 » 2 months ago, # |   +2
•  » » 2 months ago, # ^ |   0 Then MLE on test 12 :((
 » 2 months ago, # |   +3 Can you please tell me where is a mistake in my solution of B? 58581229I spent the whole contest trying to find what's wrong with it.
•  » » 2 months ago, # ^ |   +14 firstly you should get whole input, you should not use break when you are coding a multi-test case problem.
•  » » » 2 months ago, # ^ |   +8 Ahaha, thank you. So stupid mistake)
•  » » 2 months ago, # ^ | ← Rev. 2 →   -8 (deleted. Wrong comment)
 » 2 months ago, # |   0 Hey everyone, do you know what's wrong in my solution for E? 58612747
 » 2 months ago, # | ← Rev. 2 →   +3 I'm foolish to use (single) unsigned long long for hash.
•  » » 2 months ago, # ^ |   0 Why would that be a problem?
•  » » 2 months ago, # ^ |   +19 E: Wrong Answer On 65
•  » » 2 months ago, # ^ |   0 Unluckily,I also used it……
 » 2 months ago, # |   0 Nice pretest for C :v
•  » » 2 months ago, # ^ |   0 Same boat :(
 » 2 months ago, # |   +29 Hack test case in E for MOD 1e9+7 is nonsense
•  » » 2 months ago, # ^ |   +3 Dang that sounds really unfair, although I always use weird values to prevent getting owned a little bit more.
 » 2 months ago, # | ← Rev. 2 →   -18 .
•  » » 2 months ago, # ^ | ← Rev. 2 →   +3 edited
•  » » » 2 months ago, # ^ |   0 Can you help me find my mistake too .Link to submission to B
•  » » » » 2 months ago, # ^ |   +3 This line:if(arr[i-1]>=arr[i]) c+=min(k,arr[i])+abs(arr[i]-arr[i-1]);The conditional is unnecesary, because you can add blocks to the bag while arr[i-1]>arr[i]-k. With that, the sum changes too, the absolute value will generate wrong answer. You should change that line to: c+=min(k,arr[i])+arr[i-1]-arr[i];
•  » » » » » 2 months ago, # ^ |   0 Thank you so much..You are a lifesaver..
 » 2 months ago, # | ← Rev. 8 →   +19 R.I.P. for my single Hash (use unsigned int) in Problem E Wrong Answer On Test 65 TATGreat Hash-Killer!I will never use single Hash in Codeforces again...Tips: Using some unusual prime numbers to model can help you pass Elike NTT model number $998244353=119\times 2^{23} +1$ ...
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 My single hashing using $M = 10^9 + 9$ and $P = 67$ passed here 58620113. Ignore all the calculations in the end in isEqual function I only check the equality of the 3rd hash.Edit: uphacked :D. It would be appreciated if people could share in this thread some tips to make string hashing more probable to pass :)
•  » » » 2 months ago, # ^ |   0 just use random module, smth like 1e9+rand(), and then find the nearest prime
 » 2 months ago, # | ← Rev. 3 →   0 Why does Problem D use "cin" get timeout results?
•  » » 2 months ago, # ^ |   +3 Please add this in your main()，in front of your cin ios::sync_with_stdio(false); 
•  » » 2 months ago, # ^ |   +13 What an interesting way to trick the plagiarism checker. Isn't it violation of the rules?
•  » » » 2 months ago, # ^ | ← Rev. 3 →   -6 Maybe not.This is a well-known skill in China to speed up cin, and cancel the influence from stdio As far as I know, lots of chinese OIers use this skills in their own codes.For honest, maybe sometimes using cin is more convenient than using scanf, (like Probelm E), and this skill can make iostream faster.So why not use this?
•  » » » » 2 months ago, # ^ |   +18 LOL. Take a look at the code first.
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   +16 Sorry, it’s my fault.Although this skill may help him little...
•  » » » » 2 months ago, # ^ |   0 Actually I also tested without input optimization and checked if they pass just fine. I think that barely-readable code is either not O(N^2), or is extremely badly optimized.https://codeforces.com/contest/1200/submission/58638010
 » 2 months ago, # |   0 My submission got TLE on test 3 but it passes the pretests. How is this possible? .-.
 » 2 months ago, # |   +14 When will the rating be updated?
•  » » 2 months ago, # ^ |   0 Congrats :p
 » 2 months ago, # |   0 Can someone explain what happens in problem C when both n,m are 1 or any one of them is 1?
 » 2 months ago, # |   +2 Please, Can anyone help me know where my solution for problem C fails.?My Solution
•  » » 2 months ago, # ^ |   +1 +1
•  » » 2 months ago, # ^ |   +1 float precision
•  » » » 2 months ago, # ^ |   0 where exactly?
•  » » 2 months ago, # ^ |   +6 Using long double works.Or maybe $\frac{(x+y-1)}{y}$
•  » » » 2 months ago, # ^ |   0 Thanks, that worked.
 » 2 months ago, # |   +22 https://codeforces.com/contest/1200/submission/58612411https://codeforces.com/contest/1200/submission/58619785EXACT SAME CODE PASSES AFTE CONTEST??? I'm that unlucky to just get the wrong base on test 19? Are you kidding me? Can I get this restored?
•  » » 2 months ago, # ^ |   +29 Use kmp
 » 2 months ago, # | ← Rev. 3 →   +7 God damn it! I feel so unhappy now (prob.C). I got WA on main test 35 because of real number rounding :(( (look at the selected text parts) In the contest I code like this: During Contest After that I fixed a little bit and got AC :(( After Contest Who has the same errors like this? Show me your hand bruh =))
 » 2 months ago, # |   +3 For Problem E，why hash algorithm fail？
•  » » 2 months ago, # ^ |   +8 Use double hashing
 » 2 months ago, # | ← Rev. 2 →   0 Please someone tell why my solution for E is failing at case 8. Though the expected and actual output seem to be same.https://codeforces.com/contest/1200/submission/58612328
•  » » 2 months ago, # ^ |   0 Basically I had the same idea and my submission failed too. Can someone please help us to understand the error?
 » 2 months ago, # |   0 Why my submission failing for no apparent reason?58615776 Please Help B question
•  » » 2 months ago, # ^ |   0 When you do the sum m+= k-abs(h2-h1) you are forgetting that the number of blocks of height h1 could be less than k-abs(h2-h1), so when you do that sum, the remaining number of blocks of that pile become negative, and that's impossible. So, the sum is m+=min(h1, k-abs(h2-h1)), and with that the number of blocks will never be negative.
•  » » » 2 months ago, # ^ |   0 Thank you very much. My bad I overlooked it.
 » 2 months ago, # |   0 My rating becomes 2019 Nice number LOL
 » 2 months ago, # |   0 58606364 What is wrong with this solution for B ? It fails pretest 4 test case no. 6, but when i run that particular test case on an ide, it shows the correct answer.
•  » » 2 months ago, # ^ |   0 If h[i]
•  » » » 2 months ago, # ^ |   0 Why won't m increase in that case ? Suppose h[i]=4, h[i+1]=6, k=8. Then we can collect all the 4 blocks from h[i] and transfer to m,right?
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   0 Sorry it doesn't mean that. Well , k=160,h[i]=47,h[i+1]=107 then u should make b=-47 but not h[i+1]-h[i]-k=107-47-160=-100` ,right?
•  » » » » » 2 months ago, # ^ |   0 yup, got it. Thanks :)
 » 2 months ago, # |   0 58580810 Could somebody tell me where is my mistake? It's my first time to be hacked in problem A and I'm gona to be crazy. T_T
•  » » 2 months ago, # ^ |   0 Look into your (**left, right**) variables they took same value in testcases. Two costumers cann't enter same room
•  » » » 2 months ago, # ^ |   0 OMG ,thx for u saving my sleeping.
 » 2 months ago, # |   +2 Any ideas to solving F?
 » 2 months ago, # | ← Rev. 3 →   -67 As i said in this comment i got TLE on test 3 but it doesn't make sense because the the code passed the pretests.And the same code after contest got AC.WTF?And i lose rating because of this. Why is this? djm03178 MikeMirzayanov
•  » » 2 months ago, # ^ | ← Rev. 2 →   +5 Because the actual running time can be different every time it's executed. It sometimes happens when your solution is almost at the edge of the time limit.
•  » » » 2 months ago, # ^ |   -51 Check the time of the cases, they're not in the edge of the limit...
•  » » » » 2 months ago, # ^ |   +11 935ms is pretty close to 1s, I'd say.
•  » » » » » 2 months ago, # ^ |   -84 Unrated
 » 2 months ago, # |   0 Someone explain D?
•  » » 2 months ago, # ^ |   0 consider for each column and for each row, all the available left-top positions of the cfpaint which can make this column or row all white form a rectangle. We define left-bottom position of this rectangle as (x1,y1)，right-top position of this rectangle as (x2,y2),and then we need to add 1 to all the position(x,y) which satisfy x>=x1 and x<=x2 and y>=y1 and y<=y2, for this purpose, you can solve it like this: init dp[n+1][n+1] all value as 0,and when you deal with each row or column,first find the available (x1,y1)and (x2,y2),then just do like this: dp[x1][y1]++,dp[x2+1][y1]--,dp[x1][y2+1]--,dp[x2+1][y2+1]++. after solve all the rows and columns, you iterate over dp[n+1][n+1]，set dp[i][j]+=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]，after this find the maximum value in dp is just the answer.
 » 2 months ago, # |   +16 경합이 아주 재밌었고 레이팅도 올랐고 덕분에 "아무개"란 단어도 배웠어요! 고마워요ヾ(❀╹◡╹)ﾉﾞ❀Thanks to this contest I learned a Korean word "amugae" and gained +25 rating points, thank you very much!
 » 2 months ago, # | ← Rev. 2 →   0 I have received code coincide message for problem C,Here is the two links:58583425 58592979 I admit that these two codes are very similiar. But it is truly just because the solution for problem C is so simple and the codes between us written similarly accidently.What's more, not only the codes between us looks similiar,many codes are. I have tried to comunicate with Mike, but I didn't get any response yet maybe Mike is very busy now. I just want to show thst I am honest to participate in the contest.
 » 2 months ago, # |   0 For problem F, can someone explain how is the LCM term coming? (Specifically, how is the number of states for a particular vertex 2520 and the logic behind decomposition of the graph in various states). I'm not sure what the author means by state here.
 » 2 months ago, # | ← Rev. 3 →   0 Can anyone explain me why my first submission got TLE and second got AC? I think the both code has same complexity. Thanks in advance. :)1st submission: https://codeforces.com/contest/1200/submission/58837253 2nd submission: https://codeforces.com/contest/1200/submission/58837269
 » 2 months ago, # | ← Rev. 2 →   +3 Why problems aren't rated yet?Edit: They're rated now!