Hi everyone!

It has been almost 2 years since I joined Codeforces, and it has been a great journey as a contestant. I now try to take a shot at problem-setting with my friend Mahir83.

With that said, I bring to your attention my new Codeforces Round #508 (Div. 2) that will take place on Sep/06/2018 18:35 (Moscow time). If your rating is less than 2100, this round will be rated for you; otherwise, you can participate out of competition.

I would like to thank Mahir83 for his help with preparing problems, _kun_ & 300iq for coordinating my round and Um_nik, senek_k, gritukan, Vovuh & BledDest for testing my problems. I would also like to thank MikeMirzayanov for Codeforces and Polygon platforms.

You will be given 6 problems and 2 hours to solve them. Scoring distribution will be announced later.

Good luck!

**UPD:** Scoring Distribution: 500-1000-1500-1750-2250-2750

**UPD2:** Editorial

Please put this blog into HOME.

It will be added there after today's contest

Wow,an indian as a problem setter without any fest of their institution :))

Indian coders make great problems in codechef :)

(Except when there was a "notorious coincidence"...)

this will be amazing

Sadly, another midnight contest for chinese participants.

Codeforces says:

`You are registering "out of competition", reason: rating should be between 0 and 1,899 in order to register for the contest.`

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

ashishgup i hope you saw round 507

All the best Ashishgup!

two consecutive contest in two days! it is wonderfull. (the day after tomorrow will be educational contest so three consecutive contest.) thank you codeforces .

I am very excited about the contest by Ashishgup.

Because of this blog on Quora.

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

Same here in my college :p

same in my college.

not same in my university

Numb MotherFucker!!!

How to approach D?

i am to much happy about the contest due to problem setter is my neighbor

congrats Ashishgup

Indian problem setter on Codeforces. This seems to be the start of an era.

This is sure going to be fun! Looking forward to more such rounds!

I hope, we will see some interesting problems in this round.

And, Ashishgup congratulations for your first contest as problemsetter...

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

This was very sad for me because I lost my internet connection when I was about to submit the solution of problem B.

I joined Codeforces for over 2 years and even not enough color to be a problem setter...

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

Thank you, man. We're same color :D

Hope for strong pretests. X3

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

he's also not gonna be happy when a lot of people are upset over the contest

While many people are upset, many person also have extra points :)

And the person, who are hacked, will have an experience never have same bug like that. :D

Hope to see a great blend of classic problems involving (dp,algo,ds,numtheory etc..)in a single contest:D

20 min to go !! :D

Best of luck Ashishgup for your first contest as problemsetter. Looking forward to a really nice set of problems. :)

strong pretest

CF so slow can't load other people submissions

feel stupid enough to ask this type of questions again, yet I have no choiceHow to solve D? :(

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)

Except that for all negative the answer should be abs(sum) + 2 * max — I hacked two solutions with this mistake.

true i had the same mistake then resubmitted before 5 min of the end

What was the hack case for this ??

2

-4 -5

I got stuck for some time because i forgot the base case when n = 1, then the answer is the no. itself.

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_{1}±a_{2}... ±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 ordera, 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 pshishod2645 juaniisuar

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

I also tried linear dp and got some 5 — 6 WA because of it.

That's right. The solution made me realize that I misunderstood the problem. I thought I had to do a[i]-a[i+1] to combine the i and i+1 slime.

Thanks for the n = 1 pretest in problem D! :D

How to solve

Dplease ?you just need to have some

`a[i]<=0`

and`a[j]>=0`

then the answer is the`abs`

sum of all numbers.what ! T_T

hmm , any proof ?

Make negative numbers from the positive numbers by subtracting the positives from the negatives, leaving exactly one positive number. Then use this positive number to make all the negative numbers of positive contribution by subtracting them from the positive number.

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

How to solve problem E? >_<

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

Thanks you commented my question, so I need to delete some edges until no. of those nodes with odd count less or equal to 2?

Yes, deleting one edge which is not self loop would be enough always.

But why no. of those nodes with odd count only 0.2 or 4, It can be constructed more right?

There are 4 colours, each time we add a block(edge) parity of 2 of them changes. So, there can be only 0,2 or 4 with odd count.

Got it very appreciate, I misunderstood your meaning before >_<

I agree with you.

That's like my solution here.

http://codeforces.com/blog/entry/61659?#comment-456568

Why do you need all 1-block removals. We can just remove the lowest value edge that has different colors on the two sides. Right?

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

Maybe it's first time in my life when it isn't nessacary to know anything (except sort()) to solve Div2 A, B, C, D... But... somehow they were very interesting!

what is pretest 16 problem D

