I'm honored to announce that Codeforces round #459 is going to take place on January 29th and Reyna and I are the problemsetters of this round.
I'd like to thank keyvankhademi, AlexFetisov, winger, Belonogov, cyand1317 and demon1999, AnPelec for testing, KAN for coordinating the round and MikeMirzayanov for the great Codeforces and Polygon platforms.
The main characters of the round are Stranger Things characters.
The scoring distribution will be announced soon.
Good luck and have fun.
UPD0: The round is over, we hope you enjoyed it. Editorial will be posted soon.
UPD1: System testing is over, congratulations to the winners.
Div.1 winners are:
And Div.2 winners are:
- Chaarzeh (Interesting :-?)
The editorial will be posted in a bit.
UPD2: Here's the editorial. Also please help me and Reyna do better next time by filling out this form.
I hope the problem statements are as short and concise as the announcement. Good luck to all!
Have been waiting for one of your round for a long time!
What is the significance in tags princeofpersia?
DarthPrince is PrinceOfPersia.
Also hi Monika :)
Hej Hej Monika Hej pa dig Monika XD
Where is my Delete key?
Be Careful !!
Your text to link here...
please don't include spoilers in the statements ...
I haven't seen the series yet
RIP rating in advance!
PrinceOfPersia is such a cool handle.
Hilarious story behind this handle
I hope, This round will make my handle Green !
On a scale from 1 to 10 , this round is gonna be Eleven
On a difficulty scale ^^
And div2 first question was Eleven...
was it a mystry??
I guess it was a notorious coincidence ;-)
He didn't mention if the contest is rated or not.
UPD: I know that all #Codeforces rounds are rated for Div/2 by default but it should be mentioned and putted in bold like any other contest announcement.
What's need announcement for it. it will occur unexpectedly. :D :D
You are right. But we should not downvote 'is it rated' questions as it is not mentioned
Wow!! At last picture-based problems are coming after a long time. :)
Mille Bobby Brown is dating the biggest douche on earth(Jacob Sartorius)...
If you don't know who that guy is, just don't watch a song called "sweatshirt" by him.
I REPEAT DO NOT LISTEN OR WATCH THE SONG SWEATSHIRT BY JACOB SARTORIUS.
Why are all comment sections on here filled with inane crap?
Lol that's because you don't watch stranger things
Damn, codeforces is the last place on earth where I expected to learn this, but it is kinda a fun fact. The more you know.
Good luck everyone! xD
Is it rated?
All official Codeforces rounds are rated by default. They would have mentioned it, if it is unrated because of any reason.
stranger things contest means stranger things on contest?
The author of the contest makes #406 Round. There were really cool problems. Hope it will be also helpful and interesting. High ratings for everybody!
I have watched Stranger things but I still don't recognize the character whose picture is in the post!? :')
I don't think it can be anyone other than Eleven. Correct me if im wrong.
Oh yeah, the cookie! ^_^
Eggos (brand of waffle)
i hope Dustin's rrrrr exists in the round
I got a reason to watch Stranger Things :)
A reason other than Stranger Things itself!?
Brace yourself, tough problems is coming...
Took me a long time to recognize Eleven in the post having waffle
I hate kids.
I hate you!
So this tv show has kids as main characters and you want me to believe it's not shit?
This is shit
Not total shit but kinda.
yes these are shit
Yes it's not shit. And that is because unlike many stories that feature kids, Stranger Things would not work if they replaced the kids with adults. For the story to turn out as it does, it is necessary for the protagonists to be kids. As summarized by Jared on Wisecrack (video spoiler alert),
It has been awhile before we got a rated contest
UPD: Very bad contest and my rating will decrease. Why C/Div2 is harder than usual?
I'm waiting an amazing contest!
Cant wait for the Stranger Things theme, hopefully the questions are as good as the show :)
map<map<int,int>,map<int,int>>M; How to access the map ?
why did you comment that here?
Any way you can access the map by another map
AMD is back :o
If you are planning to include stranger things themed pictures in problem statements, please use small low size pictures.
What's the compiling command for GNU C++?
it is gonna be data.. wait for it ..structure contest
preparing a robust version of HLD :D
Long time, no see, Hisoka :P
I came here to comment this, now I’m leaving.
pls be short and clear
Wait for it....
All the best for the round 4 + 5 = 9
Well,now my rating is 2017,I hope that I can get a rating of 2018 after this contest...
I hope this is a great contest!
scoring distribution ???
I am also waiting for the same.. Hope for the nice problemset. As expected from princeofpersia
The scoring distribution will be announced soon.
What does 'soon' mean?
UPD:Sorry, I didn't see this question has been asked
Stranger Things are going to happen
For Div2, I don't think that problem distribution has been in correct way. :(
Damn that trigraph in Div2C pretest2
I spotted a small lore inconsistency in Div2D:
"Max and Lucas are playing the game. Max goes first, then Lucas, then Max again and so on... Since the game could take a while and Lucas and Max have to focus on finding Dart, they don't have time to play."
Are they playing or are they not playing? Problem is very unclear about this. Make the round unrated. (JK)
problem C is very tough.. this contest is not meant for div 2!! I downvote!
its not tough its tof !
Div2/D If our graph will have consisted from one cycle and characters on the edges will be the same, will they play infinitely?
its DAG :/
DAG (Directed acyclic graph)
My rating is about to go Upside Down...
Am I the only one who thinks Div2D/Div1B was a little bit easier than Div2C/Div1A?
i thought C was easier.. maybe im not good at graph problems :)
Div1B was straightforward, Div1A was pretty tricky and I needed to think about it for few minutes and decided to go with a bet that seems fine to me but I didn't prove it carefully :x
yes , but both traditional
Seems like in both divisions D is easier than C (considering the number of successful submissions).
Because it is a classic game theory problem.
anyone can explain D.. I spent 1 hrs, but i can't find the answer
Use Dynamic Programming
Wow, that will help.
dp The 2 is for turn Emulate the whole situations. O(N^3C) time complexity where N is # of vtx, C is # of alphabets
Note that you can drop 2 easily. That is, to have dp[a][b][c], by storing whether the current first player wins when he is in vertex a and the second player is in vertex b.
Good advice. Always dp = !dp
I used an array state[A][B][x] to store all the possible situations, where A is the position to move first, B is the position to move second, and x is the limitation(i.e. only edges whose weight >= x can be used). Then all these nodes form a game tree. then update each node in topology-sort order, i mean, from leaves to root and make sure you visit all children nodes before you visit a node itself. Then the problem is simple. if there exists a child of a node is "first move to lose" then this node should be "first move to win", otherwise "first move to lose". All you need will be state[i][j].
I'm still waiting for system test, hopefully I'll pass :P
UPD:It passed now XD
now i understand it. thanks for all help!
Very nice contest and nice pretests :D
That moment when I made the best performance in Div2A/Div2B, then got stuck for the next 115 minutes...
P/s: Can anyone give me a hint with C/D?
for C: you will count which starts with ith character let number of ( : a, ? : b, ) : c if c>a+b, then it means if we change all ?s to ), it is impossible so, it is always impossible!(for example, (?))) is always impossible!)
similary, we can think something like a>b+c, (for example, (((?) )
Hope my comment helped you..
Hmm, but what about cases when the order of the characters matters?
"(?"is a pretty string, while
"?("is not (however following characters may make it pretty, i.e.
first, ")?"(which is not in your examples though) can be shown impossible by my first comment. and lets check "?(" these kind of things, which is impossible because there are too many '('s at the right. choose one variable a=0 from front, if there is (, add 1 on a. if there is ) or ?, we can decrease 1 on a. But if a=0, we don't have to decrease it, since we can choose '(' rahter than ')'. if it is ), then we can think from right of it. So if a=0, add 1 on a, else, decrease 1 on a. if variable a is negative, it means it is impossible.
now we can verify "?(" these kind of things.
hope i made you understand this :) have a nice day!
UPD: edited a little bit!
Hmm, seems like I'm getting your idea — prioritizing the opening bracket.
I was complexifying my own work by judging the '?' characters separately, therefore I encountered a whole variety of bugs without a proper solution. Turns out it was so simple.
Many thanks! ;)
For D, since you can get every possible state, just see the states that each state can go to, if any of them is winning, then the current state is winning, losing otherwise.
After reading your hint and a few more comments, I'm getting it now.
Heck, no wonder some says it is easier than C. Well, I can't blame myself anyway, anyone has his/her own bad days/periods.
Thanks for the support! ;)
Div2C, I stuck in pretest 3/7 :(
Isn't Div. 1 D a special case of this?
Also, it has appeared on topcoder: https://community.topcoder.com/stat?c=problem_statement&pm=13369
Are you sure this is correct link :P?
Oops I accidentally deleted a character :P
I'm really sorry... I wasn't aware that it's been given before until now. I'll avoid making problem with short statements without researching thoroughly. I hope Codeforces community is kind enough to forgive me and give me tips to avoid such mistakes in the future.
No worries, it's understandable, problem collisions happen every now and then. I think it's still a bit hard to search for this specific problem unless you've seen it before.
Any idea what could be the test case 4 for div2 C ? I was stuck on this throughout the contest :'(
No idea, but I have a hack for your code: ())?
Thanks man.My algo was wrong then :'(
I am in Love with Problem D, thanks for the amazing problem :D
can't understand the problems.... want more explanation of the sample case...
I think that is why so many participants passed div1.D...:)
Another similar problem is from XV Open Cup (2014-2015) GP of China.
Problem I: http://opencup.ru/files/ocf/gp10/problems1-e.pdf
CF discussion: http://codeforces.com/blog/entry/16701
Is there a normal solution for Div.2 C that has complexity like O(len^2)? My only thought was to use bitsets with O(len^3 / 64)...
any idea for Div2C? It seems very tough for me :(
For each starting position, calculate the upper/lower bound for each ending position. You may reduce the time complexity if you do that in left to right. If the upper goes negative, you should stop. Otherwise, just check that upper >=0 which means there are some good solutions. (No matter what they are)
case '(': upper++,lower++ // case ')': upper--,lower-- // case '?': upper++,lower--
What is the use of lower? Should it be 0 at the valid end positions?
Does this work for:
In case of the lower going below 0, you should adjust it as 0. It forces '?' to be ')' in some cases. In case of '()?)', ? should be '('. After fixing lower to be >=0, it could fluctuate around 0 and finally affects to the desired answer.
Its not clear what upper and lower bound are actually counting?
Is it counting length of the pretty string?
In that if
((is the input string
>= 0. But that's not valid string. I am clearing missing something here, don't know what.
Also: Is it a standard problem as some have solved it in 4 mins?
I think I didn't give you a full explanation.
But in case of that, lower is 2.
The key idea is that if lower ≤ 0 ≤ upper, we can always expect that there exists some solution.
In addition, for ??))))((((), let me consider the cases only starting from the first position,
(we can only expect pretty one with even length)
How does someone come up with that idea? Why this always works?
What are actually upper and lower.. seems like top and bottom end of a stack which can be successfully emptied if its a balanced bracket, perhaps not.. still confused what the heck is upper and lower magic
I came up with the stack, right. They denote possible range of stack size when you check the given string of parenthesize is correct, even thought it is not tightly (lower)bounded near 0.
nice solution after reading your code:)
Sooo, I spent 1.5 hours writing approach for d1E, it was about 330 LoC at the end of contest and it was not even nearly enough to get something working ;_;
+1 (spent 1.5 hours on ), thought I found a small mistake which I couldn't fix.
I tried to solve for all length ≤ K separately with hash and for strings having length > K with centroid decomposition but I didn't even came to writing second part. I'm not even sure my solution is enough to get accepted.
The contest should be unrated because you did not announce the scoring.
Trying to save my rating.
You're a pupil, what rating are you trying to save? :p
You was a pupil too :P
Ratism is the best
hey purple :P
Wow this is impressive. I take back my words :)
Problem A Div2 was inspired by amiya
I wonder how long he takes to login :P
how to solve D?
You can use topsort. Than start back from the nodes and calculate next dp values : dp[currentplayer][previouscharacter][firstnode][secondnode].
I meant div1 D
For that you have links above :P
Notice that the value for k = 0 is the number of spanning trees of the complement of the input tree. This can be computed by the matrix-tree theorem (https://en.wikipedia.org/wiki/Kirchhoff's_theorem).
Using https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem#Explicit_enumeration_of_spanning_trees, we can know that if we compute the determinant of the Laplacian matrix of a complete graph with weight X for edges in the input tree, and Y for the other edges, we get a polynomial where the coefficient of XaYb gives us the number of spanning trees of the complete graph with a edges inside the input tree, and b edges outside (Since spanning trees have n - 1 edges, a + b = n - 1). We can compute this polynomial by interpolation.
Because we need to evaluate in n points, and the cost of each evaluation is O(n3) (or better with faster algorithms for computing determinants), the complexity is O(n4)
Your solution sounds much more fit to Div 1's.=D
Why is given graph a tree then?
In order to allow other solutions, quite clearly :). Mine heavily uses fact that it is a tree.
Because that is not the only solution. Mine works only on trees and likely, so does the official one
My solution is different I guess. Although I think that can also solve the problem for a graph. One of the testers had a similar solution for the problem (I didn't think of the graph version though). He also reduced it to n ^ 2 for trees. We didn't change the problem because we thought it would be too hard.
If you are allowed, please share the novel O(n^2) solution.
I'll make a place for it in the editorial, although I don't completely understand the solution.
Here is the version winger told me.
__ It's based on generalized Kirchhoff's theorem: if we take Laplacian matrix with x for edges in the original tree and 1 for edges not present in it, it's (polynomial in x) minors will be the answer.
So, let's calculate this minor for every x in [0, n) and interpolate to find the answer. To compute the minor in linear time, notice that it can be computed as det(D-(x-1)*F-E), where E is (n-1)x(n-1) matrix on ones, D is some diagonal matrix and F is incidence matrix of some forest (produced by removing a vertex from original tree). It can be computed with a tree-DP in linear time.
Look forward to the editorial for a detailed solution. Thanks, @Reyna.
As the DP you described involved polynomial multiplication, we can use interpolation to get O(n3) solution.
However, O(n2) seems to be mysterious for me so far.
Polynomial interpolation is O(n ^ 2) from what seems to be on the wikipedia page XD.
So we just have to calculate the determinant of det(D — (x — 1) * F — E) where E is an (n — 1) * (n — 1) matrix with all 1's and F is the adjacency matrix of a tree and D is diagonal. OK now let's try to calculate their determinant by choosing a permutation and a 3 ^ n (actually n — 1, but just assume the tree has n + 1 vertices) representing if the (i, p[i]) is chosen from E, D or F * (x — 1).
Fact: Let's look at the determinant as partitioning the graph into cycles and assigning each edge a tag (which can be 0, 1 or 2 depending if it's picked from E, D or F * (x — 1)). The determinant will be the product of the edges (for edge (u, v) it would be E[u][v] or D[u][v] or (F * (x — 1))[u][v] depending on the tag). Okay, now I'll claim that we don't use E tags more than once! (sum of those which use E tags more than once is zero, we can prove that by swapping 2 E tags, although the details aren't easy to me). If we use zero E tags, the answer will be only the product of D's diagonal (because trees can't make a cycle). Otherwise It'll be a path with an E tag connecting both ends and all others are loops.
Now label the vertices with starting time and denote ed[v] as the ending time of vertice v. Assume that we have a path from x to y and their LCA is p. from x to the vertex below p and from y to the vertex below p, they don't affect each other in the inversion (because they're from some px (below p from x) till ed[px] and py (below p from y) till ed[py] and these two segments don't coincide). so only from px to p and p to py affect the inversion (if we have the inversion from the paths below). We can also find the inversion from x to px with dp. I should probably write down these details in the editorial. I just found the solution (with the hints from winger) right now, so I'm not sure about the details.
Don't hesitate to ask me for more elaboration or explanation.
EDIT: It's wrong right now... I'll see what I can do to fix it
When we use zero E tags the answer is sum over all matchings of given tree(because we can still use v->u and u->v edges). I don't understand the last part but it probably gets more complicated too.
Yeah, you're right, I have to think a lot more now XD (because in the second part I also ignored the matchings and it gets much more complicated).
I'll be thankful if winger could explain a bit. I can also share his code if he allows me to.
Okay, I think it can be fixed with the fact that a swap (which is like (u, u) and (v, v) to (u, v) and (v, u)) changes the inversion parity, so we can just assume that all of them are in their place but keep in mind to multiply by -1 each time we match edges. So we can match the edges or loops in the whole process. It'll complicate things, but I guess it works?
Well, (u, u) and (v, v) use values from D and the other two use values from F so I don't think they cancel each other out or something.
Yeah, they are indeed from F, but my point is that they just change parity so we can assume that they are in their place in the permutation after multiplying by F[u][v] * F[v][u] * -1. We have to also update the dp's with matchings which I didn't notice before. They don't change the solution that much, they just make it much harder to code XD.
Finnally, got accepted with O(n2) solution.
Wow! Orz! It's actually pretty hard imo XD
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
That`s not true buddy!! Div2A/B was easy! Yes, C was tougher then regular!
A royal contest, Prince + Queen (Reyna in spanish)
The problems C+ where really hard.. Cool actually
In this contest I found that a code which submitted by other one ( after me) is almost the same as mine. I want to say that I didn't give my code to anyone and I don't like this behavior at all.
Did you use an online IDE or accidentally leaked your password? This happens from time to time and is really strange.
I think someone had access to my account by my mistake.
wich code ?!
The best choice is updating your password immediately, this happened to me last year.
I updated it after the contest. Thanks for your comment.
Wow, going to such lengths for solutions..
Memoization is clean for Div1 B: http://codeforces.com/contest/917/submission/34673801
It's actually strikingly amazing how similar my solution is to yours :D
good understandable code.
You can simplify it further by taking out the 4th dimension of your DP array. If you just store whether the current "first" player wins, and then recurse by switching u and v, and determining that current position is a win if it can recurse into a loss for the first player, or is a loss otherwise.
I got Idleness limit exceeded on pretest 1 on Problem D although it runs on my PC and on Ideone and now i got the same verdict in problem A after it passed the pretests !!!
UPD: the same for Problem B
UPD2: they were rejudged , thanks MikeMirzayanov.
Same happened for my Solutions for div2 A and div2 B.
My guess is that it's because you've used "GNU C++17 Diagnostics" compiler, which runs a bunch of debug tools alongside with your solution. They may significantly slow down the solution or even don't work during the contest at all.
MikeMirzayanov, is it indeed the case?
Sure. It seems it is good idea to hide such compilers from the submission interface in a contest. But allow them on the custom invocation tab.
And the scoring distribution is never announced...
Meanwhile the system testing seems to be neverending as well...
... even when all submissions were judged.
Div 1 not done judging
Hmm then this one is weird... "Final standings"?
UPD: Got it now. Nevermind then.
I am surprised that C got 16 ACs and D got 43 ACs. To me it seems that C is maybe not straightforward but kinda standard and easy exercise on matrix exponentiation whereas D seemed to me like a really tough problem. It seems that D was too widely known (but I didn't know it before) and also it allowed both (I guess intended) approach with generalized Prufer codes, dp on tree and dealing with multicounting and also an approach based on Kirchhoff theorem.
C allows both standard matrix multiplication and dp (with some greedy speedup).
UPDATE: Perhaps I am wrong...
Well, these matrices is also some kind of dp :). But you surely meant something entirely different, can you describe your approach?
Sorry...I might just make an insane comment. But I go with such approach during the contest.
Thinking of x = 1, if two consecutive stones is far apart, it should jump with some k where c[k] / k is minimized. I guess this can be generalized to x > 1. So we can compute the dp step by step around the stone, and use the above hypothesis to skip large gaps.
This is not clear yet, but I think you are on to something and intuitively this problem should be solvable without any dependence on n in time complexity. Btw, I see a notable connection between this approach and this P6 IMO 2010 problem https://artofproblemsolving.com/community/c6h356197p1936918 :P (which by the way doesn't really deserve to be IMO P6)
wow! the aops link looks cool!
Finally I realized that I missed the ``the leftmost pollywog should jump to the right'' part in the statement, which causes (1) I did not solve in the contest (2) invalidate my hypothesis (as we cannot shift x frogs together now...)
Haha, yes xD. Without that condition it is entirely different problem. However your version (without that "leftmost" part) can be solved by solving x^2 subproblems with x=1 and applying Hungarian at the end. Main observation here seems to be that these subproblems can be treated independently because we can get rid of any collisions that would appear throughout whole process by some swapping targets argument. Because this reduces to independent problems for x=1 this greedy optimization can easily be applied in your version and doing k^3 single steps before and after every special point and using only best move between these parts is sufficient.
I believe similar "depumping" arguments can be applied in original version as well, but it will be messier and code will be harder than doing exponentiation. But we would get rid of log n factor which is nice, but we would get some new factor depending on k which will annihilate this profit.
Maybe there's a similar problem...(link)
my first ever B 'accepted', thought that I improving my skills but... the fact is, it was easy......... :-(
I suppose I will be specialist on this contest first time. The problem A,B were quite easy that is why almost every participant solve it. BUT MY ONE HACK PLAYS A BIG MATTER HERE!
It's a lesson for you after all.
I'm not sure what does "my one hack" mean in this case.
If it was an unsuccessful hack, then a lesson about caution. Do not take ruthless action unless you are 100% sure about that. (I myself regretted such actions several times actually :P )
If you were hacked, then a lesson about case-handling. Double-check your work before (or maybe after) submitting.
No, I hacked somebody,+100 points have a big impact in the results. Because almost all participants have a near results to each other.
Haha, then good for you. Congrats! :D
What is the complexity of the DP solution of D?
Is it O(m*n*26)?
Can you explain the complexity of your solution?
O(n * n * (50 + n + m))
O(n*n*26*2 + m) i guess
But every edge can be traversed n times(every node that the other participant is in)
yes! i didn't notice it.. m will be multiplied with n..
Yes. However, in this problem, m is O(n^2), so to tell it O(26*n^3) is also okay. Actually it will be more convenient to do it in complexity O(26*n^3).
A was very much hackable with overflows but its difficult to come up with such cases.
waiting for ratings...
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
amiya's nick... Algorithm from Problem A, isn't it? ^o^
Attention! Your solution 34680762 for the problem 918D significantly coincides with solutions PuPpEy/34680021, EliasM/34680268, Aldanyshov/34680302, soohotiam/34680762, kitkat_coder/34684071. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.
MikeMirzayanov hey plz. resolve this. I didn't know those guy. u can check our msge.ur code checker is very poor. plz. update this. and update my profile. plz check. we are not same and we are not kelnew each others. plz. it is totally wrong
They are exact same codes:
I think my id was hacked. . fuck
they submitted before you
but I faced problem when I submit my code on cf. then those fucker hack my solution. it is totally wrong. I always write big name variable but they no do this. -_- -_- plz they hack my solutions.
plz help me. :( plz.
plz see the submission time and and ban those id. plz.those id isn't mine
MikeMirzayanov plz resolve this. I am afraid for this. ban those ids. those ids isn't mine.
hey when I submitted my solution then automaticlly sign out frm me. at last 20 minute I didn't submitted my D No solution. plz help me. those id isn't mine. and I always do those type code.
One quick advice for you: change your password to something not so easy to be guessed. One of my friend got infiltrated, thrice, because of his
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
How can I solve DIV2 C with DP?
why this solution get a much greater answer for 917A? I've really no idea
Submitted this solution on the contest and got wrong answer on test case 1. But it showed everything ok on my pc. Can anybody help with what's wrong here? :/
It works if you read n, m using
cin>> n >> m;
ios_base::sync_with_stdio(false);, but then you mix printf/scanf and cin/cout. can't do that.
I am sorry to say that but unfortunately data set of problem B maybe weak 918B - Радиостанция
check this my wrong solution : 34674890 which was accepted
I am sorry for informing this lately..
not wrong, its just not strong enough to catch your bug. Also, many people had overflow bug in A but since its difficult to come up with a hack we have to settle with systests.
Updated my statement, thank you .
What's the point in making such huge problem statements ?
https://ideone.com/Gb6GiQ Very good solution for 3-rd task, if anyone needs.
Very good round, I really enjoyed it.
Div.2 A using regular expression: 34722038 (and B — 34722359)