### kevinsogo's blog

By kevinsogo, history, 6 weeks ago, ,

Hello, Codeforces community!

I'm glad to invite you to Codeforces Round #607 (Div. 1) and Codeforces Round #607 (Div. 2), which will be held on 15.12.2019 08:05 (Московское время). The round will be rated for both divisions.

The problems were taken (mostly) from the 2019 ICPC Asia-Manila Regional Contest that's happening at the same time. Thus, they have been prepared by various setters and testers from the Philippines: myself (kevinsogo), Kyle See (kylesky), Payton Yao (noobcake), Tim Dumol (timd), Guissmo Asuncion (guissmo in HackerRank) and Marte Soliza (myrtactle in TopCoder).

Since the problems are based on the ICPC Manila regionals, we request all the coaches onsite to refrain from making the problem set public. We also request the coaches and everyone else who has seen the problems (or part of it) to refrain from joining this round.

A huge thanks to isaf27 for coordinating and helping me set up this round. Thanks to 300iq for some testing. Of course, thanks as well to MikeMirzayanov for providing us Codeforces and Polygon. These are great gifts to the competitive programming community! Also, thanks for the opportunity to use our problem set for a CF round.

You will be given 6 problems in both divisions and 2 hours to solve them. I recommend reading all the problems; they were written by talented writers from the judging team.

Good luck, have fun, and I wish everyone high ratings!

The scoring distribution will be announced closer to the beginning of the round.

Update: The scoring will be as follows:

Div.2: 500 — 1250 — 1500 — 2000 — 2500 — 3000
Div.1: 500 — 1000 — 1500 — 1750 — 2250 — 3000

Good luck and have fun!

Congratulations to the winners! Congratulations to ksun48 for winning the Div. 1 round, and ilovebinhh for winning the Div. 2 round!

Div. 1 Winners:

Div. 2 Winners:

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

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!

• +179

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by kevinsogo (previous revision, new revision, compare).
 » 6 weeks ago, # |   +4 Is it normal that there are two contests at the same day?
•  » » 6 weeks ago, # ^ |   -18 Pfff, is that really a problem for you?
•  » » 6 weeks ago, # ^ |   -21 Sometimes I even write three contests per day!
•  » » » 6 weeks ago, # ^ |   +8 wow, how do you do that?
•  » » » » 6 weeks ago, # ^ |   +149 First write first contest, then second and third ones
•  » » » » » 5 weeks ago, # ^ |   +81 Cool story
•  » » » » 5 weeks ago, # ^ |   +36 Live in Kamchatka
•  » » » » » 5 weeks ago, # ^ |   +10 wtf?
 » 5 weeks ago, # |   +54 I am confused.
•  » » 5 weeks ago, # ^ |   -6 You can do both the contests but say goodbye to sleep. I did that once and still got a good score.
 » 5 weeks ago, # |   +26 So, now its possible to make a perfect 'T' shape in the rating curve. :3
•  » » 5 weeks ago, # ^ |   0 I think I was wrong... a perfect 'L' is possible...not 'T' :3
 » 5 weeks ago, # |   -6 Will the problems be in English only?
•  » » 5 weeks ago, # ^ |   +19 As usual: English and Russian.
 » 5 weeks ago, # |   0 why was div2(606) contest held at such time ,also why not even one of 607 and 608 ,at a usual time??
•  » » 5 weeks ago, # ^ |   +20 Maybe because that rounds are based on some contest(#606 : Technocup 2020 Elimination Round 4, #607 : ICPC Manila 2019, #608 : Municipal Stage of All-Russian Competitions for Schools, Saratov).
 » 5 weeks ago, # |   +1 What will happen if a candidate master who has registered #608 officially becomes master in #607? Will he/she still be rated in #608?
•  » » 5 weeks ago, # ^ |   +1 Of course not
 » 5 weeks ago, # |   +1 Are there plans to upload the full contest onto codeforces gym? I am very much looking forward to this contest
