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 |

5 | gamezovladislav | 11:-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 |

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.

We have an educational round on 28th already :)

Yeah, so the questions could have been used for an educational contest someday after good bye-2018.

Awesome Anyway I love Live Contests so much

Great Job for your efforts on Writing and testing the problems

Happy New Year for all

Just first div 3 contest was the real div 3. (in problem difficulty)

If the difficulty trend in Div3 rounds keeps going, we might have to expect IOI level problems.

Hey, it's IOI jury's problem that their task was easy enough to fit into div3 contest!

Eden Hazard the best player in the world right now

Div 3 is easy for me, give me div 4

But div 1 > div 2 > div 3

is it contributed?

Good luck!

is A FFT?

hope this round results in a higher rating to all my friends ... Good luck to all

Why I see the "<copy-pasted-part>" again...Could you pay more attention when writing an announcement?

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.

I agree with you,but I think a good announcement is also important.

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.

****_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_****

Just first div 3 contest was the real div 3. (in problem difficulty)

I hope it is not like the previous contest

I hope it is not like you

I will do my best and I want to get gray

I think so

Good luck folks!

Image

Good luck to the

serverThanks vovuh for div 3 again. I like the higher frequency for div 3 these days.

Hope it's a great contest.

I hope so :) Good luck!

How to hack a solution.

Go to standings then click on any + sign

Got 2 WA using pow() in C++ :( in problem C.

Try to use byte shifts. For example (1 << 5) is equal to pow(2, 5). This is only for powers of number 2.

Yes, I had corrected it in the last 2 minutes :)

you can use int(pow(2,i)), but bit shift works fine too

How is there 100% systests already? O_o

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

Please help me with Problem E. Any hints?

Yeah you can use a segment tree for it. The leafs should store the count to open and closed brackets.

Thank you :)

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.

Thank you!

what about this "))((" it will be equal to zero however it is not valid??

thanks for an actual Div 3 round!!! on a side note, does anyhow know how to D? I struggled at it quite a bit.

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.

that's the problem I'm facing — how do you know if the edges are in the wrong direction?

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.

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?

i tried topological sort but it gave me WA on test 3

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.

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.

Damn, used the very same approach. Didn't handle the case of 3 properly.

https://codeforces.com/contest/1095/submission/47583430

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]], ...

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 like

Case-1 : a->b->c Case-2 : a->c->b

To 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.

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)

Problem E was almost the same as BRCKTS problem from SPOJ.

jg

Easy round, I solved all problems

You mean you consistently got WA on testcase 2 on all problems?

Does hacking help my rating?

Yes, it helps your rating

You don't get points for hacking in Div. 3. It helps you indirectly by making you place higher in the standings.

!(my last comment) = I love div3 rounds :P

anyway how to solve D it looked like a graph problem to me

There is no need for graph. Using 1 as the first number, find the first 3 numbers with brute force. Then its easy implementation.

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....pn

For 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

damn they scared me with that circle

Hi Can you please point out why my solution got WA on 285th Kid https://codeforces.com/contest/1095/submission/47585800.

Your code's logic seems incorrect. Please try this simple input:

Output should be (a cyclic shift of):

`1 5 4 3 2`

But your code is printing:

`1 5 4 2 3`

Can I get a hint for problem C:Powers of 2

Check the binary representation of the input

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.Can you elaborate further by taking an example?

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)

i cannot understand why u use k-=mn; then func( x, min(k+1,x) ) in your code can you eloborate please

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.

Wonder why Problem F if there are Multiple index have smallest cost pick any of them to build edge to is ok

you can refer to MST Algorithm like Prim and Kruskal

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

you can consider why MST Algorithms like Prim and Kruskal do not care about that

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

a_{i1}+a_{i2}+ ... +a_{ik}. 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 fixedk(ignoring any other restriction) is obtained by first adding the smallesta_{i}from each component, and then adding the smallesta_{i}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.Thanks. I think i got it.

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)

It is MST, with an extra idea. It turns out the only edges with costs

a_{x}+a_{y}that we need to consider are the ones that involve the vertex with minimum cost.Thanks! I'll go study more through it :)

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.

Any one can help me with problem E! I have no idea how can i solve the problem!

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 expected

Can someone explain what is happening Submission

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.

But if I compile the same code elsewhere I'm getting a correct answer as per the jury.

Can you specify about your machine or where you compiled?

I mean, some links to online compiler or you machine's OS, editor, complier

Online compiler Jdoodle