An array with size 1. Such as 1 5

What was the hack for D?

All numbers negative.

Any "Hint" for problem E ?

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

E was an interesting problem... but it took me a bit too long to implement. Is there a simpler solution than a dp with n*2^4*2^10 states?

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

What are you talking about? I don't break any rules. I'm a good boi. Idk why our names are so similar though. I think that it is just a notorious coincidence.

I noticed that you've just changed the name but Google still remembers your old name — https://webcache.googleusercontent.com/search?q=cache:https://codeforces.com/profile/eggmath.

Well, it's sad that such a great company like Google is so slow at updating. Maybe some competitive programmers here can write some faster algorithms for updating.

Congrats for an amazing contest!

What is case 15 in problem D?

n = 1

what is testcase 16

same n = 1 but a[0] < 0

shit

Can E be done with max cost max flow?

How to solve B?

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.

How about n = 5 and n = 6?

n=5 ==> {1,3,5} and {2,4}

n=6 ==> {1,3,5} and {2,4,6}

???

You can test that with code like this:

Test codeI did that during the contest to be sure that it will be AC.

n=6 means Gcd=3

I solved it with getting n*(n+1)/2 first devisor

Still can's understand how 1 + 3 + 5 = 9 can be even. Maybe 'even' means something else in English?

My bad on saying the sum would be even. But it could be easily proved that partitioning odd and even numbers into 2 different sets, the sum of both sets will always have a common divisor k, where k=ceil(n/2).

eg n=5,n=6 ==> k=3 is a divisor for both sets.

Oh, thank you! In fact, I didn't know that it can be easily proved considering pairs (k-i, k+i). I was using gcd() ans sum formulas...

The solution given by Mr_Maverick works because:

Sum of first n numbers : n * (n+1) /2

Sum of first n even numbers : n(n+1) ....(1)

Sum of first n odd numbers : n^2 ....(2)

Now gcd of (1) and (2) would be >= n ....

That is why it is safe to partition like this..

But they said first n numbers, and for n = 2, the only possible numbers are 1 and 2. gcd(1,2) can never be greater than 1

Hence "No" for n=2

I see. I thought you were saying for n = 2 we can obtain a solution. I was taking the rest of your explanation as though you were talking for n>1

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.

Okay, but still, I don't understand why it works. Is there any proof this will work?

I did it this way for n>2, there can be two cases: 1. n is even: answer would be two subset having even and odd numbers respectively (as there would be even number of odd elements). 2. or n is odd: the answer would be one subset having middle element and other having remaining elements. This works as sum of digits equidistant from center would be equal to double of middle element (hence gcd=middle element).

Ohh, yes, nice solution :D

Let's n = 2d + 1.

a = 1 + 2 + ... + d = d(d + 1)/2.

b = (d + 1) + ... + n = (2d + 1)(2d + 2)/2 — a = (2d + 1)(d + 1) — a.

gcd(a, b) = gcd(d(d + 1) / 2, (2d + 1)(d + 1)).

If d is even then gcd(a, b) = d + 1. Otherwise, gcd(a, b) = (d + 1) / 2.

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

Nice solution. Given solution of sample test cases made me think in a different way :/

In problem C

100000

1000000 1000000 1000000 . . .

1 1 1 . . .

Why this was a wrong/invalid hack? Link

so the answer will be 50000 * 10

^{6}= overflow withint... hmm it seems to be valid due to the input constraints !Hmm,

I tried this as hack to get TLE/WA but they rejected it saying invalid hack input. I messaged @Ashishgup also, but he seems to be busy in wrapping up the contest.

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.

Why does it expect newline character at the end of file? Yes, this was my first attempt to hack through the generator. In fact i specially handled cases to not print any additional space/endl.

I just realised that code which I was trying to hack got AC? Why we did not have this test case?

Can you give the link of solution please? Because the test you made for hack was alredy in pretest.

https://codeforces.com/contest/1038/submission/42569122

This solution prints sa-sb, and both sa and sb are declared as int. I did not see that int has been defined as long long on the top.

Nice problems by Ashishgup.

E is bitmask ,right?

I need 35 to go back to DIV. 1, predictor says if all my solutions are accepted I will get +36 :D

Why God ??