•  » » 5 weeks ago, # ^ |   +44 Yes, I plan on uploading the full set in the gym in the future, along with some past ICPC Manila problem sets too.
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by kevinsogo (previous revision, new revision, compare).
 » 5 weeks ago, # | ← Rev. 3 →   -12 I had this one question, how do problem setters generate big test cases, especially where some particular conditions need to be satisfied, suppose such as the given undirected graph had to be connected, and all?
•  » » 5 weeks ago, # ^ |   0 They have a testing library and tools because I once saw errichto adding testcases in a video.
•  » » 5 weeks ago, # ^ |   +3 Ye, for graphs jngen is really awesome, but in general it's pretty uncommon for tests to have hard structure. Like the said connected graph is just a spanning tree (which is easy to generate) with some more edges on top of it.
•  » » 5 weeks ago, # ^ |   +13 kevinsogo is the chief judge of ICPC Manila, that's why he has "early access."
 » 5 weeks ago, # |   +79 (
•  » » 5 weeks ago, # ^ |   -8 so funny,me too：D
 » 5 weeks ago, # |   +1 What did people get hacked on in B?
•  » » 5 weeks ago, # ^ |   +19 answer can be 0
 » 5 weeks ago, # |   +11 How to solve Div1 C?
•  » » 5 weeks ago, # ^ |   +43 Maximum — for each edge estimate upper bound of pairs which ways can contain this edge (it will be min(size_of_left_tree_if_we_erase_this_edge, size_of_right_tree_if_we_erase_edge). Answer — sum of upper bounds multiplied by weight of edge.Minimum — it can prooved that each edge must be taken at most once. Lets make tree rooted and count size of each subtree, we take an edge only if size of corresponded subtree is odd.
 » 5 weeks ago, # | ← Rev. 2 →   +8 What is pretest 2 in Div 2 B ?
