### Vovuh's blog

By Vovuh, history, 3 weeks ago, translation, ,

My session is almost done and holidays are just around the corner. It means that it's time for another one contest! Happy New Year to all of you!

<copy-pasted-part>

Hello!

Codeforces Round #529 (Div. 3) will start at Dec/27/2018 17:35 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

UPD: After the contest, you can discuss the problems in the community Discord server. Maybe I will take part in the discussion.

UPD2: Editorial is published!

UPD3: I forgot to thank my friend Roman Ajosteen Glazov for helping me with testing the round!

UPD4:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 sai_150050066 6 114
2 Skeercg 6 167
3 golubtsowroman 6 167
4 phungtienminh 6 170
5 forloop 6 183

Congratulations to the best hackers:

Rank Competitor Hack Count
1 MZuenni 219:-8
2 ______-__________-______ 105:-39
3 bacali 81:-66
4 Random456 15:-2

549 successful hacks and 540 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A ChiIIi 0:01
B GreacaEgalLuluOri2 0:02
C ChiIIi 0:05
D ChiIIi 0:12
E hahahahaha111 0:13
F kuchnaahopaayega 0:16

•
• +141
•

 » 3 weeks ago, # |   +9 Didn't we just have a div 3 this week? Instead, why not have an educational? Since the difficulty of these contests is comparable to that of div 3 contests and it would be rated for a larger audience.
•  » » 3 weeks ago, # ^ |   +8 We have an educational round on 28th already :)
•  » » » 3 weeks ago, # ^ |   +10 Yeah, so the questions could have been used for an educational contest someday after good bye-2018.
 » 3 weeks ago, # |   +1 Awesome Anyway I love Live Contests so much Great Job for your efforts on Writing and testing the problems Happy New Year for all
 » 3 weeks ago, # | ← Rev. 3 →   -19 Just first div 3 contest was the real div 3. (in problem difficulty)
 » 3 weeks ago, # |   +11 If the difficulty trend in Div3 rounds keeps going, we might have to expect IOI level problems.
•  » » 3 weeks ago, # ^ |   +57 Hey, it's IOI jury's problem that their task was easy enough to fit into div3 contest!
 » 3 weeks ago, # | ← Rev. 2 →   -33 Eden Hazard the best player in the world right now
 » 3 weeks ago, # |   0 Div 3 is easy for me, give me div 4
•  » » 3 weeks ago, # ^ |   0 But div 1 > div 2 > div 3
 » 3 weeks ago, # | ← Rev. 2 →   -21 is it contributed?
 » 3 weeks ago, # |   -6 Good luck!
 » 3 weeks ago, # |   -29 is A FFT?
 » 3 weeks ago, # |   -17 hope this round results in a higher rating to all my friends ... Good luck to all
 » 3 weeks ago, # | ← Rev. 2 →   -19 Why I see the "" again...Could you pay more attention when writing an announcement?
•  » » 3 weeks ago, # ^ |   0 At least he is spending time for making the contest. Announcement is not important more important is how he settled all the div3 contests so beautifully.
•  » » » 3 weeks ago, # ^ |   -7 I agree with you,but I think a good announcement is also important.
•  » » 3 weeks ago, # ^ |   +6 Meh, why would you need a different announcement every time? Announcement notifies you of contest (in case you only look at main page and not the schedule) and reminds you a bit of the rules. This one makes its job pretty fine, I guess. It feels like a waste of time to write it from scratch every time.
 » 3 weeks ago, # | ← Rev. 3 →   -30 ****_ahaahaahaahha bad contest you have brain or no? wtf?_**** ****_Div1+Div2=Div3_**** ****_Eden Hazard the best player in the world right now_**** ****_is it contributed?_**** ****_hello i live in a very rural part of czechoslovakia and i am wondering if the contest is contributed and or rated for me thank you_**** ****_are you ssure? i cant find it x(_**** ****_ahahahahaha one two three 123_****
 » 3 weeks ago, # | ← Rev. 2 →   0 Just first div 3 contest was the real div 3. (in problem difficulty)
 » 3 weeks ago, # |   0 I hope it is not like the previous contest
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   -11 I hope it is not like you
 » 3 weeks ago, # |   0 I will do my best and I want to get gray
