Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### kevinsogo's blog

By kevinsogo, history, 7 months ago, ,

I hope you enjoyed the problems! Thanks to the onsite teams and coaches who gave feedback; I'm glad the reception was positive.

Interestingly, in the onsite ICPC round, while "Kirchhoff" got several accepted solutions, "Miss Punyverse" got no accepted submissions at all! It is the reverse here. (Kirchhoff even has a trickier output format in the onsite round compared to the version presented in Codeforces.) It seems the ICPC scoreboard really affects the results greatly; what the top few teams are working on influences what everyone else will be working on.

I am planning on releasing the full, untouched ICPC Manila 2019 problem set in the gym sometime in the future, so you can see which problems you missed. The Intergalactic Sliding Puzzle is not the hardest problem in the round!

1281A - Suffix Three

Solution Sketch
Accepted Code

Accepted Submission: 67015948

1281B - Azamon Web Services

Solution Sketch
Accepted Code

Accepted Submission: 67049609

1281C - Cut and Paste

Solution Sketch
Accepted Code

Accepted Submission: 67016113

1281D - Beingawesomeism

Solution Sketch
Accepted Code

Accepted Submission: 67016167

1281E - Jeremy Bearimy

Solution Sketch
Accepted Code

Accepted Submission: 67020743

1281F - Miss Punyverse

Solution Sketch
Accepted Code

Accepted Submission: 67016189

1280E - Kirchhoff's Current Loss

Solution Sketch
Accepted Code

Accepted Submission: 67016199

1280F - Intergalactic Sliding Puzzle

Solution Sketch
Accepted Code

Accepted Submission: 67026155

• +99

 » 7 months ago, # |   0 Can somebody help me why my submission to Div2 C that is Div1 A is getting TLE on test 6 when I am using similar thing as the editorialhttps://codeforces.com/contest/1281/submission/66931104
•  » » 7 months ago, # ^ |   0 I am getting TLE on test 24. Can anybody help me out? I am unable to remove TLE. https://codeforces.com/contest/1281/submission/66993181
•  » » 7 months ago, # ^ |   +1 Add an additional condition in this for loop for (LL i = 0; i < s[p-1]-'0' - 1; ++i) {s+= sub;} to exit when the string length crosses x. This would most probably fix the TLE.
•  » » » 7 months ago, # ^ |   0 Oh I completely neglected that, only should take substring when we are appending. Thanks a lot!
•  » » 7 months ago, # ^ |   0 You are calling substr in every loop, and it works in O(n), so your solution TLEs. I changed this, and it got accepted.
 » 7 months ago, # | ← Rev. 3 →   +6 Can we print the pairs? 1281E
 » 7 months ago, # | ← Rev. 2 →   +3 For problem 1281F/1280D, why is 67027127 incorrect?Explanation: this submission closes all partition at the subtree instead of open it. It tries to either union the partitions from the $u$ subtree and $v$ subtree, or merge the top partitions from subtree $u$ and $v$ together.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +15 Counterexample1 4 2 3 1 3 0 0 0 0 2 1 2 2 3 2 4 
 » 7 months ago, # |   0 Here is my implementation of Div1 D, which I think is easier to understand than the one given in the editorial: 67036054
 » 7 months ago, # | ← Rev. 2 →   0 Can somebody tell me, why am I getting TLE in this? Problem C
•  » » 7 months ago, # ^ |   0 c=s.substr(pos+1); is unnecessary when times==0. You are obtaining a substring, only to find out later that you have to work on it $0$ times. That's a waste. Handle this and get an $AC$.
 » 7 months ago, # |   0 I tried my best but I am not able to understand why 67059551 for problem Div2 C gives MLE and also Why 67057569 solution for same problem is giving TLE. please help
•  » » 7 months ago, # ^ |   0 For the TLE, I think it is because substr is linear time in the length of the string, and you are potentially calling it quite a lot. If a string is of length close to x and you keep finding the number '1', then you will delete the right half of the string, then append the right half of the string again and again and again, it could easily be quadratic time complexity. Try only appending to s (never set it equal to sleft)
•  » » » 7 months ago, # ^ |   0 Thanks for the reply man. I tried what you said but still it gives TLE. heres my 67138033 . Also Could you find reason for MLE.
•  » » » » 7 months ago, # ^ |   0 When you do += on the string s it is going to make a whole new string s, maybe you can use the append method instead. Besides that there is a bigger problem in both the TLE and MLE one. You think the if statement is checking if n
•  » » » » » 7 months ago, # ^ |   +3 Thanks man. Got it
•  » » » » » 5 weeks ago, # ^ |   0 i used += and got ac at 46 ms.. https://codeforces.com/contest/1280/submission/81967475
 » 7 months ago, # | ← Rev. 2 →   0 Can someone please tell me why my submission for B is giving a WA verdict on test set 2? Here is my submission.