•  » » 5 weeks ago, # ^ |   +5 What ever it was, it was the death of me xD Had like 15 submissions xD
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +4 me too, I spent like 1hr 40 minutes trying to figure out that single problem... I guess I will lose a lot of my reputation points on this one... :(
•  » » » » 5 weeks ago, # ^ |   0 Luckly not that much, just around ~14.
•  » » » » » 5 weeks ago, # ^ |   0 What was the corner case in Pretest 2? I still couldn't figure out.
•  » » 5 weeks ago, # ^ |   0 My code failed BANANA APPLE :(
•  » » 5 weeks ago, # ^ |   0 for test case : IA GOG why AI is not the answer?
•  » » » 5 weeks ago, # ^ |   0 AI is the answer.
•  » » » » 5 weeks ago, # ^ |   0 got it !
•  » » 5 weeks ago, # ^ |   0 My code failed on BAA AABA. My code produced ABA and told me that it's impossible since it is smaller than AABA. smhAs a grey, I solved A in 4 mins then stuck on B until contest ended. Still got positive delta.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 TryEBB BBF
 » 5 weeks ago, # |   +1 It took a lot of time to solve Div.2 B :(
•  » » 5 weeks ago, # ^ |   +5 What was pretest 2?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Try Cases likeEBB BBFYXXXXX YXXXXZ
 » 5 weeks ago, # |   +17 Div.2 B is a bad problem. There was no test in Div.2 D where the answer was 0.
•  » » 5 weeks ago, # ^ |   0 For which case?
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Div.2 D for this test case answer is 0.3 3AAAAAAAAA
 » 5 weeks ago, # |   +9 For Div1 C, does anyone have a proof for why the contribution for each edge can be given by the minimum size of two components it connects multiplied by its edge weight? This seemed like a "best case" scenario to me, but I couldn't prove why it would always happen.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +6 wrong :/
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Wow, that's a slick proof. Thanks.EDIT: Apparently not.
•  » » » 5 weeks ago, # ^ |   0 It’s not always possible to split into K and K. For example, a star with 4 nodes.
•  » » 5 weeks ago, # ^ |   0 That’s the upper bound and we just need to show a way to achieve it. Think about the edge that maximizes the smaller components. Pair the nodes based on that edge and the pairings should work for future edges.
•  » » » 5 weeks ago, # ^ |   0 Yeah, I had trouble with accepting the "pairings should work for future edges" idea because it wasn't obvious to me that it wouldn't mess up previous pairings.
•  » » » » 5 weeks ago, # ^ |   +16 Find the centroid of the graph, it will split in several subtrees all with size less than or equal to half of the full tree size. For each subtree assign consecutive number 1, 2, ... k, 1, 2, ... k. Notice that none subtree will contain a pair of equal numbers. You can prove that this distribution works good.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Assume the initial 2 components have size X and Y (X <= Y). We need to prove that for further edges, its smaller components should not have more than X nodes. It's obvious for all edges in X side. Assume there exists an edge that produces a component with size Z in Y side such that X < Z < Y. Using that edge as the very first one would give us a better pairings and it contradicts to our initial assumption.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Suppose the removal of the edge splits the graph into sets $S$ and $T$ with $|S| \le |T|$. If $( i, j )$ is a pair within $S$, then there must exist a $(u, v)$ pair within $T$. Then you can show that pairing $(i, u)$ and $(j, v)$ is always better (try and draw a diagram to see why). Hence, each vertex in $S$ must be matched to something in $T$.
•  » » 5 weeks ago, # ^ |   0 Centroid can help you prove this
 » 5 weeks ago, # |   -8 I actually failed life How did I not solve 2B???? I'm getting RE/WA on testcase 2 and sometimes even test case 1 (when it works locally) Can someone help please It's an easy bruteforce?? Is my "check strictly lexicographically smaller" function wrong??Please helpCode: from random import * def r(n=10): return ''.join(chr(randint(65, 90)) for _ in range(n)) def check(s1, s2): if len(s1) < len(s2) and s2[:len(s1)] == s1: return True i = 0 while i < len(s1) - 1 and i < len(s2) - 1 and s1[i] == s2[i]: i += 1 if i < len(s1) and i < len(s2) and s1[i] < s2[i]: return True return False for _ in range(int(input())): # s1, s2 = r(3), r(3) s1, s2 = input().split() removed = "" while len(s1) > 0 and len(s2) > 0 and s1[0] == s2[0]: removed += s1[0] s1 = s1[1:] s2 = s2[1:] f = False for i in range(len(s1)): tmp = list(s1) tmp[0], tmp[i] = tmp[i], tmp[0] tmp = ''.join(tmp) if check(tmp, s2): assert (check(removed + tmp, removed + s2)) print(s1, s2, removed + tmp) f = True break if not f: print('---') 
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +4 Well now I think about it I think I can just use "<" in python to compare the strings... I think that's how python compares already...BUT ITS FINE! Next competition in an hour! Hope I promote :)EDIT: FUCKKKK I GOT 2C WRONG OMG
 » 5 weeks ago, # | ← Rev. 3 →   +1 I was stuck on Div2 B for the whole contest because I didn't read the constraints completely; seeing that the sum of the strings across test cases can only be 5000, I then soon got a AC.I had around 10 WAs :(
•  » » 5 weeks ago, # ^ |   0 How? What made it so easy after reading constraints? Did you get to know why your solution was failing on pretest 2?
•  » » » 5 weeks ago, # ^ |   0 I think that means you can use O(n^2) algorithm to solve this problem. (But I implemented one and still failed...)
•  » » » » 5 weeks ago, # ^ |   0 Now I passed the pretest 2 using O(n^3) sol (finally!!), but got TLE at pretest 10
•  » » » » » 5 weeks ago, # ^ |   0 O(n^3) would never work as cube of 5000 is like 10^11
•  » » » » » » 5 weeks ago, # ^ |   0 Yes, but the 1st place's code is also O(n^3) solution but with trim for some obvious cases. (Notice that the comparison operators for string in C++ is O(n))
•  » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I did it in O(nlogn) :P66935678
•  » » » » 5 weeks ago, # ^ |   0 Weird. My O(n^2) gave me TLE and I thought I figured out the reason.Sum of lengths across test cases doesn't exceed 5000, but we're doing sum of squares of length. In this case it looks like it could possibly exceed one second.
•  » » » » » 5 weeks ago, # ^ |   0 sum of squares is at most the square of the sum.
•  » » » » » » 5 weeks ago, # ^ |   0 Oh, just realised that. Can I then know the cause of TLE of my submission below?https://codeforces.com/contest/1281/submission/66904986
•  » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I think string ss = s; is O(|s|) so you get n^3 total. You can just swap in s, then swap it back afterwards to restore s.
•  » » » » » » » » 5 weeks ago, # ^ |   0 Thanks!
 » 5 weeks ago, # |   0 What was pretest 2 in Div. 2 Problem B. Azamon Web Services? The problem was very easy but my solution failed on this testcase even after multiple attempts.
•  » » 5 weeks ago, # ^ |   0 n^2 solution passes
•  » » » 5 weeks ago, # ^ |   0 Really mine gave TLE on pretest 10.
•  » » » » 5 weeks ago, # ^ |   0 unnecessary comparisons were not considered for example you would want to replace with smaller character only, otherwise its just waste of computation time
•  » » » » 5 weeks ago, # ^ |   0 My O(n^2) solution passed. Sum of strings can only be upto 5000, and TL is 2 secs.
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Mine did not pass pretest 2 even using O(n^3) solution...EDIT: I found a mistake. Not it passed pretest 2 and TLE at test 10.
•  » » 5 weeks ago, # ^ |   0 This is one of my submissions, which should be correct as far as I could think of : 66909918.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +11 Try AMGMG,AGM
•  » » » 5 weeks ago, # ^ |   0 Wow, My solution fails on that testcase. How did you make that case?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Is the answer is $AGGMM$. I don't know why my code is failing on test case $2$
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Get this ans, too, but failed at pretest 2
•  » » » » 5 weeks ago, # ^ |   0 I'm also getting the same answer, but WA on Test case 2
•  » » » 5 weeks ago, # ^ |   +1 Thanks for this case!
•  » » » 5 weeks ago, # ^ |   0 My solution fails on this test case. Thanks.
•  » » » 5 weeks ago, # ^ |   +3 Also try BANANA APPLE
•  » » » » 5 weeks ago, # ^ |   0 I'm getting AANANB . But WA on Pretest 2
•  » » » » » 5 weeks ago, # ^ |   +1 Tried APPLEC APPLE ?
•  » » » » » » 5 weeks ago, # ^ |   0 Yes. Getting ACPLEP
•  » » » » » » » 5 weeks ago, # ^ |   0 LOL at me. I misinterpreted "lexicographically smaller".
•  » » » 5 weeks ago, # ^ |   0 I also get this answer,But failed in test2
 » 5 weeks ago, # |   +3 What is pretest 6 in div 2 C?
•  » » 5 weeks ago, # ^ |   +2 As far as I know it is a number where if you don't MOD correctly it fails. Thats how I fixed it, I implemented standerd MOD methods.66924381
•  » » 5 weeks ago, # ^ |   +1 For me, on replacing $x \% p$ by $(x \% p + p) \% p$, I got AC.
•  » » » 5 weeks ago, # ^ |   0 Probably the same, because my neg method basically does this
 » 5 weeks ago, # | ← Rev. 2 →   +128 Just my personal opinion (not only my actually), but I didn't like this contest at allA: it's harder to understand the statement than to solve the problemB: just case checkC: superfamous problemD: maybe I shouldn't judge on it if I didn't solve it in time, but isn't it a super standard dp problemE: solution is fairly easy, the hardest part for me was parsing T_T (that's my fault for being stupid and being unable to parse it but still)Can't say anything about F
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 what dp in D? I hardcoded the cases of ans = 4/3/2/1/0, and that seemed to pass..
•  » » » 5 weeks ago, # ^ |   +3 that's Div1B
•  » » » 5 weeks ago, # ^ |   +3 oh right, my bad, you're div 1..
•  » » 5 weeks ago, # ^ |   +37 Looking at the scoreboard, D doesn't seem so standard.Although, in my opinion the problem statement is really bad. It's so long for an actually very natural problem. The definitions slowed me down so much especially because they use silly names like "village".
•  » » » 5 weeks ago, # ^ |   0 agree
•  » » 5 weeks ago, # ^ |   0 How you solved D with dp ?
•  » » 5 weeks ago, # ^ |   +37 Shouldn't an hour be enough to code up a "super standard dp problem"? :P
•  » » » 5 weeks ago, # ^ |   -23 I was trying to do E instead T_T
•  » » » » 5 weeks ago, # ^ |   +7 Shouldn't an hour be enough to code up an easy parsing problem, everything in brackets, all tokens are of length 1 etc?
•  » » » » » 5 weeks ago, # ^ |   +26 Not for a dumbass like me
•  » » » » » 5 weeks ago, # ^ |   +9 easy for you to say, not everyone is a programming god
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +65 Yeah, D is trivial once you notice that combining the DP for the left ($L$) and right ($R$) subtrees in time $\mathcal{O}(|L| |R|)$ is $\mathcal{O}(|T|^{2})$ work for any tree $T$.Just calculate for every subtree the values $DP[k]$: The maximum pair $(c, s)$, where $c$ is the amount of other villages in the subtree with more wasp than bee voters, and $s$ is the sum of the village the current node is in, when we have exactly $k$ villages in the subtree.$\mathcal{O}(n^{2})$ is fast enough, as then we do in the worst case around $3000^{2} \cdot \frac{10^{5}}{3000} = 3 \cdot 10^{8}$ work.
•  » » » 5 weeks ago, # ^ |   +18 How do you prove that it's always optimal to maximise $c$ for every subtree (and sometimes not the sum)?
•  » » » » 5 weeks ago, # ^ |   +28 Because reducing the sum cost you at most one village and that can be compensated by taking the maximum c.
•  » » » » 5 weeks ago, # ^ |   +26 This clearly holds for the root of the tree. Induction on distance from root.We'll show that for any $k$ we always find the maximum pair $DP[k] = (c, s)$ for the subtree of our current node by only considering the maximum pairs of its children. But this is trivial: The $c$ we get is just the sum of $c$'s of the current node's children, and the $s$ we get is just the sum of $s$'s for the children, so if we pick for any child a non-maximal pair, we either get smaller $c$ or equal $c$ and smaller $s$. The second case is clearly never optimal, and in the first case, if the (possibly increased sum) is positive, we get an upper bound of $(c, 0)$ for $DP[k+1]$, but we would get this anyway from $(c, s)$.
•  » » » 5 weeks ago, # ^ |   +10 i thought in a similar way, but thought that i should put c in the parameter of dp. Why can we pull c out of the parameter?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   -10 Let's say, we have 2 pairs {ans, sum} where the first one have a strictly bigger ans, but a much smaller sum compared to the second one. If you plan to take the second one, you are sacrificing at least 1 village to get a bigger sum. What's the point in getting a bigger sum? To later on, group it with something that will give you a "good" village, and at most 1 good one can be made.Therefore if you don't sacrifice this earlier village and later on you can't create a "good" village, it's practically the same thing. Therefore it's always better to take the one with the maximum ans.
•  » » » 5 weeks ago, # ^ |   0 Can you please tell what is $s$ here? I didn't get what is the meaning of the sum of the village. Do you mean $s = no. of wasps - no. of bees$? Sorry if it's a silly question.
•  » » » » 5 weeks ago, # ^ |   +5 Yeah, $s = \sum_{i \in \text{village}} \text{wasps}[i] - \text{bees}[i]$.
•  » » 5 weeks 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 antontrygubO_ohttps://codeforces.com/contest/1281/submission/66931104
 » 5 weeks ago, # | ← Rev. 2 →   +32 How to solve div1 D? answered
 » 5 weeks ago, # |   +3 it seems everyone(myself too :) ) messed up DIV2B due to over optimization. O(n^2) solution passed
 » 5 weeks ago, # |   0 DIV 2 B :-coding is not important than finding the edge case (What this problem said to me ?)
 » 5 weeks ago, # |   +8 I think F can be solved as follows:Put empty square in bottom middle always. Then you have two "dials", with a shared "center" square board[0][k].Now you can define some moves like L = u l^k d r^k = left dial clockwise by 1. Similarly you can define left/right dial clockwise/counterclockwise by 1. Using L^t you can do left clockwise by t, etc. Across all these shortcuts, the empty square is always in the bottom middle.Now your goal is to put the left dial correct except for 2 adjacent numbers, then put the right dial correct. You can do this just by spinning the dials. At the end, either the adjacent numbers are correct, or its not and the surgery failed. The existence of a failed testcase in the example proves that there is no "swap" operation, so the testcase is indeed impossible.
 » 5 weeks ago, # |   +37 Div1C(max case): https://codeforces.com/contest/700/problem/B
 » 5 weeks ago, # | ← Rev. 2 →   0 missed problem D because some silly mistake
•  » » 5 weeks ago, # ^ |   0 Same. In one case check I used r instead of c and vice versa and during whole contest trying to find a case where my solution is wrong.
 » 5 weeks ago, # |   +3 My submission isn't checked in system test. The submissions which submitted in minute 35 is checked but my submission is in minute 16 it doesn't checked why?
•  » » 5 weeks ago, # ^ |   0 Does it matter?
 » 5 weeks ago, # |   0 tight tl for div1 A ?
•  » » 5 weeks ago, # ^ |   0 Yeah, I got TLE for using mod.
•  » » » 5 weeks ago, # ^ |   0 damn ... me too i guess
•  » » » » 5 weeks ago, # ^ |   +16 I think test 18 is something like you have a string of length around $10^6$ and you do around $10^6$ paste operations while the length doesn't increase every time.
•  » » » » » 5 weeks ago, # ^ |   0 i handled it . i copied it s[i] — 1 times to the back .. maybe its about I/O
•  » » » » » » 5 weeks ago, # ^ |   +8 Did you create a new string of the suffix?
•  » » » » » » » 5 weeks ago, # ^ |   +2 yeah unfortunately now i understand .. :(
 » 5 weeks ago, # | ← Rev. 2 →   0 What if my submissions were AC during the contest, but have received TLE during system testing?
•  » » 5 weeks ago, # ^ |   0 Can I ask for rejudge or something like it? If yes, how?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Forget about it, looks like some tests have changed
 » 5 weeks ago, # |   0 How to solve Div.2 B?
•  » » 5 weeks ago, # ^ |   +4 just construct the minimal word you can and compare with the target.
•  » » » 5 weeks ago, # ^ |   0 I did the same, i think to construct the smallest possible answer then compare. I am not able to find my mistake ,as i got wrong on pretest 2.Here's the submission: 66923355
•  » » » » 5 weeks ago, # ^ |   +1 you should find the last charcter . for example "bbbbaa", minimal should be "abbbab", not "abbbba"
•  » » » » » 5 weeks ago, # ^ |   0 Thank you..I really missed that.
•  » » » » » 5 weeks ago, # ^ |   0 A lot of thanks, trying to find this got me strugling for a couple of hours
 » 5 weeks ago, # |   0 why am i not able to see other people's code (which is submitted)?
•  » » 5 weeks ago, # ^ |   0 It's system testing now...
•  » » 5 weeks ago, # ^ |   0 because System testing ~
•  » » » 5 weeks ago, # ^ |   0 system testing is over still i am not able to see other people's code :(
•  » » » » 5 weeks ago, # ^ |   0 Probably because the onsite is not yet over.
 » 5 weeks ago, # |   +9 is Div1 C Well-Known problem? Thinking solution about max case of problem C is some relevance of the previous problem I solved but I can't remember what the problem it is
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I think separating linear walk in a tree work for Min case . For Max case take edge which separates tree into two parts and get answer as the sum of subtree size * edgeWT , for all edges ;
•  » » 5 weeks ago, # ^ |   0 Can you share the approach to Div1 C? And also links to similar problems..
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   +1 min case -> sum all of the edge weight to min case answer and from root 1, if the path is x -> y and the number of child node of y is divided by 2, then subtract the x->y 's edge weight to the min case answerbecause if the number of child node is divided by 2, then the set of child node can match each other in any ordermax case -> from root 1, if the path is x->y and the number of child node of y is NUM, then add the min(NUM,child_node[1]-NUM)*(x->y 's edge weight) to the max case answerbecause Maxmizing use of all of the path x->y is optimalSurely, you choose any node to root
•  » » » 5 weeks ago, # ^ |   +1 i am not good at writing english.. So, if you can't understand what i replied above, i am sorry
 » 5 weeks ago, # |   0 MikeMirzayanov My submission isn't controlled and it is submitted in min.16
 » 5 weeks ago, # |   +1 Can anyone help me with the idea behind Div2 C?