I did all things right but then shitted while typing in Div2-D. I calculated difference and max_difference correctly and then instead of using max_difference for calculation used difference instead :(

Submission: https://codeforces.com/contest/1038/submission/42588288 JUST LAST MINUTE THINGS !!

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.

Hi, I have a doubt regarding problem A. My code gives the required output on other IDEs as well as on my system. But on codeforces it is showing wrong verdict for pretest 1. Can anyone help me ? My solution link is : https://codeforces.com/contest/1038/submission/42582475

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 ?

That '(int)ch-64' is just for hashing it doesn't affect anything just the indexing. Afterwards he has used indexing starting with 1 which is fine. His code looks fine.

Solved D, but was defeated by pretest 3 on A? What's going on there?

Please, SEND HELP!

`int ans = 30;`

Your initial value for

ansshould be at least equal ton(since that variable shows the minimum frequency of any letter, and such could rise up tonin certain circumstances).Unless

ans < nit's initial value does not affect anything within my code.Take this case for example:

n= 108,k= 3,s= "ABC" * 36 (i.e. the stringsis the concatenation of 36 consecutive substrings "ABC").Obviously you'd find that the minimum frequency is 36 (all 3 letters have the same frequency).

However, since you initialized

ans= 30, the value will be kept at 30, and thus, the output will be 90 (while it should be 108).Keep in mind that

nis at most 10^{5}.Oh, indeed.

Thank you very much for pointing out!

how to solve E?

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.

Why deleting one edge is enought?

When we have component of 3 or less vertices, we always can make Eulerian cycle or path.

If we have 4 vertices, then parity of edges from vertices can be (odd, odd, even, even), (odd, odd, odd, odd), (even, even, even, even). First and second case have Eulerian cycle or path.

When we have case with all odd parity, when we delete ane edge, we will get case (odd, odd, even, even) and this case have Eulerian cycle or path.

Is it just me or for the past 2 weeks during contests CF is taking too much time to load??? It's like...it's fine right now and 5 minutes later, it's not loading. And then it suddenly loads. Anyone?

yesterday was fine this one was really bad

Can someone share their library code for min cost max flow with negative edges and negative cycles which I believe is implemented using Bellman Ford irrespective of whether today's E has some other solution.

Thanks!!

It can be done with simple dfs.

I did not ask for solution. I have mentioned irrespective reason just to avoid answers being put here instead of my original purpose :(

Oh, sorry

That's my solution

https://ideone.com/dZbEb2

Seems pretty similar to 42583527. Did you forget to re-login?:)

You are right!

I am NSArray, and yes, you are right.

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

I used to solve D several minites after the time is over :)

One of the best codeforces contests ever!!!

Intuition for Question C?

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:

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

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

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.

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.

The strong pretests. I like it :)

Thanks for the nice contest.

Well balanced contest with interesting problem set. Clear and concise statements. Good job Ashishgup :)

The pretests were great, but IMHO, the contest was a bit on non-algorithmic side. A bit disappointed with this.

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

if every problem is just logical thinking then you will actually not learn much.. applying multiple "already invented" algorithms or modifications of them is what problems should aim on in my opinion.. I appreciate ashishgup for the problems as it is not easy to come up with original problems but I hope next time he will amaze us even more.. all the best!!

To be fair, the tag-wise distribution of contests was:

I prefer logical questions over coding-heavy questions, but I'll try to keep it in mind.

Yeah. When I solved C, I pretty much thought of what lines you were trying to make the contest, so I was trying hard to find some DP solution for D, and it turned out to be simple logic based.

@Ashishgup , anyway its good to see an Indian problem setter avoiding involvement of heavy DSA for E and F problems. Looking forward to solving some more great problems set by you :) Best of Luck for future contest! Its good to see that you took my comment in a positive spirit.

@ushagal0000 A problem can also involve logical thinking with so "already invented" algorithms. Infact, if just knowing "already invented" algorithms could help solve all questions, then the majority of the world would be LGM. You always need a logical thinking even if the problem involves usage of "already invented" algorithm.

Nice tasks + nice pretests = super contest. Thanks)

I liked problem E.

But I feel that problems B, C, D need some luck. You need to make a guess on what can be the solution then to verify it or maybe just submit it.

i spent some time try to proof that the

Bwill always have a solution(for n>2 ), my roommate just submitted the solution immediately. both got AC:DWhen I noticed my error in B was loop limit I fixed it and quickly submitted, but forgot to fix my prime range according to it and got runtime error. Being stingy about system resources not always good:P

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.

It seems that tests for E might be incomplete (or I misunderstood something); consider this testcase:

6

1 10 1

1 2 2

2 10 3

2 20 3

3 1 4

4 10 4

My solution, which passes tests, prints 52, but if I'm not wrong, the correct answer should be 43, like this:

[1|10|1] [1|2|2] [2|20|3] [3|1|4] [4|10|4]

Ashishgup, please take a look at this.

This testcase has been added to practice. Thank you!

Just want to say that you adding this test to practice showed that my solution (that I just coded AFER the contest, so it does not matter much) is incorrect, thanks!

