### platypus179's blog

By platypus179, history, 4 years ago, translation,

Codeforces Round #395 for both divisions will happen tomorrow, on Thursday, 2 February 2017 at 13:35 UTC.

Problems were prepared by me (Vasiliy Alferov) and students of Moscow school #179: s17b2_voroneckij (Dima Voronetsky), ilya_the_lamer (Ilya Pauzner) and akvasha (Anton Kvasha). Also, KAN (Nikolay Kalinin) is author of one of the problems.

Invaluable help was given to us by Codeforces coordinator KAN (Nikolay Kalinin). Thanks to MikeMirzayanov (Mike Mirzayanov) for wonderful platforms Codeforces and Polygon. Also thanks to Endagorion (Mikhail Tikhomirov), winger (Vladislav Isenbaev), AlexFetisov (Alex Fetisov) and cdkrot (Dmitry Sayutin) for reading out our statements and testing the round.

Participants will be given five problems in both divisions. Some of the problems will be common for both divisions. The scoring distribution will be announced later.

Good luck to all!

UPD: Scoring distribution:

Div1: 500-750-1500-2000-2500

Div2: 500-1000-1500-1750-2500

UPD2: The contest is over. Hope you enjoyed the problems :)

UPD3: Congratulations to the winners!

Div 1:

and Div 2:

The editorial will be posted very soon.

UPD5: Editorial

• +259

 » 4 years ago, # |   0 Auto comment: topic has been updated by platypus179 (previous revision, new revision, compare).
 » 4 years ago, # |   +62 I am new to programming and I have visited number of coding sites and I found Codeforces one of the best coding sites on the Internet. Coding rounds like this are so amazing. I really enjoy coding on Codeforces. Thanks a lot for making coding site like this.
•  » » 4 years ago, # ^ |   -53 i just signup to this site..i will see how much fun it wil give to me..i hope HACKEREARTH and HACKERRANK are best site that i came across..just go through once i hope i will never come back to this site..
•  » » » 4 years ago, # ^ |   0 Bro..At least write correct English...you are tough to get..
•  » » » 4 years ago, # ^ |   0 Those sites are also good, I am just saying that I liked this site a lot. Its my own opinion and opinions can differ from person to person. Hope you will understand.
 » 4 years ago, # |   +46 I hope it won't end up unrated like yesterday :\
 » 4 years ago, # |   -59 Time collides with Hackerrank's HourRank. I'm a pupil. I'll probably end up participating in both contests.
•  » » 4 years ago, # ^ |   +70 what does being a pupil have to do with anything?
•  » » » 4 years ago, # ^ |   -18 We dont solve lots of problems. Lots of free time. :D
•  » » » » 4 years ago, # ^ |   +126 If you think that way, you are going to stay at pupil for a long time. Seriously, just keep trying until the contest ends.
•  » » » » » 4 years ago, # ^ |   -20 Ofcourse I don't think that way. It was just a joke. Clearly, a bad one.
•  » » » » » » 4 years ago, # ^ |   +14 I found it funny.Society is just cruel.
•  » » » » » » » 4 years ago, # ^ |   +10 May God give you red rating.
•  » » » » » » » » 4 years ago, # ^ |   0 kyon Rana ji itna pareshan kyon hai kyon in becharo pe apna frustration nikal rhe hain
•  » » » » » » » » 4 years ago, # ^ |   0 Easy. Wait until 2018.
•  » » 4 years ago, # ^ |   +80 HourRank is at 16:00 UTC. The contests don't collide.
•  » » » 4 years ago, # ^ |   +13 Sorry about that. My bad.
 » 4 years ago, # |   +19 Hope the Codeforces polygon won't be unstable this time, or this round will remain unrated too... :( Anyway, I'll try my best to work on the problems no matter whether it's rated or not. :)
•  » » 4 years ago, # ^ |   +9 what's the need of writing it here?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Because it happened in the last round two days ago. Although I didn't take part in it, I think it would be very disappointing if this happened. So just pray for it...
•  » » » » 4 years ago, # ^ |   0 I just enjoy solving problems :)
 » 4 years ago, # |   -7 the round rated?
•  » » 4 years ago, # ^ |   +26 I hope so... It doesn't say it's unrated. Anyway, just try your best.
•  » » » 4 years ago, # ^ |   -14 It is rated.
 » 4 years ago, # | ← Rev. 2 →   +12 A week without any rated contest, hope this contest doesn't have any bugs like the previous one:)
 » 4 years ago, # |   -11 blue coders prepare a contest for Red coders. Amazing :)
•  » » 4 years ago, # ^ |   +28 It should not be underestimated because of the color. Let us estimate after the contest.
•  » » 4 years ago, # ^ |   +23 As you can see, a purple color and a red also worked on the problems.
•  » » 4 years ago, # ^ |   +50 Not being an excellent coder does not mean not being an excellent problem setter :)
•  » » » 4 years ago, # ^ |   +149 Yes, but as a former TopCoder admin and current AtCoder admin, I'm sure there's strong correlation between the originality of problems and the writer's rating. That's why we set a rating cutoff for being a writer.
•  » » 4 years ago, # ^ |   +56 I was orange two months ago :(
•  » » » 4 years ago, # ^ |   +94 I was red month ago..
•  » » » » 4 years ago, # ^ |   -13
•  » » » » » 4 years ago, # ^ |   +21 There were many reds a month ago due to the magic feature. I believe that he didn't lie lol.
•  » » » » » » 4 years ago, # ^ |   0 Magic is a lie too :D
 » 4 years ago, # |   +12 Hope codeforces is stable today and we get a rated contest! :)
 » 4 years ago, # |   -12 Hopefully we get something other than math and greedy for Div2 ABC :)
