### DarthPrince's blog

By DarthPrince, history, 3 months ago, ,

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:

1. MeshOmarYasser
2. Chaarzeh (Interesting :-?)
3. magicalCycloidea
4. Maxon5

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.

•
• +750
•

 » 3 months ago, # |   +48 I hope the problem statements are as short and concise as the announcement. Good luck to all!
 » 3 months ago, # |   +4 Have been waiting for one of your round for a long time!
 » 3 months ago, # | ← Rev. 3 →   +2 What is the significance in tags princeofpersia?
•  » » 3 months ago, # ^ |   +16 DarthPrince is princeofpersia.Also hi Monika :)
•  » » » 3 months ago, # ^ |   +22 Hej Hej Monika Hej pa dig Monika XD
•  » » » » 3 months ago, # ^ |   +8 Where is my Delete key?
•  » » » » 3 months ago, # ^ |   +9 I skratta'd
•  » » » » » 3 months ago, # ^ |   +7 You förlorar'd
 » 3 months ago, # |   -46 Be Careful !!Your text to link here...
 » 3 months ago, # |   +73 please don't include spoilers in the statements ...I haven't seen the series yet
 » 3 months ago, # |   +32 RIP rating in advance!
 » 3 months ago, # |   +26 DarthPrince is such a cool handle.
•  » » 3 months ago, # ^ |   +5
•  » » » 3 months ago, # ^ |   0 Haha. He is good with handles, I see.
 » 3 months ago, # |   +3 I hope, This round will make my handle Green !
 » 3 months ago, # |   +91 On a scale from 1 to 10 , this round is gonna be Eleven
•  » » 3 months ago, # ^ |   +81 On a difficulty scale ^^
•  » » 3 months ago, # ^ |   +4 And div2 first question was Eleven...was it a mystry??
•  » » » 3 months ago, # ^ |   0 I guess it was a notorious coincidence ;-)
 » 3 months ago, # | ← Rev. 3 →   -45 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.
•  » » 3 months ago, # ^ |   0 What's need announcement for it. it will occur unexpectedly. :D :D
•  » » » 3 months ago, # ^ |   -35 You are right. But we should not downvote 'is it rated' questions as it is not mentioned
 » 3 months ago, # |   +8 Waiting !!!
 » 3 months ago, # |   +8 Wow!! At last picture-based problems are coming after a long time. :)
 » 3 months ago, # |   -33 Fun Fact: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.
•  » » 3 months ago, # ^ |   +38 Why are all comment sections on here filled with inane crap?
•  » » » 3 months ago, # ^ |   -23 Lol that's because you don't watch stranger things
•  » » » » 3 months ago, # ^ |   +5 :\
•  » » 3 months ago, # ^ |   -10 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.
 » 3 months ago, # |   +17 Totally Tubular! Good luck everyone! xD
 » 3 months ago, # |   -61 Is it rated?
•  » » 3 months ago, # ^ |   +5 All official Codeforces rounds are rated by default. They would have mentioned it, if it is unrated because of any reason.
 » 3 months ago, # |   +3 stranger things contest means stranger things on contest?
•  » » 3 months ago, # ^ |   0 no
•  » » 3 months ago, # ^ |   +4 Maybe Unrated...
 » 3 months ago, # |   0 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!
 » 3 months ago, # |   0 I have watched Stranger things but I still don't recognize the character whose picture is in the post!? :')
•  » » 3 months ago, # ^ | ← Rev. 2 →   +8 I don't think it can be anyone other than Eleven. Correct me if im wrong.
•  » » » 3 months ago, # ^ |   +2 Oh yeah, the cookie! ^_^
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +6 Eggos (brand of waffle)
 » 3 months ago, # | ← Rev. 2 →   -63 The comment is hidden because of too negative feedback, click here to view it
 » 3 months ago, # |   -21 HYAHNAHAHAHHAHAHAH
 » 3 months ago, # | ← Rev. 4 →   -24 hahahahahahahaha
 » 3 months ago, # |   0 i hope Dustin's rrrrr exists in the round
 » 3 months ago, # |   0 I got a reason to watch Stranger Things :)