•  » » 7 months ago, # ^ |   0 Never mind. I have got it. Thanks.
 » 7 months ago, # | ← Rev. 2 →   0 Can somebody help, I still haven't understood why the complexity of problem 1281F/1280D is O(n^2)
•  » » 7 months ago, # ^ | ← Rev. 2 →   +13 Hi! I wrote this training material for our IOI training camp earlier this year: https://drive.google.com/open?id=1nhL63QcjUiRm1pGGmzi1QHceKAGeBsRY. A proof is given in Section 4.2, "Tree convolution DP", and also in the appendix. (It is only shown for the case of binary trees, but it can be extended to general trees by looking at the binary tree of "recursive calls" instead of the actual tree.)
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Hello kevinsogo, thank you for sharing this DP3 module could you please share DP1 and DP2 modules?also in the link you shared, the proof for general trees is left as an exercise, c in f(i, m, c) simply the index of the child we are at right?thank you!
 » 7 months ago, # |   0 Can Somebody help me with code of C Cut and Paste it is giving wrong answer on 108th testcase of test 6 but I can't see the testcase so unable to figure out the mistake. Thanks in Advance :) https://codeforces.com/contest/1281/submission/67296667
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Hi, when you are doing answer = (answer + (answer-i)*v)%MOD;, your answer is becoming negative and most programming languages don't know how to tackle negative modulo. Do  answer = (answer + (answer-i)*v )%MOD; answer = (answer%MOD + MOD)%MOD;  and it should work fine.
•  » » » 2 months ago, # ^ |   0 Why is amswer turning negative anyway? answer, (answer-i), and v should always be positive. So, (answer + (answer-i)*v ) should be positive too.Then, when you take the MOD of a (answer + (answer-i)*v ), shouldn't that also be positive?
•  » » » » 5 weeks ago, # ^ |   0 this is because..lets assume ur answer becomes 1000000010 and i=100, when you will take mod..answer will become 3,so in next iteration i=11,and answer
•  » » » 13 days ago, # ^ |   0 thanku very much scorpion_guy
 » 7 months ago, # |   0 In Problem C : Can anyone tell me why my solution using string ( Code with string ) gives runtime error but the same code with vector of char got accepted ( Code with vector
 » 7 months ago, # |   0 Hello, I can't figure out what is wrong on my problem 67396769, it is pretty much the same idea but it is wrong answer on test 2 (subtest 41). Thanks
 » 7 months ago, # |   0 OK this is probably a dumb question but I'm still gonna ask . In problem D , wouldn't the optimal solution be counting N the number of the nodes where the condition ( number of bees < number of wasps) holds and returning max(m-1,N) ? (In this case , we will consider ALL the nodes where the condition is false to be a single village and consider every node where the condition holds as a single village as well ) Am I missing any details ?
•  » » 6 months ago, # ^ |   0 Not sure I understand what you meant, but the villages need to be connected subtrees, so you can't just turn any bunch of nodes into a single village.
•  » » » 6 months ago, # ^ |   0 Why can't I turn any bunch of nodes into a single village ? (By considering them to be a sub-tree)
•  » » » » 6 months ago, # ^ |   0 A subtree needs to be connected, so for instance if you take the tree with vertices 1, 2, 3 and edges (1 -> 2), (1 -> 3) , then 2 and 3 can't be turned into a subtree because they are not connected without 1
 » 6 months ago, # |   0 In 1281E, Can somebody give me a bit more proof why this technique is correct for maximizing and minimizing? And hopefully links to more problems like this one.
 » 6 months ago, # |   0 Problem D's video tutorial: https://youtu.be/SAPSHUv_zZE
 » 6 months ago, # |   0 can someone help me in problem 1281B. I am getting wrong answer in test2 testcase41 but I am not getting my mistake as that case is not visible. I am doing similar as in editorial solution sketch. https://codeforces.com/contest/1281/submission/68429120
 » 5 months ago, # | ← Rev. 2 →   0 Can someone plese get me any testcase where My Solution fails.
 » 3 months ago, # |   0 If anyone need detail explanation of DIV2 C SEE HERE