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 Dec/15/2019 08:05 (Moscow time). 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 (jabbawookiees), 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!
Update: The editorial is up: Click here.
Congratulations to the winners! Congratulations to ksun48 for winning the Div. 1 round, and I_am_single 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!
Auto comment: topic has been updated by kevinsogo (previous revision, new revision, compare).
Is it normal that there are two contests at the same day?
Pfff, is that really a problem for you?
Sometimes I even write three contests per day!
wow, how do you do that?
First write first contest, then second and third ones
Cool story
Live in Kamchatka
wtf?
I am confused.
You can do both the contests but say goodbye to sleep. I did that once and still got a good score.
So, now its possible to make a perfect 'T' shape in the rating curve. :3
I think I was wrong... a perfect 'L' is possible...not 'T' :3
Will the problems be in English only?
As usual: English and Russian.
why was div2(606) contest held at such time ,also why not even one of 607 and 608 ,at a usual time??
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).
What will happen if a candidate master who has registered #608 officially becomes master in #607? Will he/she still be rated in #608?
Of course not
Are there plans to upload the full contest onto codeforces gym? I am very much looking forward to this contest
Yes, I plan on uploading the full set in the gym in the future, along with some past ICPC Manila problem sets too.
Auto comment: topic has been updated by kevinsogo (previous revision, new revision, compare).
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?
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.
kevinsogo is the chief judge of ICPC Manila, that's why he has "early access."
Вы неправы
хотелось поломать B, а теперь придётся плакать
(
so funny,me too：D
What did people get hacked on in B?
answer can be 0
How to solve Div1 C?
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.
What is pretest 2 in Div 2 B ?
What ever it was, it was the death of me xD Had like 15 submissions xD
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... :(
Luckly not that much, just around ~14.
What was the corner case in Pretest 2? I still couldn't figure out.
My code failed
BANANA APPLE:(for test case : IA GOG why AI is not the answer?
AI is the answer.
got it !
My code failed on BAA AABA. My code produced ABA and told me that it's impossible since it is smaller than AABA. smh
As a grey, I solved A in 4 mins then stuck on B until contest ended. Still got positive delta.
Try
EBB BBF
It took a lot of time to solve Div.2 B :(
What was pretest 2?
Div.2 B is a bad problem. There was no test in Div.2 D where the answer was 0.
For which case?
Div.2 D for this test case answer is 0.
3 3
AAA
AAA
AAA
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.
wrong :/
Wow, that's a slick proof. Thanks.
EDIT: Apparently not.
It’s not always possible to split into K and K. For example, a star with 4 nodes.
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.
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.
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.
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.
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$$$.
Centroid can help you prove this
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 help
Code:
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
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 :(
How? What made it so easy after reading constraints? Did you get to know why your solution was failing on pretest 2?
I think that means you can use O(n^2) algorithm to solve this problem. (But I implemented one and still failed...)
Now I passed the pretest 2 using O(n^3) sol (finally!!), but got TLE at pretest 10
O(n^3) would never work as cube of 5000 is like 10^11
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))
I did it in O(nlogn) :P
66935678
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.
sum of squares is at most the square of the sum.
Oh, just realised that. Can I then know the cause of TLE of my submission below?
https://codeforces.me/contest/1281/submission/66904986
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.Thanks!
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.
n^2 solution passes
Really mine gave TLE on pretest 10.
My O(n^2) solution passed. Sum of strings can only be upto 5000, and TL is 2 secs.
This is one of my submissions, which should be correct as far as I could think of : 66909918.
Try
AMGMG,AGMWow, My solution fails on that testcase. How did you make that case?
Is the answer is $$$AGGMM$$$. I don't know why my code is failing on test case $$$2$$$
I'm also getting the same answer, but WA on Test case 2
Thanks for this case!
My solution fails on this test case. Thanks.
Also try
BANANA APPLEI'm getting
AANANB. But WA on Pretest 2Tried
APPLEC APPLE?Yes. Getting
ACPLEPLOL at me. I misinterpreted "lexicographically smaller".
What is pretest 6 in div 2 C?
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
For me, on replacing $$$x \% p$$$ by $$$(x \% p + p) \% p$$$, I got AC.
Probably the same, because my neg method basically does this
Just my personal opinion (not only my actually), but I didn't like this contest at all
A: it's harder to understand the statement than to solve the problem
B: just case check
C: superfamous problem
D: maybe I shouldn't judge on it if I didn't solve it in time, but isn't it a super standard dp problem
E: 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
what dp in D? I hardcoded the cases of ans = 4/3/2/1/0, and that seemed to pass..
that's Div1B
oh right, my bad, you're div 1..
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".
agree
How you solved D with dp ?
Shouldn't an hour be enough to code up a "super standard dp problem"? :P
I was trying to do E instead T_T
Shouldn't an hour be enough to code up an easy parsing problem, everything in brackets, all tokens are of length 1 etc?
Not for a dumbass like me
easy for you to say, not everyone is a programming god
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.
How do you prove that it's always optimal to maximise $$$c$$$ for every subtree (and sometimes not the sum)?
Because reducing the sum cost you at most one village and that can be compensated by taking the maximum c.
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)$$$.
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?
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.
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.
Yeah, $$$s = \sum_{i \in \text{village}} \text{wasps}[i] - \text{bees}[i]$$$.
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_o
https://codeforces.me/contest/1281/submission/66931104
How to solve div1 D? answered
it seems everyone(myself too :) ) messed up DIV2B due to over optimization. O(n^2) solution passed
DIV 2 B :-coding is not important than finding the edge case (What this problem said to me ?)
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.
Div1C(max case): https://codeforces.me/contest/700/problem/B
missed problem D because some silly mistake
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.
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?
Does it matter?
tight tl for div1 A ?
Yeah, I got TLE for using mod.
damn ... me too i guess
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.
i handled it . i copied it s[i] — 1 times to the back .. maybe its about I/O
Did you create a new string of the suffix?
yeah unfortunately now i understand .. :(
What if my submissions were AC during the contest, but have received TLE during system testing?
Can I ask for rejudge or something like it? If yes, how?
Forget about it, looks like some tests have changed
How to solve Div.2 B?
just construct the minimal word you can and compare with the target.
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
you should find the last charcter . for example "bbbbaa", minimal should be "abbbab", not "abbbba"
Thank you..I really missed that.
why am i not able to see other people's code (which is submitted)?
It's system testing now...
because System testing ~
system testing is over still i am not able to see other people's code :(
Probably because the onsite is not yet over.
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
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 ;
Can you share the approach to Div1 C? And also links to similar problems..
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 answer
because if the number of child node is divided by 2, then the set of child node can match each other in any order
max 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 answer
because Maxmizing use of all of the path x->y is optimal
Surely, you choose any node to root
i am not good at writing english.. So, if you can't understand what i replied above, i am sorry
MikeMirzayanov My submission isn't controlled and it is submitted in min.16
Can anyone help me with the idea behind Div2 C?
Only implementation. I literally just implemented the operations, except the fact that if string length (which is always increasing very quickly) becomes $$$ \gt 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
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.me/contest/1281/submission/66937956
Can anyone give me a hint on problem 2?
Why submission is hidden? when submission can be seen?
get a WA on div.2 D test 8...
In Div1C, can negating the edges to get the min answer if we find the max answer work?
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.
Spent almost 1 hour find O(N) solution in div2B because didnt realize that solution O(N^2) will pass :(
Were you able to solve it in O(N)?
I did it in $$$O(n * 26)$$$ you can see my submission : 66933398
I did it in O(N+26), my submission : 66916571
I did it in O(nlogn) https://codeforces.me/contest/1281/submission/66905440
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...
Can someone share their approach for Div2 E ?
How to solve div. 2 D ?
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.
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
but predefined substr string function also takes O(n)...
Same bro I didn't code the obvious solution because I thought it is $$$O(n ^ 2)$$$
Just make a character array of size about 10^6 , then you can generate that required string of length x in O(x).
You don't need a string whose length is greater than X to solve Div.2 C.
buggy forces
What is subcase 136 in pretest 2 ?
How to solve Div1 D?
For div1 C for max -> summation of distances of all nodes from centroid also works
Please provide editorial
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
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) )
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
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+ ^_^
Im getting a weird runtime error that question Question B can someone look into my solution ans help me. https://codeforces.me/contest/1281/submission/66990716
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)Yes I fixed it and it worked perfectly. Thankyou so much lemongrab
Does someone know what's the testcase 41 in test 2 problem B? Answer is
IUWWWWWWUUUUUUWZIn 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
It helped me, thx!
Is ans >= 1000000007 very slow in python? I got TLE use if ans >= 1000000007 before ans % 1000000007? submissions: 67007248 and 67007151
Auto comment: topic has been updated by kevinsogo (previous revision, new revision, compare).