•  » » 4 years ago, # ^ |   +124 What do you expect? Persistent segment trees? :)
•  » » » 4 years ago, # ^ |   0 easy dp , graphs ?
•  » » » » 4 years ago, # ^ |   +47 Graphs are too complicated for beginners who have just started competitive programming. Some of them don't even know what a graph is. So I believe graph problems are not suitable for div2 AB.:)Easy DP would be a good idea for div2 C. But similar to graph problems, I don't think it's a good idea for Div2 AB.
•  » » » » » 4 years ago, # ^ |   +27 Yeah, in my opinion, problem Div2 A and B will be the situations that we'll meet in our life, such as buying watermelons(just kidding :P). They won't require a very high skill. You can just do it in the way you think. So I don't think they require learning deeply into mathematics or greedy. Just very simple thoughts. The problem for beginners is that they can't code it or consider every situation, instead of they can't get the way of doing them.
 » 4 years ago, # |   -14 The answer is Yes, right?
 » 4 years ago, # |   -35 I hope to see some physics problems this round :)
•  » » 4 years ago, # ^ |   +35 Hope it won't be so..
•  » » » 4 years ago, # ^ |   0 A change of scenery would be nice... a bit tired of all the math problems haha
•  » » » 4 years ago, # ^ |   +5 I think this idea is interesting. But for the ones who haven't learnt deep into physics, it's a little bit unfair, because they have to spend a lot of time understanding the problem statement. Also they won't think of some situations that is different from others but not mentioned in the problem statement. So personally, I won't choose a physics problem. But I don't have the chance to decide or know. :D
 » 4 years ago, # |   +45 I hope this time we don't have any problem with the server. I got trauma from this image in the previous contest.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 it is already showing very busy, i wonder if it will happen today again
 » 4 years ago, # |   +3 Finally Div1 & div2 separated
 » 4 years ago, # |   +6 CodeForces is toooooooo slow from here Hope not a server error
 » 4 years ago, # |   +30 A good time for Chinese students!Hope it will be a good warm-up round for the Chinese Winter Camp next day.
 » 4 years ago, # |   +3 Hope that this time contest doesn't go unrated.
 » 4 years ago, # |   +5 I hope that this contest will be interesting :)
 » 4 years ago, # |   +5 I hope all is well this time! :D
 » 4 years ago, # |   -20 PC hanged while reading problem A. Forced shutdown and restart. More than 3400 submissions on A and 1800 submissions on B. out of competition :(
 » 4 years ago, # |   +10 What does "more" in div1D mean? more pairs or more vertices?
 » 4 years ago, # |   0 Please add the explainations to div 2 problem c sample inputs and also adding explainations to the problem like A and not to a problem like C is not fair at all :(, seems like it is done deliberately.
 » 4 years ago, # |   0 In the input of Problem C from div2, u < v , or it doesn't matter?
•  » » 4 years ago, # ^ |   +1 The questions are to be asked in the contest.
•  » » » 4 years ago, # ^ |   0 how?
•  » » » » 4 years ago, # ^ |   +1 There is a special button on page "Problems"
•  » » » » » 4 years ago, # ^ |   0 thank you!
•  » » » » » » 4 years ago, # ^ |   0 Why I can not solve more than 3 problems A B C ????? ^)
 » 4 years ago, # |   +15 Very Nice Problems! :D I made a history for myself, this is the my First Time to solve graph related problem! Trees are so much fun! Hooray Rating!
 » 4 years ago, # |   -78 problems like shit .
•  » » 4 years ago, # ^ | ← Rev. 5 →   +32 Never say something like this. It's your fault that you can't solve the problems. The problem settler may should have designed some easier problems, but it's their chance to do that. Also taking part in contest will be more valuable if you can discover what you are poor at. You should improve your own skills, instead of saying rude languages towards the problems.
•  » » » 4 years ago, # ^ |   -93 fu** off
•  » » » » 4 years ago, # ^ |   -17 Sorry, but deep_learning is right. Argument this or go away.
•  » » » » » 4 years ago, # ^ |   -73 also fu** off
•  » » » » » » 4 years ago, # ^ |   -13 You are too rude Please, stop it.
•  » » » » » » » 4 years ago, # ^ |   +12 Maybe (s)he's on a period
•  » » 4 years ago, # ^ |   -10 Problems were easy compared to regular contests
 » 4 years ago, # |   +38 The gap between div2C and div2D problems is far bigger than 250 points imo.