•  » » 3 months ago, # ^ |   +15 A reason other than Stranger Things itself!?
 » 3 months ago, # |   +8 Brace yourself, tough problems is coming...
 » 3 months ago, # | ← Rev. 2 →   +14 Took me a long time to recognize Eleven in the post having waffle
 » 3 months ago, # |   +26 I hate kids.
•  » » 3 months ago, # ^ |   +14 I hate you!
•  » » » 3 months ago, # ^ |   +3 :(
 » 3 months ago, # |   +32 So this tv show has kids as main characters and you want me to believe it's not shit?
•  » » 3 months ago, # ^ |   0 This is shit
•  » » » 3 months ago, # ^ |   +4 Not total shit but kinda.
•  » » » 3 months ago, # ^ |   +8 yes these are shit
•  » » 3 months ago, # ^ | ← Rev. 2 →   +16 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), "..the kids don't save the day despite being kids, they save the day because they were kids.."
•  » » 3 months ago, # ^ |   0 yes
 » 3 months ago, # | ← Rev. 3 →   +6 It has been awhile before we got a rated contestWaiting ❤UPD: Very bad contest and my rating will decrease. Why C/Div2 is harder than usual?
 » 3 months ago, # |   +4 I'm waiting an amazing contest!
•  » » 3 months ago, # ^ |   -24 No, u are only waiting amazing rating
 » 3 months ago, # |   -27 CF pe aayegi aandhi, jab khelega anant gandhi
 » 3 months ago, # |   +4 Cant wait for the Stranger Things theme, hopefully the questions are as good as the show :)
 » 3 months ago, # |   -30 map,map>M; How to access the map ?
•  » » 3 months ago, # ^ |   +6 why did you comment that here?Any way you can access the map by another map map,map> M; map S; M[S][0] = 1; cout << M[S][0]; 
 » 3 months ago, # |   +4 AMD is back :o
 » 3 months ago, # |   +42 If you are planning to include stranger things themed pictures in problem statements, please use small low size pictures.
 » 3 months ago, # |   -10 What's the compiling command for GNU C++?
 » 3 months ago, # |   -24 I don't think it is rated.
 » 3 months ago, # | ← Rev. 2 →   +91 it is gonna be data.. wait for it ..structure contest
•  » » 3 months ago, # ^ |   +42 preparing a robust version of HLD :D
•  » » » 3 months ago, # ^ |   +3 Long time, no see, Hisoka :P
•  » » 3 months ago, # ^ |   +38 I came here to comment this, now I’m leaving.
 » 3 months ago, # |   +8 pls be short and clear
 » 3 months ago, # |   -8 ahhh.....rated ;)
•  » » 3 months ago, # ^ |   0 Wait for it....
 » 3 months ago, # |   0 GLHF :D
 » 3 months ago, # |   +9 All the best for the round 4 + 5 = 9
 » 3 months ago, # |   +31 Well,now my rating is 2017,I hope that I can get a rating of 2018 after this contest...
 » 3 months ago, # |   +1 I hope this is a great contest!
 » 3 months ago, # |   +16 scoring distribution ???
•  » » 3 months ago, # ^ |   +9 I am also waiting for the same.. Hope for the nice problemset. As expected from princeofpersia
•  » » 3 months ago, # ^ |   0 me also waiting
 » 3 months ago, # | ← Rev. 2 →   +9 The scoring distribution will be announced soon.What does 'soon' mean?UPD:Sorry, I didn't see this question has been asked
 » 3 months ago, # |   0 Stranger Things are going to happen
 » 3 months ago, # |   +1 Scoring???
 » 3 months ago, # |   +4 For Div2, I don't think that problem distribution has been in correct way. :(
 » 3 months ago, # |   0 Damn that trigraph in Div2C pretest2
 » 3 months ago, # |   0 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)
 » 3 months ago, # |   -24 problem C is very tough.. this contest is not meant for div 2!! I downvote!