And thanks antguz

I actually noticed my first solution was wrong before submitting, but did it anyway, it was pretty surprising to see AC. Actually, a few submissions from the top of standings fail on that case too...

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

300iq _kun_ please delete my one of the exactly same codes submitted during the contest for problem C .

https://codeforces.com/contest/1038/submission/42577005 and https://codeforces.com/contest/1038/submission/42576866

Ok, we will do it.

Strong pretests? Wow, it darn good

An Enjoyable Contest by an Indian Ashishgup. I am Happy to be back in track after many bad days

rating changes !!

i get +101

Thanks for the great contest :)

Hi, Are

longandlong longnot same in codeforces GNU G++17 7.3.0 compiler?long is 32 bits, long long is 64 bits.

This is valid for G++11/14/17 also.

Why are the max values of both same then?

I ran this using custom invocation on GNU G++17 7.3.0 and didn't give the same value for both types.

Yes, that's my doubt. All other ide's at https://wandbox.org https://ide.geeksforgeeks.org https://www.codechef.com/ide and my macbook gave the ouput as 9223372036854775807 for both. I was unable to figure out the bug in 3rd question due to this. Why are they different here and not elsewhere?

Long is the same as int in c++

I believe that this depends heavily on the compiler. The standard for c++ guarantees that

`int`

has at least 16 bits (i.e. it goes from 2^{15}to 2^{15}- 1),`long`

has at least 32 bits (from - 2^{31}to 2^{31}- 1) and`long long`

has at least 64 bits (from - 2^{63}to 2^{63}- 1). Nevertheless, the individual compiler can assign more bits to a particular type.Thanks for the great contest)

Can anyone explain how to solve D with a proof? thanks in advance ....

First of all, notice that the maximum value that you may get is sum(abs(a[i])) for 1<=i<=n. If the array consists of a combination of positive (>=0) and negative (<0) values, if you have v positive values, then v-1 of them can be subtracted from the negative values, and then subtract any negative value from the remaining positive value. By this, you get sum(abs(a[i]))

If the array consists of only positive or only negative values, in this case, notice that if you subtracted any value from the other (v1-v2), min(abs(v1), abs(v2)) is better to be v1. For example, if the two values are (where all values are positive) 5,3; 5-3=2, but 3-5=-2. The difference here is that -2 can be used with the rest of positive values to get sum(abs(aa[i])) (assume aa is a after removing 3,5 and inserting -2). Also abs(v1) needs to be as minimum as possible, because in the subtraction process, abs(v1) is lost twice from sum(abs(a[i])) (in 3-5=-2, abs(3)+abs(5)-abs(2)=6=2*3). So the answer is sum(abs(a[i]))-2*min(abs(a[i])).

Thank you...

Thank you for a very nice contest

It seems that the test data for E is weak.

Some contestants just sum up all weights in a connected component, then check whether there are four odd vertices, and if so, subtract the minimum weight of a non-loop edge. Such solution could survive System Test. However, this is incorrect, for the graph may be unconnected after that edge removed.

Anyway, this is not a very common situation in Codeforces! lol

I am sorry for the weak test data. We tried to add cases of every type and also some manual cases, but failed to break a few incorrect submissions (due to different heuristics being used by different participants). One case was added after system test, and if you think that incorrect solutions still get AC and you have any breaking case/code link, do tell. We will add the case to practice for further submissions. (We cannot rejudge the contest codes)

I agree that it is rather difficult to generate strong and complete test data. Anyway, thanks for your hard work.

There are many ways to solve Problem B, for example: if n>2 set 1: (n+1)/2； set 2: others;

because (int)((n+1)/2) can divide (1+n)*n/2.

Can someone check the code for me?

http://codeforces.com/contest/1038/submission/42591350

Getting an error in Problem C in test case 58

you should add ' and i<n' at 'if(mx==arr1[i]) ' also 'and j<n' at 'if(mx==arr1[j]) '

My solution got accepted by making the changes you recommended.

But, how does it make a difference? I didn't understand.

i can't quite tell but your array can exceed the size limit and may have strange results

If the array size limit exceeds, the strange results won't match the mx variable

there are coincidences in the world

how to solve div2a please? i solved only div2d because of too tricky problems not fair!!

I noticed that winner (SBHeltion) has cheated, you can totally understand that these two code written by two different people :

A 42559251 B 42560979 C 42566710 D 42573485 E 42575080 F 42582709

In A B C D he used spaces in for and +=1 instead of ++ but in problem E he used ++ and without spaces.

And if you look defines A-B-C-D have , but E-F have not... suddenly he use N define instead of maxn