We have an educational round on 28th already :)

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

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.

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.

I hope it is not like you

I think so

I hope so :) Good luck!

Go to standings then click on any + sign

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

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

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.

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.

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.

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)

jg

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

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.

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.

1. You just need to find a possible permutation of first 3 elements. lets say, p1, p2 and p3.

2. 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.net/contest/1095/submission/47575058

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.

you can refer to MST Algorithm like Prim and Kruskal

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 fixed k (ignoring any other restriction) is obtained by first adding the smallest a_i from each component, and then adding the smallest a_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.

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.

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.

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.

Should I report it to someone?

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.

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

MZuenni on fire!

May be for this reason : Link

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

You should be printing 5 numbers and you only printed 2

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.

If an offer with cost w is included, the cost of building an edge connecting x and y can be either a_x + a_y 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).

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 a_x + a_y.

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.

vovuh

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

vovuh

chong

Nope, it crashes in your while

while((k-cnt) != 0){ ...

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.

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

See here.

Please read the description carefully!

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

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