•  » » 5 weeks ago, # ^ |   +1 Only implementation. I literally just implemented the operations, except the fact that if string length (which is always increasing very quickly) becomes $>x$, I didn't actually update the string, rather just updated the $length \% MOD$ of the string. And as the MOD-ed length can be less than $l$, be careful of that. My submission if you want: 66928873
•  » » 5 weeks ago, # ^ |   +1 Cut and paste until the string length is equal x.suppose, x = 7 and given string is "231" then construct the string it doesn't reach "2313113".Then iterate the whole string and increase the length if necessary.initially, length = length of the given string and we can assume that first index of the constructing string is 0 and last index x-1.For every character,If the character is '1' then length remains the same.If the character is '2' then length = i+1 + ((length-i-1)*2);If the character is '3' then length = i+1 + ((length-i-1)*3);Don't forget to use modulus.My solution — > https://codeforces.com/contest/1281/submission/66937956
 » 5 weeks ago, # |   0 Can anyone give me a hint on problem 2?
 » 5 weeks ago, # |   0 WA in problem B pretest 2
 » 5 weeks ago, # |   +5 Why submission is hidden? when submission can be seen?
 » 5 weeks ago, # |   +3 get a WA on div.2 D test 8...
 » 5 weeks ago, # |   0 In Div1C, can negating the edges to get the min answer if we find the max answer work?