•  » » 4 years ago, # ^ |   0 I'm not so sure. Maybe because I'm not used to DP on trees, but have a lot of experience in combinatorics style problems, I found D to be far easier than C. At the very least, it was easier to code.
•  » » » 4 years ago, # ^ |   0 Now when I saw solutions to D I'm not so sure either :D
•  » » » 4 years ago, # ^ |   0 I couldn't submit on time , but i am not sure if we even need dp on trees . Could be done without that.
•  » » » 4 years ago, # ^ |   0 Easier to code? Could you, please, share your solution? I've struggled a lot with implementation.
•  » » » » 4 years ago, # ^ |   +1
•  » » » 4 years ago, # ^ |   0 DP on trees? If you are reffering to div1A, it was just a matter of finding all edges that connect vertices of different color, and seeing if all those edges share a same vertex.
 » 4 years ago, # |   +1 Problem set of this contest was nice. Although Problem D deserved 2000 points imo, if not 2250, since the difficulty gap between C and D was too high.
 » 4 years ago, # | ← Rev. 2 →   +117
 » 4 years ago, # |   +47 Is this an IQ contest or something ??????????????
•  » » 4 years ago, # ^ |   +14 If it is, I am very stupid :D Very nice problem D, I really like it.
•  » » » 4 years ago, # ^ |   +5 How did you solve it?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +33 Just consider the top-right corner of each rectangle and color it based on (xmod2, ymod2).I somehow thought this doesn't work in the contest and got stuck for 40+ minutes. Then I realized it actually works -_- RIP rating.
•  » » » » » 4 years ago, # ^ |   0 Can you prove its correctness?
•  » » » » » » 4 years ago, # ^ |   +3 It's quite easy to prove. Just prove that the top right corner of two touching rectangles cannot have both coordinates with equal parity (with the condition that all rectangles are non-intersecting and have odd side lengths)
•  » » » » 4 years ago, # ^ |   -17 answer is always YES . let a = x1&1 , b = y1&1 , colour the rectangle with colour = a*2+b+1 .I liked this problem the most .
•  » » » » 4 years ago, # ^ |   +8 Notice that two adjecant recetangles must have left (right) — bottom corner with different x % 2 coordinate or y % 2 coordinate.So for each combination (0,0), (0,1), (1,0), (1,1) assign different color.
•  » » » » » 4 years ago, # ^ |   +21 OMG, this is so simple and easy. And there am I, generating an adjacency list and trying to solve the graph problem.
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I was doing the same thing at first, and than I saw that guys solved in three minutes and I said forgot this, try again :)I believe we can run normal dfs for case with any length of sides and put the smallest different color than all adjecant colors and run dfs from next node again. Somehow I think it will produce correct answer.But you need big code for caluclating adjecants recetangles. Can someone prove than we won't have more than 4n pairs of adjecant recetangles ?
•  » » 4 years ago, # ^ |   -7 no, usual one don't be rude. dude
 » 4 years ago, # |   0 How to approach problems like Div2C which require dfs to calculate answer?
•  » » 4 years ago, # ^ |   +34 Consider writing dfs.
•  » » » 4 years ago, # ^ |   0 er...i am poor at the problem at div2c , and now after i read the editorial,i dont know how to implement it by myself,i think i should practice some similar to this problem or maybe easy than this problem, can anybody suggest me some similar problem ? thanks in advance , and sorry for my bad english ^_^
•  » » » » 4 years ago, # ^ |   0 But what is diffuclt in this problem? The dfs there is rather simple.
•  » » 4 years ago, # ^ |   +5 Find two adjacent nodes where their colours are different, if the answer is YES, then one of those two points would be the root.Do a dfs at both the points to check if their subtrees have nodes of the same colour. If it is not possible for both of them, then it is NO. It is YES otherwise,and you know the answer.
•  » » » 4 years ago, # ^ |   0 but it looks brute force i thought that did not implemented that, then i thought some more complex solution dsu + segment tree but got memory limit exceeded :( . I think sinus_070 your solution complexity is O(n2) , either the testcases are not more strong enough or i am missing some thing . Anyways it is always fun to think and solve problems , it always gives satisfaction .
•  » » » » 4 years ago, # ^ |   0 I'm doing 2 dfs' only. And finding the pair is O(n)
•  » » 4 years ago, # ^ |   +4 Nice and easy problem I had wrong answer on testcase 10,hadn't time to solve some special, but this algorithm almost surely is correct.You have to find 2 vertices that are connected and different color, one of them must be root.So if you you have more then 1 such pairs and they don't share one vertices you're done,otherwise that vertices is root,proof is simple.
 » 4 years ago, # |   +28 How to solve Div1 C??
•  » » 4 years ago, # ^ |   +15 How to solve Div1 C without random !
 » 4 years ago, # |   +126 Div 1C is the same as this problem http://codeforces.com/gym/100451/problem/I.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +14 Shit.In fact, it isn't exactly this problem, in our Div1C the modulo was prime and the model solution uses this fact. Anyway, I didn't see this problem before. Neither, probably, did KAN.
•  » » 4 years ago, # ^ |   0 how to solve it ? I could only think of O(N^2)
•  » » 4 years ago, # ^ |   0 By the way, is there any published editorial for Petrozavodsk training camp contests? The official one seems to require credentials to log in.
 » 4 years ago, # | ← Rev. 4 →   +9 On problem D, my output for the first test is: YES 3 2 2 1 2 1 2 1 Why does it give WA?Here are the rectangles, black numbers are indexes, brown numbers are color. No same color touches:
