It will be added there after today's contest

Indian coders make great problems in codechef :)

The registrations have been postponed to account for today's contest rating changes. This glitch will no longer be there.

Here in my college, if you don't have 75% attendance, they don't let you sit in for exams directly :( .Dedicating your time to do what you like is really good thing to follow.

Looking forward to a good problem set :)

you turn green again. that's very sad to solved only one problem.

I think, problem setting is not about any color, problem setting is an art. Keep trying...!!! ... Never lose your hope.

I think the problem setter is happy when there are many hacks :v Strong pretests will make the number of hack decreases. :(

Take sum of abs(a(i)) for all i as sum. Now ans=max(ans,sum-abs(a(i))-abs(a(i-1))+abs(a(i)-a(i-1))

Same here. please help

if all negative abs(sum) — 2 * max

if all postive abs(sum) — 2 * min

else abs(sum)

Here's a hint: You can pick any subset and multiply it by -1 (except subset of size 0 and n)

For n > 1, you can show that you can choose the order of the eatings in such a way that the final number is  ± a₁ ± a₂... ± a_n for any combination of signs, in such a way that at least one of the  ±  is  +  and at least one of the  ±  is  - . Then, if you order a, the answer will be simply

.

let sum store sum of abs(a[i])

when all a[i] > 0, ans is sum — 2*min_element

when all a[i] < 0 ans is sum + 2*max_element

when there exists a[i] of each type ans is sum

You can show that if every number has the same sign, you can get the sum of their absolute values as a result except for one of them that you have to exclude. In this case you can choose to exclude the one with minimum absolute value and the result ends up being the sum of the absolute value of all the elements minus two times the one with the minimum absolute value (two times because you've already counted it in once).

If there are positive and negative numbers it's similar, but this time you can avoid having to exclude anything, so the result ends up being the sum of the absolute values of all the elements.

Tried a linear-dp, only to realize by now it was pure mathematical observations. Got things now :<

Thanks anyway guys. sdssudhu pleb Ahmed- Saat fugazi juanigsrz

ddolgu14 I guess you'll have all what you need.

you just need to have some a[i]<=0 and a[j]>=0 then the answer is the abs sum of all numbers.

you just need to have some a[i]<=0 and a[j]>=0 then the answer is the abs sum of all numbers.

UPD: Sorry for repeated comment, I am having the worst Internet connection now :(

Hint: If we denote colours by nodes and blocks by edges, then all blocks of a connected component can be taken into final sequence if no. of nodes with odd count is 0 or 2 in that connected component.

Let us count occurences of colours. Now, no. of colours having odd count can be 0,2 or 4 obviously. Now we can put two odd colours at the ends of the sequence. So, for odd=0 or odd=2, maximum of sum over all connected components can be considered(like for blocks(ignoring value)- (1-2),(2-3),(1-3),(4-4) connected components are- (1,2,3),(4)). Now for odd = 4 we will need to remove at least one of blocks. So, we can find answer by taking maximum of above thing over all 1-block removals which make odd=2. Sorry, if I am unclear.42588216

Alternative solution (harder to implement but was easier to come up with for me): While there are 3 or more edges between two colors, we can remove two most valuable edges and note that if any of these vertices is visited than we need to add the value of all corresponding removed edges. Now there are no more than 2 (edges per color-pair) * 6 (color-pairs) = 12 edges. The graph became small enough to bruteforce all possible edge-paths: After making 11 steps there will be only 1 edge left so we won't have a choice at that point. First 11 times there will be no more than 3 (number of other colors) edges to choose from. This gives an upper bound of 3^11 = 177147 node traversals. We will need to try starting at all four colors so the final number is 4 * 3^11 = 708588. In practise it works surprisingly fast: 31ms. If you for some reason would like to look at my solution: https://codeforces.com/contest/1038/submission/42595983

An array with size 1. Such as 1 5

All numbers negative.

View the blocks as edges. Conditions for the edges: 1. all edges are connected together 2. the edges can form an euler path

Is it your second account — eyg? Name and name of the school match.

n = 1

For n=1, n=2, output is "No".
For n>2
Break into 2 sets, one containing odd numbers, other containing even numbers.
Or
Break into 2 sets, one containing 'n', other containing remaining numbers.

I think there are many solutions, mine was adding up all the odd numbers if they were an even amount (so the gdc would be two), or partitioning the elements into [1,N/2] and [N/2+1,N] otherwise.

if n < 3, answer is no else, one set is n, the other set is 1, 2, 3, ..., n-1

this is because the sum of the second set is (n-1)*(n)/2, so if n is odd, they have a common factor n, and if n is even, they have common factor n/2, and as n > 2, n/2 > 1

so the answer will be 50000 * 10⁶ = overflow with int ... hmm it seems to be valid due to the input constraints !

The hack log tells it all:

Validator 'val_b.exe' returns exit code 3 [FAIL Expected EOLN (stdin, line 3)]

Don't forget to put a new line character in the end of test.

Morale power, bro — such things will take time to be perfect. Better luck next time ;)

At least you were so close to it. I myself couldn't come up with a proper idea during contest time.

The ASCII code for 'A' is 65 not 64.

EDIT: Ignore that, maybe it's because you didn't set the values in the a[ ] array to 0 ?

int ans = 30;

Your initial value for ans should be at least equal to n (since that variable shows the minimum frequency of any letter, and such could rise up to n in certain circumstances).

I know how to solve E in O(n^2). But it can be done with O(n) as well.

If we have one component, we can take all edges, if we can make there Eulerian cycle or Eulerian path. And it is enough to delete one edge or none at all to get AC.

Then pick one edge and then run dfs.

yesterday was fine this one was really bad

It can be done with simple dfs.

That's my solution

https://ideone.com/dZbEb2

https://textb.org/r/n4oyl3a5x5/

In terms of score difference it doesn't really matter to take your number or to erase your opponents' number. So you always want to deal with biggest number of both lists: if it yours you take it, if it opponent's you erase it from his list

Its based on this optimal strategy from a player:

1. If I don't have any element, I would delete the largest element from the list of the other player.

2. Else If the other player doesn't have any elements, I would simply add the largest element in my list to my sum.

3. Else if the largest element that I have has a greater value than the largest element of my opponent, I would add my element to my sum. Since if I go for deleting the largest element in my opponent's list, he would in turn delete mine and I will have to incur a greater loss. However, if I add my current largest element to my sum. Either my opponent will delete some no. in my list that has a lesser value or he will add to his own list an element that has a value <= the value of my element. In case my new difference would be >= my previous difference.

4. Similarly, if other player has a larger element than the largest element I have, I would go for deleting the element in his list.

All this can be simulated by using 2 vectors, 1 for each player and sorting both the vectors and accessing only the last elements of both at any instant.

Disappointing that you value the already invented algorithms over logical thinking!

i spent some time try to proof that the B will always have a solution(for n>2 ), my roommate just submitted the solution immediately. both got AC :D

I have actually verified my B. If you a take any divisor v of n(n+1)/2 such that 2 <= v <= sqrt(n(n+1)/2), you can create the two sets such that one of them contains this divisor and the other contains the rest of numbers. Because if v|a and v|b, therefore v|(a+b).

In B I have a nice proof:

The sum of all values is n*(n+1)/2, you want to find a single element that divides the sum and is equal or smaller than n. This number can be (n+1)/2 rounded down clearly.

It is possible to prove D too (even thogh I failed systest for mistaking a variable haha)

Superb contest. And I agree with this. Literally, when I was solving D. I found correct soln. Accounted for all corner case. And was just praying to get AC. At last, I got it. Although for B,C I made some proof. And then submitted. For all questions, I found correct soln. Then waited for 3-4 to 10-15 min. To verify it. And take care of corner test cases.
Really enjoyed Solving Tasks. Thanks Ashishgup.
Looking forward for the editorials.

This testcase has been added to practice. Thank you!

Oh they become disconnected when removing the edge with the minimum value.

Ok, we will do it.