•  » » 3 weeks ago, # ^ |   0 I think so
 » 3 weeks ago, # | ← Rev. 2 →   +10 Good luck folks! Image
 » 3 weeks ago, # | ← Rev. 3 →   +18 Good luck to the server
 » 3 weeks ago, # |   +18 Thanks vovuh for div 3 again. I like the higher frequency for div 3 these days.Hope it's a great contest.
•  » » 3 weeks ago, # ^ |   +21 I hope so :) Good luck!
 » 3 weeks ago, # |   0 How to hack a solution.
•  » » 3 weeks ago, # ^ |   0 Go to standings then click on any + sign
 » 3 weeks ago, # |   0 Got 2 WA using pow() in C++ :( in problem C.
•  » » 3 weeks ago, # ^ |   +5 Try to use byte shifts. For example (1 << 5) is equal to pow(2, 5). This is only for powers of number 2.
•  » » » 3 weeks ago, # ^ |   0 Yes, I had corrected it in the last 2 minutes :)
•  » » » » 3 weeks ago, # ^ |   0 you can use int(pow(2,i)), but bit shift works fine too
 » 3 weeks ago, # |   0 How is there 100% systests already? O_o
•  » » 3 weeks ago, # ^ |   0 Maybe because it has already the pretests passed, I guess the test should happen after the hack phase is over, otherwise, maybe the machines were ultra fast today
•  » » 3 weeks ago, # ^ |   -8 Yeah you can use a segment tree for it. The leafs should store the count to open and closed brackets.
•  » » » 3 weeks ago, # ^ |   +1 Thank you :)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +9 If a '(' represents 1 and a ')' represents -1 then the bracket sequence is valid if and only if every prefix sum is non-negative and the total sum is 0. When you change a '(' into a ')' it subtracts 2 from every prefix sum starting from that point. The opposite change has the opposite effect. Now just figure out which of these changes make the prefix sums non-negative and the total sum equal to zero.
•  » » » 3 weeks ago, # ^ |   0 Thank you!
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 what about this "))((" it will be equal to zero however it is not valid??
 » 3 weeks ago, # |   +20 thanks for an actual Div 3 round!!! on a side note, does anyhow know how to D? I struggled at it quite a bit.
•  » » 3 weeks ago, # ^ |   +1 If two integers are in the same line, this means they're adjacent in the graph. The input gives you all n edges in the graph (though maybe not oriented correctly).Arrange the edges to form a cycle. You may need to reverse your output if the edges are facing the wrong direction.
•  » » » 3 weeks ago, # ^ |   +10 that's the problem I'm facing — how do you know if the edges are in the wrong direction?
•  » » » » 3 weeks ago, # ^ |   0 Look at the first 3 values. If they match what's given in the input, then the solution is facing the correct direction. Otherwise, reverse the output.
•  » » » » » 3 weeks ago, # ^ |   0 I checked that reversing conditions for all n, if it's true i incremented the counter variable.At last if that counter having value equal to n i reverse the output else not.I got AC.But don't understand the reversing condition.Can any one can help?
•  » » » 3 weeks ago, # ^ |   -9 i tried topological sort but it gave me WA on test 3
•  » » » » 2 weeks ago, # ^ |   0 Topological sort doesn't guarantee a unique tree, which is what you want (as you'd be breaking the cycle otherwise). The generated trees depend on the order in which you visit the neighbors, which explains why you got WA on the third test.
•  » » 3 weeks ago, # ^ |   -7 The approach I used is slightly different: if a and b are on the same line, then either b occurs on the line of a or a occurs on the line of b. We check which of these two is the case, and immediately know whether there is an edge from a to b, or from b to a. By doing this operation for every line, we calculate all the edges with the correct direction. The only problem with this approach is that it may give incorrect answer for n = 3; but outputting 1 2 3 always works if n = 3, since the all the inputs for 1 3 2 would be correct for 1 2 3, as well.
•  » » » 3 weeks ago, # ^ |   0 Damn, used the very same approach. Didn't handle the case of 3 properly. https://codeforces.com/contest/1095/submission/47583430
•  » » 3 weeks ago, # ^ |   -13 ezaf dude, if a[a[i]] == b[i] or b[a[i]] == b[i] then next_to[i] = a[i], else next_to[i] = b[i]. then print 1, next_to[1], next_to[next_to[1]], ...
•  » » 3 weeks ago, # ^ |   0 Since n>=3 Consider if we are at node "a" and we know by input that node "b" and node "c" are its next nodes So, case would be likeCase-1 : a->b->c Case-2 : a->c->bTo verify which is the case , simple check that if "c" comes in the next_nodes_list of "b". Then it will be Case-1. If "b" comes in the next_nodes_list of "c", then it will be Case-2 If it is case-1 , then it is sure "c" does not contain "b" in its next_nodes. If it is case-2 , then it is sure "b" does not contain "c" in its next_nodes.Use this above condition and put nodes in order.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I solved it in the following way — 1) every number will appear exactly 2 times, one in the vertex to which it is next and and secondly in the vertex where it is next to next. 2) lets look for the vertices for which we get 1, and let then be called vertex a and b. so the order is either a b 1 or b a 1. 3) we go to vertex a and look for b , if b is there it means b comes after a so the order is a b 1, or if not present the order is b a 1. 3) After getting the order of first 3 element we will look for the adjacent vertices of vertex at index 1 [ 'b' in case of a b 1, and 'a' in case of b a 1], the vertex other than 1 will be the vertex at index 3, after we will repeat this process for all the vertices up to index n-3. my submission, time complexity O(n)
 » 3 weeks ago, # |   0 Problem E was almost the same as BRCKTS problem from SPOJ.