•  » » 4 years ago, # ^ |   +8 In system your output is "NO".
•  » » » 4 years ago, # ^ |   0 So weird. I tried custom invocation, it outputs NO. On my compiler it outputs the right answer. I'm sure the files are the same, I tried uploading the file twice, it told me I've submited it before. My code is here. Might be a C++11/C++14 problem.
•  » » » » 4 years ago, # ^ |   +3 The problem is in line 67:bool can[5];It looks like you are expecting the initial values to be 0. But you are dynamically allocating the array, so it will be uninitialized.
•  » » » » » 4 years ago, # ^ |   0 Oh yeah, thanks a lot.
 » 4 years ago, # |   +2 No Hacks This Time :) !!
•  » » 4 years ago, # ^ |   -12 I made 3 :P
•  » » 4 years ago, # ^ |   0 some didn't handle the case of only two different number in B 2 1 5 
•  » » 4 years ago, # ^ |   0 I made 2. I think C had weak pretests.
 » 4 years ago, # |   +14 How to solve Div1 B??
•  » » 4 years ago, # ^ | ← Rev. 3 →   +49 Since edge lengths are odd, just assign colours on basis of the pair (a%2, b%2), where top-left corner is (a,b). You are guaranteed that same color rectangles will never touch each other.
•  » » 4 years ago, # ^ |   -7 colour of a rectangle is 2*(x1&1) + (y1&1) + 1
 » 4 years ago, # |   +1 How to solve div2C ?
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 I solved it using greedy technique.The solution is that we define f(u) for vertex u as the number of adjacent vertices to u like v such cu != cv. then choose the vertex with greatest f(u) and check if erasing it from tree annoys him or not! if not, the answer is "NO". otherwise, print this vertex.I hope it would pass sys tests. ;)
•  » » 4 years ago, # ^ |   0 Assume vertex #1 is the root. For each child C of the root check whether all elements in subtree with root C are the same color as C. If you found vertex of different color — make it a root of your tree and do this checking one more time but now print NO if found different color.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +9 My approach- Consider all such edges that connect two vertices of different color. Let's call them heterogeneous edges. There will be an answer iff there is one vertex common in all the heterogeneous edges. And that common vertex will be the root. You don't even need to build a graph. It's elegant...well, only if it's correct. :D Edit: It is correct. :)
 » 4 years ago, # |   +18 I think it was better that task D worth 2250 points, it seems really tough for lots of competitors
 » 4 years ago, # |   +17 Div2 A .. very bad statement
•  » » 4 years ago, # ^ |   0 Why?
•  » » » 4 years ago, # ^ |   +1 I tried to conceive the whole situation for a few minutes, but failed to understand what's going on there. Then I went straight to the examples and was able to abstract away from these climbers, artists random phone calls and odd killings for no reason.
•  » » 4 years ago, # ^ |   +3 The only thing I could say it was bad is because you don't know if he would kill everyone that has visited, or only people that visit that minute. However, test case 3 answers that question. I thought it was good, but I was second guessing myself.
•  » » » 4 years ago, # ^ |   0 exactly :D
•  » » » » 4 years ago, # ^ |   0 Again, it is stated that you should minimize killed artists.
•  » » » 4 years ago, # ^ |   0 The statement says "Print single integer — the minimum number of artists that should be killed so that there are no artists in the room when Ilia calls."
•  » » » » 4 years ago, # ^ |   0 I missed that somehow. However, the test cases gave the example. So there was multiple ways to get the information. Awesome Sause. Have a great day!
•  » » » 4 years ago, # ^ |   0 I didn't read statements, just looked samples, then got the idea :D
•  » » 4 years ago, # ^ |   +1 Strongly agree!
 » 4 years ago, # |   +2 Does anyone knows the test case of pretest 7 of problem C in the div 2 contest. It's like a freaking walls.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 5 — 1 2 — 1 3 — 1 4 — 1 5 --- Mb
•  » » 4 years ago, # ^ |   0 If you have figured out what's special about pretest 7 let me know. Thanks
 » 4 years ago, # |   +10 For description of DIV1 E. I think you should let (1<=l<=r<=100000) be (1<=l<=r<=n)
•  » » 4 years ago, # ^ |   +41 And it's same as hdu 5333 :P
•  » » » 4 years ago, # ^ |   +10 I think some coders will get runtime error if r>n
•  » » » 4 years ago, # ^ |   0 Yeah, seems like easier version of this: http://acm.hdu.edu.cn/showproblem.php?pid=5333Extra constraint on edges allows simpler but uglier solutions.
 » 4 years ago, # |   0 Thank you for the nice problemset! I really enjoyed this contest!
 » 4 years ago, # |   0 How to solve D...I thought about turning it into a graph and then DP it but I thought it would be too messy and I didn't know how to handle cycles could anybody who has solved it explain his/her solution ?My DP was going to be DP(node, which color this node is)
•  » » 4 years ago, # ^ | ← Rev. 3 →   +10 If you mean Div.2 D, there is a simple trick. Let's say that the top left corner of rectangle 1 is (X1,Y1) and rectangle 2 is (X2,Y2). As the rectangles have odd length, they can only be in contact if either X1-X2=1 (mod 2) or Y1-Y2=1 (mod 2) or both. In other words, two rectangles can not be in contact if the modular 2 of the top left corner is the same. There are four possible ways for (X,Y); (0,0), (0,1), (1,0), (1,1). Assign a color for each.
•  » » » 4 years ago, # ^ |   0 Hmmm...interesting observation...I wish I could notice that at the right time...Thank you.
 » 4 years ago, # |   0 How to solve Div2 D? I assume it is graph constructing and coloring problem. Can you give some hints if it's so? Otherwise please tell me that it's wrong approach.