•  » » 5 weeks ago, # ^ |   +3 In theory of course, but it depends on how your solutions works. If you have a general algorithm that handle any weight min/max is just the same.In this particular case my two solutions (for min and max) work for positive weight only, and I believe it was intended, so the answer to your question for this problem is no.
 » 5 weeks ago, # |   0 Spent almost 1 hour find O(N) solution in div2B because didnt realize that solution O(N^2) will pass :(
•  » » 5 weeks ago, # ^ |   0 Were you able to solve it in O(N)?
•  » » » 5 weeks ago, # ^ |   0 I did it in $O(n * 26)$ you can see my submission : 66933398
•  » » » 5 weeks ago, # ^ |   0 I did it in O(N+26), my submission : 66916571
•  » » » 5 weeks ago, # ^ |   0 I did it in O(nlogn) https://codeforces.com/contest/1281/submission/66905440
•  » » » » 5 weeks ago, # ^ |   0 Yeah, I did it in O(nlog n) too. But I was unable to think of an O(n) solution.
 » 5 weeks ago, # |   0 ProblemB Pretest 2 is this. Try below.1 GYYYYYYYTTTTTTTZ GTYYYYYYTTTTTTYZThe answer should be ---.What a bad problem:(
 » 5 weeks ago, # |   +4 In Div2 C when i just use for loop my solution got tle on test 18...66931998 bt when i just replace it from predefined substr string function my solution Accepted....66932640 but predefined substr function complexity is also O(n) then why it give TLe... Correct me if i am wrong...
 » 5 weeks ago, # |   0 Can someone share their approach for Div2 E ?
 » 5 weeks ago, # |   0 How to solve div. 2 D ?