•  » » 3 weeks ago, # ^ |   0 I am using segment tree just as usual , can you help me where i am wrong here is my code for spoj BRCKTS code for spoj this code is giving wrong answer on spoj can you please help me. P.S i am asking help for BRCKTS question not problem E
 » 3 weeks ago, # |   -47 Easy round, I solved all problems
•  » » 3 weeks ago, # ^ |   +8 You mean you consistently got WA on testcase 2 on all problems?
 » 3 weeks ago, # |   -8 Does hacking help my rating?
•  » » 3 weeks ago, # ^ |   -23 Yes, it helps your rating
•  » » 3 weeks ago, # ^ |   +2 You don't get points for hacking in Div. 3. It helps you indirectly by making you place higher in the standings.
 » 3 weeks ago, # |   0 !(my last comment) = I love div3 rounds :Panyway how to solve D it looked like a graph problem to me
•  » » 3 weeks ago, # ^ |   0 There is no need for graph. Using 1 as the first number, find the first 3 numbers with brute force. Then its easy implementation.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 It was a simple implementation problem. You just need to find a possible permutation of first 3 elements. lets say, p1, p2 and p3. Then you can easily find the rest elements. How?Finding part 2 is easy,As you know p2 and p3, you can easily find p4 because, only number after p2 other than p3 is p4.In other words, a21 = p3 => p4 = a22; And so on, we can find p5, p6....pnFor part 1,Fix p1 lets say '1'; now p2 and p3 can be either a11 or a12. How to fix them?If a21 = p3 or a22 = p3 then p1, p2, p3 is correct; else p1, p3, p2 is correct;Check my submission: https://codeforces.com/contest/1095/submission/47575058
•  » » » 3 weeks ago, # ^ |   0 damn they scared me with that circle
•  » » » 3 weeks ago, # ^ |   0 Hi Can you please point out why my solution got WA on 285th Kid https://codeforces.com/contest/1095/submission/47585800.
•  » » » » 3 weeks ago, # ^ |   0 Your code's logic seems incorrect. Please try this simple input: 5 5 4 1 5 2 1 3 2 4 3 Output should be (a cyclic shift of): 1 5 4 3 2But your code is printing: 1 5 4 2 3
 » 3 weeks ago, # |   0 Can I get a hint for problem C:Powers of 2
•  » » 3 weeks ago, # ^ |   0 Check the binary representation of the input
•  » » 3 weeks ago, # ^ |   0 First find the binary representation to know the minimum powers necessary. Now, if we can represent n using x powers of 2, then we can also do it using x+1 powers of 2, provided x < log2(n). Think about how to get x+1 powers from x powers.
•  » » » 3 weeks ago, # ^ |   0 Can you elaborate further by taking an example?
•  » » » » 3 weeks ago, # ^ | ← Rev. 3 →   +1 Suppose you have x slices of pizza, but you want to have x+1 slices what do you do, divide one of the slices into 2, now you have x+1 pizza slices.Similarly, if you have minimum powers of 2 necessary to make a number. you can keep on dividing the numbers till you get k numbers.you can also do it recursively. See my codes: 1) Recursive 2) Iterative (Using a queue)
•  » » » » » 3 weeks ago, # ^ |   0 i cannot understand why u use k-=mn; then func( x, min(k+1,x) ) in your code can you eloborate please
•  » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Well, it's hard to explain because I have done it in a messy way, What I am just doing is that for each number in binary representation of n, I keep on dividing it till I have k numbers. For example: Take n=10 it can be represented in minimum powers as: 8+2 I keep on dividing 8, then I go to 2 then I keep on dividing it. When I have k numbers I stop dividing.You can build your own logic for this.
 » 3 weeks ago, # | ← Rev. 3 →   0 Wonder why Problem F if there are Multiple index have smallest cost pick any of them to build edge to is ok