•  » » 4 years ago, # ^ |   +8 No. Just output answer based on whether x and y are odd or even. Because the side length is always odd.
 » 4 years ago, # |   0 I solved Div. 2 C with DSU. I don't know if it's wrong, since many people solved with normal DFS. How would you do normal DFS though?
•  » » 4 years ago, # ^ |   0 I was too trying with DSU but didn't managed to get AC.-_-
•  » » 4 years ago, # ^ |   0 first dfs from any leaf till you encounter a node with different color(named save and its parent in dfs be save2). Now (if the # of nodes with distinct colors attached with this node save2 > 2) then mark save as the desired node and run dfs for all vertices attached with save and check if they are of same color to their respective parents. else mark save2 as the desired node and run dfs for all vertices attached with save and check if they are of same color to their respective parents. if its possible then output mark else "no"
•  » » 4 years ago, # ^ |   +6 well, I solved(passed pretest) with dsu. Just merge the neighbor together if their color is the same, then iterate over the vertex. See if the size of all distinct dsu from its neighbor and himself is equals n. If so then you can choose it.
•  » » » 4 years ago, # ^ |   0 Now I got it , did exactly same as you did but i checked degree not number of vertex may be thats why i was getting WAs. thanks :)
•  » » 4 years ago, # ^ |   +7 I solved without using dfs/bfs/dsu. Just checked edges between two different colored vertices.
•  » » 4 years ago, # ^ |   0 even i tried with DSU and segment tree got memory limit exceeded :( .
 » 4 years ago, # |   0 Very nice div2 D! That was wonderful
 » 4 years ago, # |   +10 Nice hack case to C: n=m-3 and sequence lacks 3 elements that don't form arithmetic sequence.
•  » » 4 years ago, # ^ |   +4 How did you solve Div1C ?
 » 4 years ago, # |   0 Auto comment: topic has been updated by platypus179 (previous revision, new revision, compare).
 » 4 years ago, # |   0 Div2D was awesome . How to solve it if the dimensions of the rectangles can be even too ?
•  » » 4 years ago, # ^ |   0 By the four-colour theorem, the answer definitely exists.Not really sure how to construct the solution though.
•  » » » 4 years ago, # ^ |   0
•  » » » » 4 years ago, # ^ |   +5 So this paper says there is quadratic algorithm, however I believe it can be done in O(nlog(n)) too.
•  » » » » » 4 years ago, # ^ |   0 Why?
•  » » » 4 years ago, # ^ |   0 Well, I'm not sure but can't we also prove that the planar graph will be 3-colorable as well? It seems to satisfy all the conditions necessary.
•  » » » » 4 years ago, # ^ |   0 There can be 5-cycles, actually.
 » 4 years ago, # |   +18 What was the expected (or popular) solution to C? I noticed that, given and , we have a quadratic equation on d, though I somewhat expect to see many probabilistic solutions.
•  » » 4 years ago, # ^ |   +15 I tried all possible starts and found d from equation, then verified that sum of squares is same as well. Not sure that it will pass.
•  » » 4 years ago, # ^ |   +5 The difference between any two element is kd, and we can use the number of occurrence of kd to compute k since k1d = k2d implies k1 = k2.If we choose kd to be the smallest difference between any two elements, the number of kd can be counted in via sorting. Suppose we have c pairs of element having difference kd. Originally I take k = n - c, but this is correct only when 2n < m and I didn't notice it until the last 15 minutes. I "flip" the sequence to fix it but maybe it's not necessary. :P
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 I'm sure that the number of (x, d) satisfies two equations is O(1) (It can be three or more equations). So the complexity may be O(NlogN).
 » 4 years ago, # | ← Rev. 2 →   +35 Div1 A is so simple..Spent about an hour trying to write hard dfs-tree-based solution. Finally got simple idea, coded in 4 minutes:All the edges (u, v) such that color[u] != color[v] should have one common vertex. This vertex is the answer. Otherwise, there is no answer.
•  » » 4 years ago, # ^ |   +3 Yeah bro, but Div1 B is an even bigger fail for most people here. :)
•  » » 4 years ago, # ^ |   0 Yeah man did exectly same,but got WA on test 10 mabe I messed some special case...
 » 4 years ago, # | ← Rev. 2 →   +90 Me after reading Div1-B solutionBest Div1-B problem ever (even though I failed to solve it).
•  » » 4 years ago, # ^ |   +21 Wasted whole time thinking about point compression, graph building, coloring graph.. And messed up everything :| :|
•  » » » 4 years ago, # ^ |   +17
 » 4 years ago, # |   +16 Didn't notice, rather didn't pay much attention to the fact that lengths were odd inspite of it being in bold for Div 2D. Ended up thinking about general case and hence wasting the whole time :(
 » 4 years ago, # |   +1 I know there's an easy solution for D, but what if the sides can be even too? I think this will work, correct me if I am wrong: Create 2 arrays, one for vertical sides and one for horizontal sides, sort each of them by y/r, then by beginning and end of a side. Then we just use two pointers to find all intersections of rectangles and build a graph. Then just DFS in this graph. I tried to implement this but the round ended. Do you think it will fit into the time limit?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 This way the problem is NP-complete. Given that n ≤ 105, it cannot be solved in 2 seconds. Nevertheless, I did a blind try 24386589 =)