•  » » 5 weeks ago, # ^ |   0 If there are no A's then you can not convert the matrix, so answer for this case is 'MORTAL'. otherwise, check for each row and column whether you can convert this row or column into all A's. If yes, then using this row or column you can convert entire matrix into A's. Take minimum at every step.
 » 5 weeks ago, # |   0 Isn't in $Div2 C$ if you Generate the string in each step it should give $TLE$. Because as far as I know string concatenation in $O(n)$ operation
•  » » 5 weeks ago, # ^ |   0 but predefined substr string function also takes O(n)...
•  » » » 5 weeks ago, # ^ |   +3 Same bro I didn't code the obvious solution because I thought it is $O(n ^ 2)$
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +5 Just make a character array of size about 10^6 , then you can generate that required string of length x in O(x).
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 You don't need a string whose length is greater than X to solve Div.2 C.
 » 5 weeks ago, # |   -23 buggy forces
 » 5 weeks ago, # |   0 What is subcase 136 in pretest 2 ?
 » 5 weeks ago, # |   +7 How to solve Div1 D?
 » 5 weeks ago, # |   -6 Brute force solution of Div2 task-B. Main check bool ok=false; rep(i,0,SZ(s)-1){ rep(j,i+1,SZ(s)){ if(s[j]>=s[i])continue; // important. if missing it will be TLE swap(s[i],s[j]); if(s
 » 5 weeks ago, # |   +11 For div1 C for max -> summation of distances of all nodes from centroid also works
 » 5 weeks ago, # |   +11 Please provide editorial
 » 5 weeks ago, # |   +3 Here is my approach for Div2 B — Azamon Web Services. Idea: We find the smallest string that can be obtained when we are allowed only a single swap. Let sorted string be $s'$. Now if the string $s$ is already sorted, then $s' = s$. But if string is not sorted, then we have an index $j \in [0, |s|)$ such that $s'[j] \neq s[j]$. We loop through $s$ to from the end to find this character (find $s'[j]$ in string $s$ from end) and let its position be $k$. We swap $s[j]$ and $s[k]$. This new string, call $s' '$ is the lexicographically smallest string obtainable from $s$ with one swap.Now simply compare $s' '$ and $c$. Complexity $O(|s| \log|s|)$ My submission : 66919628
 » 5 weeks ago, # | ← Rev. 2 →   0 I think I don't fully understand d. so is there a problem if we lose? ( I mean we must find the maximum in the cases that we dont lose the game ) ?If its a problem then how to solve the problem if we can lose the game to ( Stop at a city (Don't have enough soldiers) )
 » 5 weeks ago, # |   0 The problems were quite easy, the first four problems felt like they could been in a Div 3 contest. The problem D could be replaced a harder problem. :D
 » 5 weeks ago, # |   -13 I have solved problem 1281B - Azamon Web Services be with implementation code 66977057 Omg i am very happy for this accepted My rate geten up 115+ ^_^
 » 5 weeks ago, # |   0 Im getting a weird runtime error that question Question B can someone look into my solution ans help me. https://codeforces.com/contest/1281/submission/66990716
•  » » 5 weeks ago, # ^ |   +1 Hey, a possible source of error could be that you are varying $i$ according to size of string $s$ but don't check out of bound error for string $c$ (no mention of c.size() anywhere in code)
•  » » » 5 weeks ago, # ^ |   0 Yes I fixed it and it worked perfectly. Thankyou so much lemongrab
 » 5 weeks ago, # |   0 Does someone know what's the testcase 41 in test 2 problem B? Answer is IUWWWWWWUUUUUUWZ
•  » » 5 weeks ago, # ^ |   +1 In that test case you need to consider cases of equality of characters. For Example:- AAAGIZZB AAABZZE You can swap G with B to obtain AAABIZZG which is lexico smaller than AAABZZE
•  » » 5 weeks ago, # ^ |   +1 Try this on your solution1 EDDD DDDF 
•  » » 5 weeks ago, # ^ |   0 It helped me, thx!
 » 5 weeks ago, # |   0 Is ans >= 1000000007 very slow in python? I got TLE use if ans >= 1000000007 before ans % 1000000007? submissions: 67007248 and 67007151
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by kevinsogo (previous revision, new revision, compare).
 » 3 weeks ago, # | ← Rev. 2 →   0 Can someone help me with div1B/div2D. getting WA in 8