•  » » 3 weeks ago, # ^ |   0 you can refer to MST Algorithm like Prim and Kruskal
•  » » » 3 weeks ago, # ^ |   0 i means the given a1~an may have multiple of them have same smallest value and why i pick any of them build edge connect to others the answer will be same
•  » » » » 3 weeks ago, # ^ |   0 you can consider why MST Algorithms like Prim and Kruskal do not care about that
•  » » 3 weeks ago, # ^ |   +3 Assume we've already chosen which special edges will be present in our tree. We need to figure out the cheapest way to join the connected components that they induce.The total weight for the other edges is some expression of the form ai1 + ai2 + ... + aik. We have to choose at least one vertex from each connected component induced by the special edges, so the minimal possible value of the expression for fixed k (ignoring any other restriction) is obtained by first adding the smallest ai from each component, and then adding the smallest ai of them all however many times. By choosing any vertex with minimum cost we will get exactly this value for the expression, so it doesn't matter which one we choose.
•  » » » 3 weeks ago, # ^ |   0 Thanks. I think i got it.
 » 3 weeks ago, # |   0 Can F be solved by Prim's Algorithm? I thought this is MST problem, but how can we find MST when we have so many edges? I know we can use binary heap, priority queue and some data structures on Prim's algorithm, but I don't get how to fit in time and memory. Plz let me know if I'm missing something.. (I'm not even sure if this is a MST problem or not)
•  » » 3 weeks ago, # ^ |   0 It is MST, with an extra idea. It turns out the only edges with costs ax + ay that we need to consider are the ones that involve the vertex with minimum cost.
•  » » » 3 weeks ago, # ^ |   0 Thanks! I'll go study more through it :)
•  » » 3 weeks ago, # ^ |   0 It is a MST problem. Use the set 1 as the given edges. find the smallest ai and make n-1 edges this vertex to other vertices. Call this set 2 of edges. combine both sets and apply prim's algo.
 » 3 weeks ago, # |   0 Any one can help me with problem E! I have no idea how can i solve the problem!
 » 3 weeks ago, # |   0 I'm getting a wrong answer by the checker but if I compile it elsewhere I get the right solution.The checker's log read: wrong output format Unexpected end of file — int32 expectedCan someone explain what is happening Submission
•  » » 3 weeks ago, # ^ |   0 It means that your solution just terminated when jury has some output left to check. In your submission, jury had one more integer number to check, but your execution ended without giving an integer.
•  » » » 3 weeks ago, # ^ |   0 But if I compile the same code elsewhere I'm getting a correct answer as per the jury.
•  » » » » 3 weeks ago, # ^ |   0 Can you specify about your machine or where you compiled?I mean, some links to online compiler or you machine's OS, editor, complier
•  » » » » » 3 weeks ago, # ^ |   0 Online compiler Jdoodle
•  » » 3 weeks ago, # ^ |   0 Should I report it to someone?
•  » » » 3 weeks ago, # ^ |   0 vovuh Please look into this.
•  » » » » 3 weeks ago, # ^ |   0 Lol. I looked into this and I can say you should remove your 'very useful' optimization pragmas because your solution works fine without them. But I don't know what is the real problem because I don't know anything about such 'optimizations'. Maybe MrDindows can help you?
•  » » » » » 3 weeks ago, # ^ |   0 I can, that's because of abm in target. https://codeforces.com/blog/entry/59457?#comment-431178
•  » » » » » » 3 weeks ago, # ^ |   0 Thanks, that's quite interesting!
 » 3 weeks ago, # |   0 In Problem D, can the permutation be in any cyclic order (clockwise or anti-clockwise)? Like for this test case 5 3 5 1 4 2 4 1 5 2 3is this 1 4 2 3 5 also a valid answer?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 No. 1 4 2 3 5 is invalid. You must consider the order. (i.e standing in front or back matters)You should check clockwise or counterclockwise. After that, starting point doesn't matter.1 5 3 2 45 3 2 4 13 2 4 1 52 4 1 5 34 1 5 3 2These are the only valid answers for first example.
