Ladies and gentlemen!
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
Auto comment: topic has been updated by platypus179 (previous revision, new revision, compare).
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.
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..
Bro..At least write correct English...you are tough to get..
I hope it won't end up unrated like yesterday :\
Time collides with Hackerrank's HourRank. I'm a pupil. I'll probably end up participating in both contests.
what does being a pupil have to do with anything?
We dont solve lots of problems. Lots of free time. :D
If you think that way, you are going to stay at pupil for a long time. Seriously, just keep trying until the contest ends.
Ofcourse I don't think that way. It was just a joke. Clearly, a bad one.
I found it funny.Society is just cruel.
May God give you red rating.
Easy. Wait until 2018.
HourRank is at 16:00 UTC. The contests don't collide.
Sorry about that. My bad.
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. :)
what's the need of writing it here?
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...
the round rated?
I hope so... It doesn't say it's unrated. Anyway, just try your best.
It is rated.
A week without any rated contest, hope this contest doesn't have any bugs like the previous one:)
blue coders prepare a contest for Red coders. Amazing :)
It should not be underestimated because of the color. Let us estimate after the contest.
As you can see, a purple color and a red also worked on the problems.
Not being an excellent coder does not mean not being an excellent problem setter :)
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.
I was orange two months ago :(
I was red month ago..
check this
There were many reds a month ago due to the magic feature. I believe that he didn't lie lol.
Magic is a lie too :D
Hope codeforces is stable today and we get a rated contest! :)
Hopefully we get something other than math and greedy for Div2 ABC :)
What do you expect? Persistent segment trees? :)
easy dp , graphs ?
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.
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.
The answer is Yes, right?
I hope to see some physics problems this round :)
Hope it won't be so..
A change of scenery would be nice... a bit tired of all the math problems haha
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
I hope this time we don't have any problem with the server. I got trauma from this image in the previous contest.
it is already showing very busy, i wonder if it will happen today again
Finally Div1 & div2 separated
CodeForces is toooooooo slow from here Hope not a server error
A good time for Chinese students!Hope it will be a good warm-up round for the Chinese Winter Camp next day.
Hope that this time contest doesn't go unrated.
I hope that this contest will be interesting :)
I hope all is well this time! :D
PC hanged while reading problem A. Forced shutdown and restart. More than 3400 submissions on A and 1800 submissions on B. out of competition :(
What does "more" in div1D mean? more pairs or more vertices?
In the input of Problem C from div2, u < v , or it doesn't matter?
The questions are to be asked in the contest.
how?
There is a special button on page "Problems"
thank you!
Why I can not solve more than 3 problems A B C ????? ^)
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!
problems like shit .
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.
fu** off
Sorry, but deep_learning is right. Argument this or go away.
also fu** off
You are too rude Please, stop it.
Maybe (s)he's on a period
Problems were easy compared to regular contests
The gap between div2C and div2D problems is far bigger than 250 points imo.
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.
Now when I saw solutions to D I'm not so sure either :D
Easier to code? Could you, please, share your solution? I've struggled a lot with implementation.
24377942
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.
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.
Is this an IQ contest or something ??????????????
If it is, I am very stupid :D
Very nice problem D, I really like it.
How did you solve it?
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.
Can you prove its correctness?
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)
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 .
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.
OMG, this is so simple and easy. And there am I, generating an adjacency list and trying to solve the graph problem.
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 ?
no, usual one don't be rude. dude
How to approach problems like Div2C which require dfs to calculate answer?
Consider writing dfs.
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 ^_^
But what is diffuclt in this problem? The dfs there is rather simple.
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.
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 .
I'm doing 2 dfs' only. And finding the pair is O(n)
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.
How to solve Div1 C??
How to solve Div1 C without random !
Div 1C is the same as this problem http://mirror.codeforces.com/gym/100451/problem/I.
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.
how to solve it ?
I could only think of O(N^2)
By the way, is there any published editorial for Petrozavodsk training camp contests? The official one seems to require credentials to log in.
On problem D, my output for the first test is:
Why does it give WA?
Here are the rectangles, black numbers are indexes, brown numbers are color. No same color touches:
In system your output is "NO".
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.
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.
Oh yeah, thanks a lot.
No Hacks This Time :) !!
I made 3 :P
some didn't handle the case of only two different number in B
I made 2. I think C had weak pretests.
How to solve Div1 B??
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.
colour of a rectangle is 2*(x1&1) + (y1&1) + 1
How to solve div2C ?
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. ;)
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.
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. :)
I think it was better that task D worth 2250 points, it seems really tough for lots of competitors
Div2 A .. very bad statement
Why?
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.
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.
exactly :D
Again, it is stated that you should minimize killed artists.
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."
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!
I didn't read statements, just looked samples, then got the idea :D
Strongly agree!
Does anyone knows the test case of pretest 7 of problem C in the div 2 contest. It's like a freaking walls.
5 — 1 2 — 1 3 — 1 4 — 1 5 --- Mb
If you have figured out what's special about pretest 7 let me know. Thanks
For description of DIV1 E. I think you should let (1<=l<=r<=100000) be (1<=l<=r<=n)
And it's same as hdu 5333 :P
I think some coders will get runtime error if r>n
Yeah, seems like easier version of this: http://acm.hdu.edu.cn/showproblem.php?pid=5333
Extra constraint on edges allows simpler but uglier solutions.
Thank you for the nice problemset! I really enjoyed this contest!
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)
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 eitherX1-X2=1 (mod 2)orY1-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.Hmmm...interesting observation...I wish I could notice that at the right time...Thank you.
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.
No. Just output answer based on whether x and y are odd or even. Because the side length is always odd.
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?
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.
I solved without using dfs/bfs/dsu. Just checked edges between two different colored vertices.
even i tried with DSU and segment tree got memory limit exceeded :( .
Very nice div2 D! That was wonderful
Nice hack case to C: n=m-3 and sequence lacks 3 elements that don't form arithmetic sequence.
How did you solve Div1C ?
Auto comment: topic has been updated by platypus179 (previous revision, new revision, compare).
Div2D was awesome . How to solve it if the dimensions of the rectangles can be even too ?
By the four-colour theorem, the answer definitely exists.
Not really sure how to construct the solution though.
http://people.math.gatech.edu/~thomas/PAP/fcstoc.pdf
:P
So this paper says there is quadratic algorithm, however I believe it can be done in O(nlog(n)) too.
Why?
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.
There can be 5-cycles, actually.
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.
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.
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
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).
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.
Yeah bro, but Div1 B is an even bigger fail for most people here. :)
Me after reading Div1-B solution
Best Div1-B problem ever (even though I failed to solve it).
Wasted whole time thinking about point compression, graph building, coloring graph.. And messed up everything :| :|
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 :(
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?
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 =)
What, the complexity will be O(nlogn).
Then, probably, I don't understand. Could you, please, explain how would you use DFS to color the graph?
For some reason I believe you can do greedy approach while scanning through the rectangles from left to right. Does that seems plausibly true?
Good idea, that may work.
Yeah, that sounds good.
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.
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...
This might work. But why do you need 3 if you have already sorted them by the number of neighbours?
Sorry, my mistake. In fact, I tried BFS, just visit each neighbor by F(x)
Thats what I did in contest. But for some reason I get WA on test 1 while it works on my compiler.
Not joined the contest, but isn't it related to parity of corners?
Read my first sentence.
This is my second time to participate in codeforces, and now or unrated, I hope this will be integral.
Nice problems. I really enjoyed. ty
When will be rating updated ?
After seeing this 24373708 solution for Div2D/Div1B —
Amazing solution. I start thinking that D was very easy problem after seeing this :)
That's nothing. 17059723 was once the correct answer to a Div2D.
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
It seems the standings page is a bit bugged.
how?
Due to slow response time of the website and slow rating changes, this contest will be unrated.
Have a great day!
Do you think it's slow rating change?
I think he's just making a joke of tuesday's contest.
Problems like today's Div 1B make me feel handicapped :| Such an easy solution, yet I was nowhere near it during contest
My head is hurting very much for not being able to solve. Uggh. I hope intuition comes by practice.
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://mirror.codeforces.com/contest/764/submission/24371107 http://mirror.codeforces.com/contest/764/submission/24388501
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.
Is it just me or Codeforces lags really hard?
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?
TLE starts from 109 operations. In a good day you can even try to fit 109 operations in one second.
Oh, I see! But is it only for codeforces or for all other online judges(like codechef)?
I don't know about codechef, but it is also true for topcoder.
It seems that some people knew that C appeared previously at Saratov training camp.
Compare the following 2 solutions: 24379628 24373544
There 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?
Et tu, moejy0viiiiiv? How sad.
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.
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.
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 :)
It looks like two first coder's solutions for div2E is same. Compare:
24380405
24382432
UPD: their D codes looks similar too
and they are from the same school :|
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
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.:)
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.:)
Why rates changed for previous contest?! :|
UPD: It's fixed now
shh...
There is something weird going on. The ratings for Round 394 are getting updated in few profiles.
mine too
Maybe not only "few profiles".. all profiles :|
Why this —
Problem B was copied :-|
Tournament of Towns problem 5 is div1 B exactly!!
How is the difficulty rated there?
Yes !!! This is copied from here exactly — Here -_-
what do you mean?
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 :|
You have to prove it yourself not refer to wikipedia :D
Here is its solution that is published!
Not for Odd idea.
But I think amsen's link has Odd idea
Even or Odd... A Map is Map :v So here Four-Color-Theorem applies :)
Algorithm and it's proof by parity: http://www.math.toronto.edu/oz/turgor/archives/TT2008F_SOsolutions.pdf
CF contest? Just Google it :|
but nice collection of old problems from all around the world, problems were new for me and I really enjoyed that!
If only it was just B :D :D :D
LOOOL! xD
I had one also —
:P
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!
Maybe you commented on wrong post -_-
It's Rated! >:v
my solution for Div2C get Accepted http://mirror.codeforces.com/contest/764/submission/24389994 but this solution should get WA on the following test :
11
1 2
3 2
4 2
5 2
6 2
7 2
8 2
9 2
10 2
11 2
1 1 2 3 4 5 6 7 8 9 10
Weak tests!!
LOL :D
it should be
YES
2
but yours is
NO
LOL.Dude Nymar style XD
can anyone tell the hack for question B of div2?
Finally purple ^_^
congrats!
Very nice contest. I like C task!!!
The testdata for the C is weak, This code 24392371 passed
It doesn't pass this case:-
4
1 2
1 3
3 4
4 1 5 3
I 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.
Rip testdata: (
http://mirror.codeforces.com/contest/763/submission/24391818
Hey 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.
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)?
there is a simple O(n) algorithm
note that each item i will be swapped several times against n-i+1
more precisely, each item i will be swapped min(i,n-i+1) times with its counterpart
so 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
Wrong : vector < bool >can_be_child (true,N);
Accepted: vector < bool >can_be_child (N,true);
Took me an hour to notice that bug.
But how did the first one got right answer in first 6 cases ! o.O o.O
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.
Auto comment: topic has been updated by platypus179 (previous revision, new revision, compare).
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.
Div.2 D is allsome…… -_-||
http://mirror.codeforces.com/blog/entry/52419
Div1E a lot of solutions can be hacked by the following test: 4 2 4 1 2 3 4 2 4 1 3 2 1 3 2 4