•  » » » 4 years ago, # ^ |   +3 What, the complexity will be O(nlogn).
•  » » » » 4 years ago, # ^ |   0 Then, probably, I don't understand. Could you, please, explain how would you use DFS to color the graph?
•  » » » » » 4 years ago, # ^ |   0 For some reason I believe you can do greedy approach while scanning through the rectangles from left to right. Does that seems plausibly true?
•  » » » » » » 4 years ago, # ^ |   0 Good idea, that may work.
•  » » » » » » 4 years ago, # ^ |   0 Yeah, that sounds good.
•  » » » » » 4 years ago, # ^ |   0 First we create the graph itself by creating arrays for vertical and horizontal sides, then sort them(nlogn) and then iterate through this array using two pointers(linear). The resulting graph has O(N) vertices. We just start a DFS from some vertice, DFS all its neighbours and their neighbors and try to colour the vertice in a colour that its neigbours don't share. I think this should work.
•  » » » » » 4 years ago, # ^ |   +1 Define F(a) as the number of neighbors of rectangle a.1) sort these rectangles by F(x);2) for each unfilled rectangle: fill an available min color, do 3);3) for each rectangle's neighbor: do 2).I am not sure if it's right...
•  » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 This might work. But why do you need 3 if you have already sorted them by the number of neighbours?
•  » » » » » » » 4 years ago, # ^ |   0 Sorry, my mistake. In fact, I tried BFS, just visit each neighbor by F(x)
•  » » 4 years ago, # ^ |   0 Thats what I did in contest. But for some reason I get WA on test 1 while it works on my compiler.
•  » » 4 years ago, # ^ |   +5 Not joined the contest, but isn't it related to parity of corners?
•  » » » 4 years ago, # ^ |   0 Read my first sentence.
 » 4 years ago, # |   0 This is my second time to participate in codeforces, and now or unrated, I hope this will be integral.
 » 4 years ago, # |   0 Nice problems. I really enjoyed. ty
 » 4 years ago, # |   +10 When will be rating updated ?
 » 4 years ago, # |   +39 After seeing this 24373708 solution for Div2D/Div1B —
•  » » 4 years ago, # ^ |   +3 Amazing solution. I start thinking that D was very easy problem after seeing this :)
•  » » 4 years ago, # ^ |   +8 That's nothing. 17059723 was once the correct answer to a Div2D.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 That was easily guessable :| But what happened in this round is speechless. Almost everybody didn't expect to have this kind of solution :( I have another one also — 23720774 Div2D :P
 » 4 years ago, # |   +25 It seems the standings page is a bit bugged.
•  » » 4 years ago, # ^ |   0 how?
 » 4 years ago, # |   0 Could someone please tell why 24374429 is giving TLE for problem B. Simple O(n) loop.
•  » » 4 years ago, # ^ |   0 because u used scanner , if u used the buffered reader it would have been accepted which is kinda bad
•  » » » 4 years ago, # ^ |   0 But generally for the java submissions, time limit is double than the normal time limit.
•  » » » » 4 years ago, # ^ |   0 well this is not the case here , i did the same mistake as u did so i know how frustrating this is check out my 2 submissions
•  » » » » » 4 years ago, # ^ |   0 Did your submission passed pretests during the contest. This is the case with me. My submission passed all pretests during the contest but later after the contest, on same pretests, it failed. :(
•  » » » » » » 4 years ago, # ^ |   0 yep same happened to me , but on top of that my C had a wrong answer on test 60 because i forgot a return statment xD i guess it wasnt my day
 » 4 years ago, # |   0 Due to slow response time of the website and slow rating changes, this contest will be unrated.Have a great day!
•  » » 4 years ago, # ^ | ← Rev. 2 →   +14 Do you think it's slow rating change?
•  » » » 4 years ago, # ^ |   +10 I think he's just making a joke of tuesday's contest.
 » 4 years ago, # |   +14 Problems like today's Div 1B make me feel handicapped :| Such an easy solution, yet I was nowhere near it during contest
•  » » 4 years ago, # ^ |   0 My head is hurting very much for not being able to solve. Uggh. I hope intuition comes by practice.
 » 4 years ago, # |   +1 it so unfair to solve a simple problem in o(n) to recieve a TLE because of input time , this is the first time this happens to me on codeforces , i dont wanna bring up the conflict of java vs c++ but this shouldnt happen :'( http://codeforces.com/contest/764/submission/24371107 http://codeforces.com/contest/764/submission/24388501
•  » » 4 years ago, # ^ |   +1 I am a java person too. For large inputs you need to use BufferedReader for input, and for large outputs you need to do PrintWriter.CodeForces has done this to me multiple times. It sucks I know.
•  » » » 4 years ago, # ^ |   0 i never faced this problem here before although i took inputs very much similar to this problem if not larger , still i though it was similiar to c++ 's cin/cout vs scanf/printf but i guess i was wrong >.<
 » 4 years ago, # |   0 Editorial ?
 » 4 years ago, # |   +2 Is it just me or Codeforces lags really hard?
 » 4 years ago, # | ← Rev. 2 →   0 I think this solution for Div2C should get TLE or something like that on the following test: 100000 1 2 2 3 3 4 4 5 . . . 99999 100000 1 1 1 1 1 ... 1 2 but it gets Accepted...
 » 4 years ago, # |   -10 How can O(z^2) algorithm get Accepted in Div2 A. I was trying to hack this code by giving the test case 1 1 10000. And I think this code does 10^8 operations for the particular test case. Then why didn't it gave TLE?