•  » » » 3 weeks ago, # ^ |   0 I tried to think of making a bi-directional graph and then apply a DFS. But it didn't seem to work out. Not able to figure out how to determine the order?
 » 3 weeks ago, # | ← Rev. 2 →   0 Problem D is ambiguous, I cannot understand what he want. can anyone help me please. thanks in advance.
•  » » 3 weeks ago, # ^ |   0 There's a directed circle(a premutation p), giving the two vertexes behind every vertex, you should print a valid order.
•  » » » 3 weeks ago, # ^ |   0 Ycrpro1 thanks bro, i got Acc
 » 3 weeks ago, # |   +1 Why all Java solutions on B are getting hacked? Although they all seem correct.
•  » » 3 weeks ago, # ^ |   0 MZuenni on fire!
•  » » » 3 weeks ago, # ^ |   +8 Java's DualPivotQuicksort used in Arrays.sort is deterministic and therefore in O(n^2) they all get timelimit by that...
•  » » » » 3 weeks ago, # ^ |   0 Good Job! Even though I was one of the victim, felt good to learn these intricate things.Cheers!
•  » » 3 weeks ago, # ^ |   0 May be for this reason : Link
•  » » » 3 weeks ago, # ^ |   0 yes thats correct. p.s. for all people writing me direct: i have reached my codeforces message limit and therefore cant respond for the next hour...
 » 3 weeks ago, # | ← Rev. 2 →   0 Why did my solution for F Link failed?? Update:Solved
•  » » 3 weeks ago, # ^ |   +3 your variable mst_cost is int.... it should be long long
•  » » » 3 weeks ago, # ^ |   0 Yup,that was the problem, just got an AC, Thanks acIN1go
 » 3 weeks ago, # | ← Rev. 2 →   0 for problem D, why WA??? Judge says wrong output format Unexpected end of file — int32 expectedlink to my code is Your text to link here... please someone check it...
•  » » 3 weeks ago, # ^ |   0 You should be printing 5 numbers and you only printed 2
•  » » » 3 weeks ago, # ^ |   0 yes, that's the problem. IDE prints all the five values but, judge shows only two. I'm not getting the reason.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 1) I had the same issue before, that happens because the current compiler makes some "corrections" to the code at runtime, to see the exact result on your ide (in this case Codeblocks) you should make it follow the C++11 standard as seems in this link2) About your code, I got it working removing adj = new list[n + 2]; and vis = new int[n + 2]; but instead delcaring adj and vis like this list adj[200001]; int vis[200001];It's a good practice to declare your variables as globals and at the same time with the max length posible since that way only you can be sure they are fully initialized (the default compiler in our machines does some tricky stuff when a variable is not propelly initialized and instead of giving an error it tries to make it work which makes us think it works propelly meanwhile codeforces and other evalutaros don't do that)
 » 3 weeks ago, # |   0 A lot of people got hacked on Problem B, including myself. Does anybody know what the issue could have been?
•  » » 3 weeks ago, # ^ |   0 Hey:)So Java's Arrays.sort() uses quicksort, and the average runtime is nlogn but worst case runtime is n^2. The hack is an anti-quicksort hack. To fix this, you should declare the array as Integer[] rather than int[], since merge sort is used to sort objects, which runs in time.
•  » » » 3 weeks ago, # ^ |   0 Thanks! I'll remember that for future reference.
 » 3 weeks ago, # |   0 What does this statement mean in problem "F. Make It Connected"?You don't have to use special offers: if there is a pair of vertices x and y that has a special offer associated with it, you still may connect these two vertices paying ax+ay coins for it.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 If an offer with cost w is included, the cost of building an edge connecting x and y can be either ax + ay or w, it's up to your choice (yet obviously if you're really going to build that edge you would want the minimum value between them).