•  » » 3 months ago, # ^ |   +12 its not tough its tof !
 » 3 months ago, # |   -6 Div2/D If our graph will have consisted from one cycle and characters on the edges will be the same, will they play infinitely?
•  » » 3 months ago, # ^ |   +34 its DAG :/
•  » » 3 months ago, # ^ |   +19 DAG (Directed acyclic graph)
 » 3 months ago, # |   +45 My rating is about to go Upside Down...
 » 3 months ago, # |   +40 Am I the only one who thinks Div2D/Div1B was a little bit easier than Div2C/Div1A?
•  » » 3 months ago, # ^ |   0 no
•  » » 3 months ago, # ^ |   +5 i thought C was easier.. maybe im not good at graph problems :)
•  » » 3 months ago, # ^ |   0 maybe
•  » » 3 months ago, # ^ |   +63 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
•  » » 3 months ago, # ^ |   0 yes , but both traditional
 » 3 months ago, # | ← Rev. 2 →   +10 Seems like in both divisions D is easier than C (considering the number of successful submissions).
•  » » 3 months ago, # ^ |   0 Because it is a classic game theory problem.
 » 3 months ago, # |   +16 anyone can explain D.. I spent 1 hrs, but i can't find the answer
•  » » 3 months ago, # ^ |   +1 Use Dynamic Programming
•  » » » 3 months ago, # ^ |   +38 Wow, that will help.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +6 dp[100][100][26][2] The 2 is for turn Emulate the whole situations. O(N^3C) time complexity where N is # of vtx, C is # of alphabets
•  » » » 3 months ago, # ^ |   +31 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.
•  » » » » 3 months ago, # ^ |   +13 Good advice. Always dp[][][][0] = !dp[][][][1]
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 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][0].I'm still waiting for system test, hopefully I'll pass :PUPD:It passed now XD
•  » » 3 months ago, # ^ |   0 now i understand it. thanks for all help!
 » 3 months ago, # |   +1 Very nice contest and nice pretests :D
 » 3 months ago, # |   +12 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?
•  » » 3 months ago, # ^ |   +4 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..
•  » » » 3 months ago, # ^ |   +2 Hmm, but what about cases when the order of the characters matters?Like, "(?" is a pretty string, while "?(" is not (however following characters may make it pretty, i.e. "?()?").
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   +3 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!
•  » » » » » 3 months ago, # ^ |   +2 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! ;)
•  » » 3 months ago, # ^ |   +3 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.
•  » » » 3 months ago, # ^ |   0 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! ;)
 » 3 months ago, # |   +3 Div2C, I stuck in pretest 3/7 :(
 » 3 months ago, # |   +45 Isn't Div. 1 D a special case of this?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +25 Also, it has appeared on topcoder: https://community.topcoder.com/stat?c=problem_statement&pm=13369
•  » » » 3 months ago, # ^ |   +20 Are you sure this is correct link :P?
•  » » » » 3 months ago, # ^ |   +10 Oops I accidentally deleted a character :P
•  » » » 3 months ago, # ^ |   +77 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.
•  » » » » 3 months ago, # ^ |   +65 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.
 » 3 months ago, # |   0 Any idea what could be the test case 4 for div2 C ? I was stuck on this throughout the contest :'(
•  » » 3 months ago, # ^ |   +1 No idea, but I have a hack for your code: ())?
•  » » » 3 months ago, # ^ |   0 Thanks man.My algo was wrong then :'(
 » 3 months ago, # |   0 I am in Love with Problem D, thanks for the amazing problem :D
 » 3 months ago, # | ← Rev. 2 →   0 can't understand the problems.... want more explanation of the sample case...
 » 3 months ago, # | ← Rev. 4 →   +81 I think that is why so many participants passed div1.D...:)div1 D
•  » » 3 months ago, # ^ |   +15 Another similar problem is from XV Open Cup (2014-2015) GP of China.CF discussion: http://codeforces.com/blog/entry/16701
 » 3 months ago, # |   0 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)...