Should I report it to someone?

vovuh Please look into this.

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?

I can, that's because of

`abm`

in`target`

.https://codeforces.com/blog/entry/59457?#comment-431178

Thanks, that's quite interesting!

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 3

is this 1 4 2 3 5 also a valid answer?

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 4

5 3 2 4 1

3 2 4 1 5

2 4 1 5 3

4 1 5 3 2

These are the only valid answers for first example.

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?

Problem D is ambiguous, I cannot understand what he want. can anyone help me please. thanks in advance.

There's a directed circle(a premutation p), giving the two vertexes behind every vertex, you should print a valid order.

Ycrpro1 thanks bro, i got Acc

Why all Java solutions on B are getting hacked? Although they all seem correct.

MZuenni on fire!

Java's DualPivotQuicksort used in Arrays.sort is deterministic and therefore in O(n^2) they all get timelimit by that...

Good Job! Even though I was one of the victim, felt good to learn these intricate things.Cheers!

But isn't time complexity of Arrays.sort() changed to O(nlogn) for worst case too in Java 8?

no.

https://docs.oracle.com/javase/8/docs/api/ Implementation note: The sorting algorithm is a Dual-Pivot Quicksort[...]

May be for this reason : Link

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...

Why did my solution for F Link failed?? Update:Solved

your variable mst_cost is int.... it should be long long

Yup,that was the problem, just got an AC, Thanks acIN1go

for problem D, why WA??? Judge says wrong output format Unexpected end of file — int32 expected

link to my code is Your text to link here... please someone check it...

You should be printing 5 numbers and you only printed 2

yes, that's the problem. IDE prints all the five values but, judge shows only two. I'm not getting the reason.

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 link

2) About your code, I got it working removing

`adj = new list<int>[n + 2];`

and`vis = new int[n + 2];`

but instead delcaring adj and vis like this`list<int> 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)

A lot of people got hacked on Problem B, including myself. Does anybody know what the issue could have been?

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.

Thanks! I'll remember that for future reference.

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.

If an offer with cost

wis included, the cost of building an edge connectingxandycan be eithera_{x}+a_{y}orw, 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).For two vertices

xandy, there may be some special offers. You may potentially use one of these offers during the construction if you want to connectxtoy. However, you can connectxtoywithout using any of these offers, as well. In that case, the cost of connectingxandyis given bya_{x}+a_{y}.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/47569625

Later 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?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.Oh, now it makes sense. Thanks for the clarification :)

(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.

declare the round unrated for java users whose B was hacked!

vovuh

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...

but that works perfectly well with c++, as it is faster

they gave the java users only 1k ms they should have given 2k ms

For java we are allowed 2000 ms for a problem in which the limit is 1000ms but here we got a tle at 1000ms

submission here: http://codeforces.com/contest/1095/submission/47602564

please rectify this

vovuh

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!

So according to you what could be an alternative to Arrays.sort() for getting O(nlogn)?

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.

hey i read your blog. Thanks for the information, I got what you were trying to say.

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.

chong

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. Isn`t 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

Nope, it crashes in your while

yes, but that`s because 'sz' was evaluated as 2, if it would have been evaluated as 3, I would have got "YES 8"

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.

yep, ceil would have done it.

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.

When will the ratings change?

I love Vovuh's Problem set...He is making Div3 great

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?

They are same on codeforces, because they are same in C++. (long and long long are different).

See here.

On my machine they are different! :(

This is so unfair :|

Even on GeeksforGeeks they are different!

https://ide.geeksforgeeks.org/gL0gqCYQVs

Could someone help me with problem E? I think I have not understood what is a

regularsequence. 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 notregularones?Please read the description carefully!

What is the solution to Problem B? I am getting WA on test case 6.

There is 3 cases. The first one is to take one element that is not minimum nor maximum: The

instabilitydoesn't change. The second case is to take one element that is maximum: Theinstabilitywill bethe maximum of the new array minus the minimum of the array. The third one is to take one element that is minimum: Theinstabilitywill bethe maximum of the array minus the minimum of the new array. So the answer is min(second case,third case).Problem D. What's wrong with this approach? Just dfs from 1 untill I get all the unexplored nodes. can anyone explain??

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/IDE

Here's my code. https://ideone.com/qVAsiL

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.

Is there any editorial posted for this Div3 Round?

Can we have the editorials?

How to approach problem E?

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] :)

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

Your solution is pretty clear and easy to understand..Thank you. I understood the logic behind the problem.

why we have to check min???