•  » » 3 weeks ago, # ^ |   0 For two vertices x and y, there may be some special offers. You may potentially use one of these offers during the construction if you want to connect x to y. However, you can connect x to y without using any of these offers, as well. In that case, the cost of connecting x and y is given by ax + ay.
 » 3 weeks ago, # | ← Rev. 2 →   0 Today during contest I got WA on test 1, for problem D. While it ran well on my IDE with correct answer. My submission: https://codeforces.com/contest/1095/submission/47569625Later after 20 mins I realized, I had left a return false; statement inside the check() function. After adding the line it got accepted. (https://codeforces.com/contest/1095/submission/47575058). If it wouldn't have worked on my IDE I would have fixed it and submitted in matter of seconds, rather than 20 mins of trying to find some error which still works fine on my IDE. Any ideas why it worked fine for all sample cases plus my own custom cases, on my IDE but not on cf server?
•  » » 3 weeks ago, # ^ |   +1 It's called "undefined behaviors".Since the function return a non-void value and you left its ending ambiguous (not stating explicitly if it would return true or false), so depending on the compiler and environment of your PCs, IDEs or online judges, the returning value will fluctuate.
•  » » » 3 weeks ago, # ^ |   +8 Oh, now it makes sense. Thanks for the clarification :)
•  » » » 3 weeks ago, # ^ |   0 (https://codeforces.com/contest/1095/submission/47597346) Dude, can you please check my code once. it prints all 5 numbers on the IDE, but here it prints only two digits and says wrong output format Unexpected end of file — int32 expected.
 » 3 weeks ago, # |   -30 declare the round unrated for java users whose B was hacked!
•  » » 3 weeks ago, # ^ |   -6
•  » » » 3 weeks ago, # ^ |   +3 why should that happen?there is no difference between getting hacked or failing the system tests (there are also enough problem setters who directly include such testcases for systemtests so no hack is needed).And you will learn from this and will think about this the next time you use Arrays.sort...
•  » » » » 3 weeks ago, # ^ |   +1 but that works perfectly well with c++, as it is faster
•  » » 3 weeks ago, # ^ |   0 they gave the java users only 1k ms they should have given 2k ms
 » 3 weeks ago, # |   -16 For java we are allowed 2000 ms for a problem in which the limit is 1000ms but here we got a tle at 1000mssubmission here: http://codeforces.com/contest/1095/submission/47602564please rectify this
•  » » 3 weeks ago, # ^ |   0
•  » » » 3 weeks ago, # ^ |   +2 the problem is NOT that java is generally slower! the problem is that you used an algorithm which is in O(n^2) which is clearly to slow!
•  » » » » 3 weeks ago, # ^ |   0 So according to you what could be an alternative to Arrays.sort() for getting O(nlogn)?
•  » » » » 3 weeks ago, # ^ |   0 According to the documentation of Arrays.sort() Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.
•  » » » » 3 weeks ago, # ^ |   +1 hey i read your blog. Thanks for the information, I got what you were trying to say.
 » 3 weeks ago, # |   0 I Learn a very important thing in this contest. DO NOT FEAR to read hard problems. I am able to solve problem F easily with kruskal, but i didn't solve it during the contest because I always thought that if I can't solve easier problems (problem C and E), i can't solve the harder one.
•  » » 3 weeks ago, # ^ |   -7 chong
 » 3 weeks ago, # |   -11 Hi Everyone, I got a runtime error due to wrong evaluation of log(n)/log2 by the CF compiler, but it is being evaluated fine in my own ide, and a number of online compilers. Isnt it unfair for me. my submission,problem c. For input 8,1 CF compiler is evaluating it as 2, where as it should be evaluated as 3
•  » » 3 weeks ago, # ^ |   +3 Nope, it crashes in your while while((k-cnt) != 0){ ...
•  » » » 3 weeks ago, # ^ |   0 yes, but thats because 'sz' was evaluated as 2, if it would have been evaluated as 3, I would have got "YES 8"
•  » » » » 3 weeks ago, # ^ | ← Rev. 3 →   +3 Gotcha, it's weird behavior. As to why, i guess you should consider that doubles aren't exact just as the result of log() isn't, so the division isn't exactly 3. You should avoid doubles whenever possible, in this case when you want to check over log in base 2 you should use bit operations.
•  » » » » » 3 weeks ago, # ^ |   0 yep, ceil would have done it.
•  » » 3 weeks ago, # ^ |   +3 Try using log2(n) instead of log(n)/log(2). Idk, it may work or not, but you should have gone for ceil value anyway.
 » 3 weeks ago, # |   0 When will the ratings change?
 » 3 weeks ago, # |   +3 I love Vovuh's Problem set...He is making Div3 great
 » 3 weeks ago, # |   0 My Submission 47584196 was rejected by Codeforces compiler because the values of INT_MAX and LONG_MAX are apparently same on codeforces it works perfectly on my laptop! Isn't this unfair to me? What can i do about this now?