•  » » 3 months ago, # ^ |   0 yes
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 If you are still interested:my 36441589 solution is O(len2).First, let's do it without '?':for each fixed l, iterate by r, maintain "unclosed parens" counter (u).Interpret '(' as +1 to u,')' as -1 from it.When u reaches zero, +1 to the result.When u is negative, stop iterating by r.To deal with '?', it's enough to maintain two counters (umin, umax).Interpret '?' as +1 to umax and -1 from umin. Upd: I found that iriszero already described a similar solution in a comment below.
 » 3 months ago, # |   0 any idea for Div2C? It seems very tough for me :(
•  » » 3 months ago, # ^ | ← Rev. 2 →   +16 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)
•  » » » 3 months ago, # ^ | ← Rev. 3 →   +8 Clearly speaking,case '(': upper++,lower++ // case ')': upper--,lower-- // case '?': upper++,lower--
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 What is the use of lower? Should it be 0 at the valid end positions?Does this work for: ????))))(((()
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 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 upper will be 2. which >= 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?
• »
»
»
»
»
»
»
3 months ago, # ^ |
Rev. 2   0

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,

? ? ) ) ( ( ( ( )
lower 0 0 0 0 1 2 3 4 3
upper 1 2 1 0 1 2 3 4 3
solution y y n n

(we can only expect pretty one with even length)

•  » » » » » » » » 3 months ago, # ^ |   +1 The key idea is that if lower ≤ 0 ≤ upper, we can always expect that there exists some solution. 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
•  » » » » » » » » » 3 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » » » 4 weeks ago, # ^ |   0 The upper/lower bounds are for counting the number of unclosed parentheses(in other words, the number of '(' for which we have not encountered corresponding ')' yet).I also described the idea in my comment above.
•  » » » » 3 months ago, # ^ |   0 nice solution after reading your code:)
•  » » » » » 3 months ago, # ^ |   0 Thanks. :)
 » 3 months ago, # |   +30 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 ;_;
•  » » 3 months ago, # ^ |   +5 +1 (spent 1.5 hours on ), thought I found a small mistake which I couldn't fix.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Same story.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.
 » 3 months ago, # |   -44 The contest should be unrated because you did not announce the scoring.Trying to save my rating.
•  » » 3 months ago, # ^ |   +71 You're a pupil, what rating are you trying to save? :p
•  » » » 3 months ago, # ^ | ← Rev. 2 →   -6 You was a pupil too :P
 » 3 months ago, # |   +141 Problem A Div2 was inspired by OO0OOO00O0OOO0O00OOO0OO
•  » » 3 months ago, # ^ |   +33 Yup!
•  » » 3 months ago, # ^ |   +36 I wonder how long he takes to login :P
 » 3 months ago, # |   -13 how to solve D?
•  » » 3 months ago, # ^ |   0 You can use topsort. Than start back from the nodes and calculate next dp values : dp[currentplayer][previouscharacter][firstnode][secondnode].
•  » » » 3 months ago, # ^ |   -14 I meant div1 D
•  » » » » 3 months ago, # ^ |   +11 For that you have links above :P
•  » » 3 months ago, # ^ | ← Rev. 3 →   +41 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)
•  » » » 3 months ago, # ^ |   +10 Your solution sounds much more fit to Div 1's.=D
•  » » » 3 months ago, # ^ |   +20 Why is given graph a tree then?
•  » » » » 3 months ago, # ^ |   +60 In order to allow other solutions, quite clearly :). Mine heavily uses fact that it is a tree.
•  » » » » 3 months ago, # ^ |   +25 Because that is not the only solution. Mine works only on trees and likely, so does the official one
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +10 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.
•  » » » » » 3 months ago, # ^ |   +10 If you are allowed, please share the novel O(n^2) solution.
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » » » » » 3 months ago, # ^ |   +10 Look forward to the editorial for a detailed solution. Thanks, @Reyna.
•  » » » » » » » 3 months ago, # ^ |   +5 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.
•  » » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   +10 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
•  » » » » » » » » » 3 months ago, # ^ |   +10 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.
•  » » » » » » » » » 3 months ago, # ^ |   0 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.
•  » » » » » » » » » 3 months ago, # ^ |   0 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?
•  » » » » » » » » » 3 months ago, # ^ |   +10 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.
•  » » » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   +10 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.
•  » » » » » » » » » 12 days ago, # ^ |   0 Finnally, got accepted with O(n2) solution.
•  » » » » » » » » » 11 days ago, # ^ |   0 Wow! Orz! It's actually pretty hard imo XD
 » 3 months ago, # |   0 Auto comment: topic has been updated by DarthPrince (previous revision, new revision, compare).
 » 3 months ago, # |   -38
•  » » 3 months ago, # ^ |   -7 Thats not true buddy!! Div2A/B was easy! Yes, C was tougher then regular!
 » 3 months ago, # |   +41 A royal contest, Prince + Queen (Reyna in spanish)
 » 3 months ago, # |   0 The problems C+ where really hard.. Cool actually
•  » » 3 months ago, # ^ |   0 "where"? o.o
 » 3 months ago, # | ← Rev. 2 →   +13 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.
•  » » 3 months ago, # ^ |   +5 Did you use an online IDE or accidentally leaked your password? This happens from time to time and is really strange.
•  » » » 3 months ago, # ^ |   0 I think someone had access to my account by my mistake.
•  » » 3 months ago, # ^ |   0 wich code ?!
•  » » 3 months ago, # ^ | ← Rev. 2 →   +20 The best choice is updating your password immediately, this happened to me last year.
•  » » » 3 months ago, # ^ |   0 I updated it after the contest. Thanks for your comment.
•  » » » 3 months ago, # ^ |   0 Wow, going to such lengths for solutions..
 » 3 months ago, # |   +1 Memoization is clean for Div1 B: http://codeforces.com/contest/917/submission/34673801
•  » » 3 months ago, # ^ |   0 It's actually strikingly amazing how similar my solution is to yours :D
•  » » 3 months ago, # ^ |   0 good understandable code.
•  » » 3 months ago, # ^ |   +5 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.
 » 3 months ago, # | ← Rev. 3 →   +10 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 BUPD2: they were rejudged , thanks MikeMirzayanov.
•  » » 3 months ago, # ^ |   +4 Same happened for my Solutions for div2 A and div2 B.
•  » » 3 months ago, # ^ |   +19 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?
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 If this is the case then the solution must fail even the pretests. My solution for Div2A passed the pretests and failed the main tests.EDIT : The solution has been rejudged.
•  » » » 3 months ago, # ^ |   +46 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.
 » 3 months ago, # |   0 Kareeeee
 » 3 months ago, # |   +19 And the scoring distribution is never announced...
•  » » 3 months ago, # ^ |   +5 Meanwhile the system testing seems to be neverending as well...... even when all submissions were judged.
•  » » » 3 months ago, # ^ |   +3 Div 1 not done judging
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   0 Hmm then this one is weird... "Final standings"?UPD: Got it now. Nevermind then.
 » 3 months ago, # |   +45 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.
•  » » 3 months ago, # ^ | ← Rev. 3 →   +10 C allows both standard matrix multiplication and dp (with some greedy speedup). UPDATE: Perhaps I am wrong...
•  » » » 3 months ago, # ^ |   0 Well, these matrices is also some kind of dp :). But you surely meant something entirely different, can you describe your approach?
•  » » » » 3 months ago, # ^ |   0 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.:(
•  » » » » » 3 months ago, # ^ |   0 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)
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 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...)
•  » » » » » » » 3 months ago, # ^ |   +10 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.
•  » » 3 months ago, # ^ |   0 Maybe there's a similar problem...(link)
 » 3 months ago, # | ← Rev. 2 →   0 Thanks to all organizers of this round, I realy enjoy it, let's hope all rounds would be like this one and even much better.
 » 3 months ago, # |   +11 my first ever B 'accepted', thought that I improving my skills but... the fact is, it was easy......... :-(
 » 3 months ago, # |   +6 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!
•  » » 3 months ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » 3 months ago, # ^ |   +8 No, I hacked somebody,+100 points have a big impact in the results. Because almost all participants have a near results to each other.
•  » » » » 3 months ago, # ^ |   +5 Haha, then good for you. Congrats! :D
 » 3 months ago, # |   -11 What is the complexity of the DP solution of D?Is it O(m*n*26)?
•  » » 3 months ago, # ^ |   0
•  » » » 3 months ago, # ^ |   0 Can you explain the complexity of your solution?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +5 O(n^2*50+m)
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 O(n * n * 50 + n * m)
•  » » 3 months ago, # ^ |   0 O(n*n*26*2 + m) i guess
•  » » » 3 months ago, # ^ |   +1 But every edge can be traversed n times(every node that the other participant is in)
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 yes! i didn't notice it.. m will be multiplied with n..
•  » » 3 months ago, # ^ |   +3 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).
 » 3 months ago, # |   +52
•  » » 3 months ago, # ^ |   0 A was very much hackable with overflows but its difficult to come up with such cases.
 » 3 months ago, # |   +5 waiting for ratings...
 » 3 months ago, # |   0 Auto comment: topic has been updated by DarthPrince (previous revision, new revision, compare).
 » 3 months ago, # |   +10 OO0OOO00O0OOO0O00OOO0OO's nick... Algorithm from Problem A, isn't it? ^o^
 » 3 months ago, # | ← Rev. 2 →   -39 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
•  » » 3 months ago, # ^ |   0
•  » » » 3 months ago, # ^ | ← Rev. 2 →   -21 I think my id was hacked. . fuck
•  » » » » 3 months ago, # ^ |   +5 they submitted before you
•  » » » » » 3 months ago, # ^ |   -22 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.
•  » » » » » 3 months ago, # ^ |   0 plz help me. :( plz.
•  » » » 3 months ago, # ^ |   -34 plz see the submission time and and ban those id. plz.those id isn't mine
•  » » » » 3 months ago, # ^ |   -44 MikeMirzayanov plz resolve this. I am afraid for this. ban those ids. those ids isn't mine.
•  » » » » » 3 months ago, # ^ |   -27 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.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +6 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 123456 password.
 » 3 months ago, # |   0 Auto comment: topic has been updated by DarthPrince (previous revision, new revision, compare).
 » 3 months ago, # |   0 How can I solve DIV2 C with DP?
 » 3 months ago, # |   0 why this solution get a much greater answer for 917A? I've really no idea bool match(int a, int b) { if(S[a] == '(') { if(S[b] != '(') return true; } else if(S[a] == '?') { if(S[b] != '(') return true; } return false; } for(int i=1; i
 » 3 months ago, # |   0 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? :/http://codeforces.com/contest/918/submission/34678446
•  » » 3 months ago, # ^ |   0 It works if you read n, m using cin>> n >> m;
•  » » 3 months ago, # ^ |   +5 You say ios_base::sync_with_stdio(false);`, but then you mix printf/scanf and cin/cout. can't do that.
 » 3 months ago, # | ← Rev. 8 →   +5 I am sorry to say that but unfortunately data set of problem B maybe weak 918B - Радиостанция For example this case: 2 2 main 192.168.0.12 replica 192.168.0.1 block 192.168.0.1; proxy 192.168.0.12; check this my wrong solution : 34674890 which was accepted I am sorry for informing this lately..
•  » » 3 months ago, # ^ |   0 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.
•  » » » 3 months ago, # ^ |   +1 Updated my statement, thank you .
 » 3 months ago, # |   +1 What's the point in making such huge problem statements ?
 » 3 months ago, # | ← Rev. 2 →   0 https://ideone.com/Gb6GiQ Very good solution for 3-rd task, if anyone needs.
 » 3 months ago, # |   0 Very good round, i really enjoyed it.
 » 3 months ago, # |   0 Div.2 A using regular expression: 34722038 (and B — 34722359)