•  » » 4 years ago, # ^ |   0 TLE starts from 109 operations. In a good day you can even try to fit 109 operations in one second.
•  » » » 4 years ago, # ^ |   0 Oh, I see! But is it only for codeforces or for all other online judges(like codechef)?
•  » » » » 4 years ago, # ^ |   +3 I don't know about codechef, but it is also true for topcoder.
•  » » 4 years ago, # ^ |   0 On my PC it runs in about 1.2-1.3 seconds.
 » 4 years ago, # | ← Rev. 2 →   +26 It seems that some people knew that C appeared previously at Saratov training camp.Compare the following 2 solutions: 24379628 24373544There may be other people with the same code but I assume the plagiarism test should detect it. What will be done in such a case?Edit: Huh, looks like nothing has been done. platypus179 are you going to overlook this?
•  » » 4 years ago, # ^ |   0 Et tu, moejy0viiiiiv? How sad.
•  » » 4 years ago, # ^ |   +57 I have read such sentence in the rule: Solutions and test generators can only use source code completely written by you, with the following two exceptions: the code was written and published/distributed before the start of the round, the code is generated using tools that were written and published/distributed before the start of the round.So I don't think it is cheating.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Well, yeah, it's not cheating obviously because you didn't share it with anyone else. I didn't know about the rule you quoted(I've never even read the rules, heh). I just supposed that the plagiarism test would detect this and some kind of announcement would be made by the authors.So, in conclusion, it's fine to use code that was published before the start of the contest and it's the responsibility of problem setters to guarantee the originality of the tasks.
•  » » » 4 years ago, # ^ |   0 I must ask how did you find this problem? Did you remember it from solving or was it some very clever Googling? I am very impressed because the problem statements are fairly different, even though it is the same problem I suppose :)
 » 4 years ago, # | ← Rev. 3 →   +41 It looks like two first coder's solutions for div2E is same. Compare:2438040524382432UPD: their D codes looks similar too
•  » » 4 years ago, # ^ |   0 and they are from the same school :|
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 High possibility that both two ids are fake id of a red coder :| Their graph's are same too :| But going trough their past submission it seems that they write code in same style .. :) Since they both from same institution :) But there are still many codes that they shared :| :| i.e exactly same
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +14 No,No,No,our school training program always contains many problems in codeforces,so we ususally solve the same problem.We share our solutions,because our teacher encourage us to have discussions together,it's a part of our study program,too.If you say we are fake id of a red coder,that's interesting.And I really hope my id can become a red id one day.:)
•  » » 4 years ago, # ^ |   +3 First,I have to say that this problem has been done by all of my classmates in our teams.As you know,we come from the same school and the same city,and I want to tell you that div2 E has appeared in our school test we attended in the past.Also,that problem has been published by our fellow students in China before,our teacher can prove that we all solved the problem ourselves,because she has told us the solution to the problem a month ago when we first read the problem which is similar to the div2 E(maybe a little different,but the solution is similar,too).If you say we write code in same style,what I want to say is that we have studied together for two years,and all of my classmates' styles are the same.:) I have to say if the code has been written and published before the start of the round,if I need to write it again,and our classmates are taught by the same teacher,and we all have the solution by our fellow students,it's not difficult to explain this situation.div2 E is a difficult but intersting problem,I hope you can solve this problem soon,too.:)UPD:div2 D is also a interesting problem ,maybe everyone who has solved this problem used the same solution.:)
 » 4 years ago, # |   -26 is it rated ?? Div 2D problem — can't be better !!
 » 4 years ago, # | ← Rev. 2 →   +6 Why rates changed for previous contest?! :|UPD: It's fixed now
•  » » 4 years ago, # ^ |   0 shh...
 » 4 years ago, # |   +6 There is something weird going on. The ratings for Round 394 are getting updated in few profiles.
•  » » 4 years ago, # ^ |   0 mine too
•  » » 4 years ago, # ^ |   +3 Maybe not only "few profiles".. all profiles :|
 » 4 years ago, # |   0 Why this —
 » 4 years ago, # |   0 Problem B was copied :-|Tournament of Towns problem 5 is div1 B exactly!!
•  » » 4 years ago, # ^ |   0 How is the difficulty rated there?
•  » » 4 years ago, # ^ |   -32 Yes !!! This is copied from here exactly — Here -_-
•  » » » 4 years ago, # ^ |   0 what do you mean?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +1 The question paper is telling to prove only the thing that the map can be colored in only 4 colors.. It is a well known identity :|
•  » » » » » 4 years ago, # ^ |   0 You have to prove it yourself not refer to wikipedia :D
•  » » » » » 4 years ago, # ^ |   0 Here is its solution that is published!
•  » » » 4 years ago, # ^ |   0 Not for Odd idea.But I think Hifdah's link has Odd idea
•  » » » » 4 years ago, # ^ |   0 Even or Odd... A Map is Map :v So here Four-Color-Theorem applies :)
•  » » » » » 4 years ago, # ^ |   0 Algorithm and it's proof by parity: http://www.math.toronto.edu/oz/turgor/archives/TT2008F_SOsolutions.pdf
•  » » 4 years ago, # ^ |   +19 CF contest? Just Google it :|
•  » » » 4 years ago, # ^ |   +6 but nice collection of old problems from all around the world, problems were new for me and I really enjoyed that!
•  » » 4 years ago, # ^ |   0 If only it was just B :D :D :D
 » 4 years ago, # |   +25