•  » » 3 weeks ago, # ^ |   -6 They are same on codeforces, because they are same in C++. (long and long long are different).See here.
•  » » » 3 weeks ago, # ^ |   0 On my machine they are different! :(This is so unfair :|
•  » » » 3 weeks ago, # ^ |   0 Even on GeeksforGeeks they are different!https://ide.geeksforgeeks.org/gL0gqCYQVs
 » 3 weeks ago, # | ← Rev. 2 →   0 Could someone help me with problem E? I think I have not understood what is a regular sequence. In the first example — (((()) , can I change the second bracket to get ()(()) or change the 4th to get ((())) ? I can insert 1 and + into them such as (1)+(1+(1+1)+1) and (1+(1+(1)+1)+1) but why are they not regular ones?
•  » » 3 weeks ago, # ^ |   0 Please read the description carefully!
 » 3 weeks ago, # |   0 What is the solution to Problem B? I am getting WA on test case 6.
•  » » 3 weeks ago, # ^ |   0 There is 3 cases. The first one is to take one element that is not minimum nor maximum: The instability doesn't change. The second case is to take one element that is maximum: The instability will be the maximum of the new array minus the minimum of the array. The third one is to take one element that is minimum: The instability will be the maximum of the array minus the minimum of the new array. So the answer is min(second case,third case).
 » 3 weeks ago, # |   0
 » 3 weeks ago, # |   0 In problem C, Many solutions are getting runtime error on test case 10 that is 1 1 But it is showing right output in almost every other compiler/IDEHere's my code. https://ideone.com/qVAsiL
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I suspect that it is Undefined Behaviour. For test case 1 1, you pass 0, 0 as your arguments to the function rec(). It will return when y == 0 part without actually initialising vector V. So when you are executing this line fn(i,V.size()-1,0), V.size()-1 gives random big values and can be machine dependent. EDIT: I was right. Solution. It passes after removing ambiguity I mentioned.
 » 3 weeks ago, # |   0 Is there any editorial posted for this Div3 Round?
 » 3 weeks ago, # |   0 Can we have the editorials?
 » 3 weeks ago, # |   0 How to approach problem E?
•  » » 3 weeks ago, # ^ |   +1 try to think when flipping a single character will make the whole sequence good , character can be "(" or ")" at each position so just two case, see what should be the number of EFFECTIVE "(" and ")" on both sides of concerned index. there difference must be one(you can verify). but we must be careful that either left or right side should not have parts which cannot be balanced either. while going left to right(maintain array A) try to maintain the net effective number of "(" at each index, means for all 0<=i<=n-1 store number of free "(" from [0->i] , and do same for ")" while going from right to left(maintain array B) maintain num of free")" for each i . on which indices we should perform the tests because other indices may give positive test instead of them they are wrong->if for any l>=0 A[l]=-1 then we should not check for indices greater than l (convince yourself by examples) because they will never effect left part in any better way so range to check will be [0,l] l can be at max n-1 ,similarly in array B for index i<=n-1 check till you approch 0 or where it is negative first time.check should be made finally on intersection of [0,l] and [m,n-1] :)
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +5 Calculate balance of given string. Let bal[i]=balance of substring [0;i]. (Balance is a sum of opening and closing brackets). Now go through this array and check:1) if bal[i-1]<0 at any moment, then you can stop and print answer, because you won't be able to make correct bracket sequence later anyway.2) if s[i]=='(' then by changing it to ')' balance will decrease by 2 from [i;n-1] in bal[]. So you need to check that minimum in bal[] from i to n-1 is >=2 and bal[n-1]==2. If it is true then increment answer variable.3) if s[i]==')' then same logic. Just check if min>=-2 and bal[n-1]==-2.To find minimum on interval you can just use multiset. See my solution
•  » » » 3 weeks ago, # ^ |   0 Your solution is pretty clear and easy to understand..Thank you. I understood the logic behind the problem.
•  » » » 3 weeks ago, # ^ |   0 why we have to check min???