•  » » 4 years ago, # ^ |   0 LOOOL! xD
•  » » 4 years ago, # ^ | ← Rev. 2 →   +4 I had one also — if(ans == -1) cout<<-1<
 » 4 years ago, # |   +3 I'm new to competitive programming. and this is my first contest that I have managed to solve at least one problem; although it became unrated, I learnt a lot!
•  » » 4 years ago, # ^ |   +8 Maybe you commented on wrong post -_-
•  » » 4 years ago, # ^ |   0 It's Rated! >:v
 » 4 years ago, # | ← Rev. 3 →   +10 my solution for Div2C get Accepted http://codeforces.com/contest/764/submission/24389994 but this solution should get WA on the following test :11 1 23 24 25 26 27 28 29 210 211 21 1 2 3 4 5 6 7 8 9 10 Weak tests!!
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 LOL :Dit should beYES2but yours isNO
•  » » 4 years ago, # ^ |   +1 LOL.Dude Nymar style XD
 » 4 years ago, # |   0 can anyone tell the hack for question B of div2?
•  » » 4 years ago, # ^ |   -8 2 1 5 
 » 4 years ago, # |   +24 Finally purple ^_^
•  » » 4 years ago, # ^ |   +1 congrats!
 » 4 years ago, # |   +1 Very nice contest. I like C task!!!
 » 4 years ago, # | ← Rev. 2 →   +10 The testdata for the C is weak, This code 24392371 passedIt doesn't pass this case:- 41 21 33 44 1 5 3I sent it during the contest then i realized that the idea is wrong so I changed it but I was surprised after the contest that it passed system tests.
•  » » 4 years ago, # ^ |   0 Rip testdata: (
 » 4 years ago, # |   0 http://codeforces.com/contest/763/submission/24391818Hey guys just wanna share a greedy solution to the problem Div2C I just came up with. First I have to find all the connected pairs which has different color. Then I divide by 2 because some will be repeated. And then I will just find out if there is any vertex that has the same amount of connected vertex with different color as the total sum. That vertex will be the root. Hope my solution help.
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 There is a better solution Store all the edge which connects two node and both the node having different color. Now in all this edge there should be only one common node. If there is then print yes and that node. Otherwise print no. There will be one more case in which every node have same color then in this case print YES and any node.
 » 4 years ago, # |   0 I came up with an O(n^2) solution for the second exercise but I got a TLE. Was the maximum time limit allowed O(nlogn)?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 there is a simple O(n) algorithmnote that each item i will be swapped several times against n-i+1more precisely, each item i will be swapped min(i,n-i+1) times with its counterpartso you check whether each pair will be swapped an even or an odd number of times, if the number is odd, then it is the same as 1 swap, is it is even the same as no swaps
 » 4 years ago, # |   +1 Wrong : vector < bool >can_be_child (true,N); Accepted: vector < bool >can_be_child (N,true);Took me an hour to notice that bug.
•  » » 4 years ago, # ^ |   0 But how did the first one got right answer in first 6 cases ! o.O o.O
•  » » » 4 years ago, # ^ |   0 It surprised me too. Actually vector < bool > C(true,N) is equivalent to C(1,N). It creates a vector of size 1 and initialized it with N. As N!=0 it is taken as true. Hence C(true,N) is equivalent to C(1,true). So basically It created a vector of size 1 initialised with true, but except the first value all other values(extra spaces of vectors) will be false by default. Unfortunately all inputs tll tc 6 were such that initialization values didn't affect final answer.
 » 4 years ago, # |   0 Auto comment: topic has been updated by platypus179 (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 8 →   -20 shouldn't all div2 C solutions be re-judged with stronger tests since the test data was weak ? (and accordingly updating the standings and rating changes again)EDIT:note to be clear: weak test data of problem C in div2 is not an argument in my imagination, there are two comments or more in this comments section which are describing that their codes give wrong answer on test cases they wrote in their comments but despite that their codes are accepted.
 » 4 years ago, # |   0 Div.2 D is allsome…… -_-||
 » 4 years ago, # | ← Rev. 2 →   0 Getting TLE on DIV2 C . My logic is : First i store those edges node to set those which color are different , then i put a simple dfs on each of the node assuming as root which stored in set , now which node will fulfill properties of root i break the loop and print it . If i aint found a node , print no . Now I understand for which case i got TLE . If i can stop calling dfs again and again , i can reduce TLE . But can find the logic .
•  » » 4 years ago, # ^ |   0 No need for doing dfs There is a better solution Store all the edge which connects two node and both the node having different color. Now in all this edge there should be only one common node. If there is then print yes and that node. Otherwise print no. There will be one more case in which every node have same color then in this case print YES and any node.
 » 3 years ago, # |   0