Codeforces Round #508 (Div. 2)

6 years ago, # ^ |

+41

It will be added there after today's contest

→ Reply

ILoveDoraemon

6 years ago, # |

+183

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

→ Reply

vjvjain0

6 years ago, # ^ |

-17

Indian coders make great problems in codechef :)

→ Reply

aryaman

6 years ago, # ^ |

+143

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

→ Reply

6 years ago, # |

this will be amazing

→ Reply

Medusa

6 years ago, # |

-17

Sadly, another midnight contest for chinese participants.

→ Reply

mehrunesartem

6 years ago, # |

+19

If your rating is less than 2100, this round will be rated for you.

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

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+38

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

→ Reply

6 years ago, # |

+38

Ashishgup i hope you saw round 507

→ Reply

Siriuslight

6 years ago, # |

+16

All the best Ashishgup!

→ Reply

Amoo_Safar

6 years ago, # |

+29

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

→ Reply

starboy_jb

6 years ago, # |

← Rev. 2 →

+62

I am very excited about the contest by Ashishgup.

Because of this blog on Quora.

→ Reply

forgotter

6 years ago, # ^ |

+43

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

→ Reply

harshit15

6 years ago, # ^ |

-6

Same here in my college :p

→ Reply

starboy_jb

6 years ago, # ^ |

same in my college.

→ Reply

rotavirus

6 years ago, # ^ |

-24

not same in my university

→ Reply

I_Love_Nicki_Minaj

6 years ago, # ^ |

-49

Numb MotherFucker!!!

→ Reply

abhist

6 years ago, # |

← Rev. 7 →

+17

How to approach D?

→ Reply

al_____

6 years ago, # |

congrats Ashishgup

→ Reply

vntshh

6 years ago, # |

← Rev. 2 →

+79

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!

→ Reply

Assaduzzaman_Sohan

6 years ago, # |

+18

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

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

→ Reply

caojielong

6 years ago, # ^ |

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

→ Reply

Assaduzzaman_Sohan

6 years ago, # ^ |

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

→ Reply

6 years ago, # |

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

→ Reply

Assaduzzaman_Sohan

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # ^ |

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

→ Reply

BrokenDummy

6 years ago, # |

+30

Hope for strong pretests. X3

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

Murk

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

MonsterInMe

6 years ago, # |

+19

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

→ Reply

arjitkansal

6 years ago, # |

+20

20 min to go !! :D

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

→ Reply

iamSourav

6 years ago, # |

← Rev. 3 →

-11

strong pretest

→ Reply

6 years ago, # |

CF so slow can't load other people submissions

→ Reply

6 years ago, # |

← Rev. 2 →

+35

feel stupid enough to ask this type of questions again, yet I have no choice

How to solve D? :(

→ Reply

sdssudhu

6 years ago, # ^ |

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

→ Reply

ddolgu14

6 years ago, # ^ |

← Rev. 2 →

Same here. please help

→ Reply

6 years ago, # ^ |

+14

if all negative abs(sum) — 2 * max

if all postive abs(sum) — 2 * min

else abs(sum)

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

sdssudhu

6 years ago, # ^ |

What was the hack case for this ??

→ Reply

6 years ago, # ^ |

← Rev. 2 →

-4 -5

→ Reply

roll_no_1

6 years ago, # ^ |

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

→ Reply

Ahmed-

6 years ago, # ^ |

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

→ Reply

Saat

6 years ago, # ^ |

+13

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

$\text{[math]}$

→ Reply

fugazi

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

juanigsrz

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+12

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.

→ Reply

sdssudhu

6 years ago, # ^ |

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

→ Reply

ddolgu14

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

spar5h

6 years ago, # |

+39

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

→ Reply

6 years ago, # |

How to solve D please ?

→ Reply

C137

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

what ! T_T

hmm , any proof ?

→ Reply

prakhar17252

6 years ago, # ^ |

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.

→ Reply

C137

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # |

+17

How to solve problem E? >_<

→ Reply

amnesiac_dusk

6 years ago, # ^ |

← Rev. 2 →

+11

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

→ Reply

6 years ago, # ^ |

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?

→ Reply

amnesiac_dusk

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

amnesiac_dusk

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

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

→ Reply

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

6 years ago, # ^ |

I agree with you.

That's like my solution here.

→ Reply

sikander_nsit

6 years ago, # ^ |

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?

→ Reply

nns2009

6 years ago, # ^ |

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://mirror.codeforces.com/contest/1038/submission/42595983

→ Reply

6 years ago, # |

← Rev. 3 →

+23

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!

→ Reply

6 years ago, # |

what is pretest 16 problem D

→ Reply

ashkANOn

6 years ago, # ^ |

An array with size 1. Such as 1 5

→ Reply

hell_hacker

6 years ago, # |

What was the hack for D?

→ Reply

Linkus

6 years ago, # ^ |

All numbers negative.

→ Reply

Ahmed-

6 years ago, # |

Any "Hint" for problem E ?

→ Reply

6 years ago, # ^ |

+26

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

→ Reply

6 years ago, # |

+13

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?

→ Reply

6 years ago, # ^ |

-7

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

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

+21

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

→ Reply

6 years ago, # ^ |

-25

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.

→ Reply

apostoldaniel854

6 years ago, # |

← Rev. 3 →

+35

Congrats for an amazing contest!

→ Reply

Vergara

6 years ago, # |

← Rev. 2 →

What is case 15 in problem D?

→ Reply

vladalos

6 years ago, # ^ |

n = 1

→ Reply

6 years ago, # ^ |

what is testcase 16

→ Reply

vladalos

6 years ago, # ^ |

same n = 1 but a[0] < 0

→ Reply

6 years ago, # ^ |

shit

→ Reply

0101-1001

6 years ago, # |

Can E be done with max cost max flow?

→ Reply

Brankonymous

6 years ago, # |

How to solve B?

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

How about n = 5 and n = 6?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # ^ |

???

→ Reply

aboAdnan

6 years ago, # ^ |

You can test that with code like this:

Test code

int main()
{
    int n = 45001;
    int ev = 2, od = 1;
    for (int i = 3; i < n; i++)
    {
        if (i & 1)
        {
            od += i;
        }
        else
        {
            ev += i;
        }
        if (__gcd(ev, od) == 1)
        {
            return printf("NO"), 0;
        }
    }
    printf("YES");
    return 0;
}

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

→ Reply

Jhin

6 years ago, # ^ |

n=6 means Gcd=3

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

→ Reply

6 years ago, # ^ |

← Rev. 3 →

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

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

Kakashi_150

6 years ago, # ^ |

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

→ Reply

Carlson.Bimbuh

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

Hence "No" for n=2

→ Reply

juanigsrz

6 years ago, # ^ |

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.

→ Reply

Brankonymous

6 years ago, # ^ |

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

→ Reply

no_life_

6 years ago, # ^ |

← Rev. 3 →

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

→ Reply

Brankonymous

6 years ago, # ^ |

Ohh, yes, nice solution :D

→ Reply

6 years ago, # ^ |

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.

→ Reply

davidzhou

6 years ago, # ^ |

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

→ Reply

6 years ago, # |

← Rev. 6 →

In problem C
100000
1000000 1000000 1000000 . . .
1 1 1 . . .

Why this was a wrong/invalid hack? Link

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

greencis

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

-8

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

→ Reply

ashkANOn

6 years ago, # ^ |

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

→ Reply

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

6 years ago, # ^ |

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.

→ Reply

starboy_jb

6 years ago, # |

+54

Nice problems by Ashishgup.

→ Reply

Joxa_P

6 years ago, # |

E is bitmask ,right?

→ Reply

C137

6 years ago, # |

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

→ Reply

agrocks23

6 years ago, # |

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://mirror.codeforces.com/contest/1038/submission/42588288 JUST LAST MINUTE THINGS !!

→ Reply

6 years ago, # ^ |

+13

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.

→ Reply

generic11

6 years ago, # |

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://mirror.codeforces.com/contest/1038/submission/42582475

→ Reply

GLAYS

6 years ago, # ^ |

← Rev. 2 →

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 ?

→ Reply

Denton

6 years ago, # |

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

Please, SEND HELP!

→ Reply

6 years ago, # ^ |

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

→ Reply

Denton

6 years ago, # ^ |

Unless ans < n it's initial value does not affect anything within my code.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Take this case for example:

n = 108, k = 3, s = "ABC" * 36 (i.e. the string s is 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 n is at most 10⁵.

→ Reply

Denton

6 years ago, # ^ |

Oh, indeed.

Thank you very much for pointing out!

→ Reply

Erdenebayar

6 years ago, # |

how to solve E?

→ Reply

6 years ago, # ^ |

← Rev. 3 →

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.

→ Reply

PetroTarnavskyi

6 years ago, # ^ |

Why deleting one edge is enought?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

Nuruhuhuhu

6 years ago, # |

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?

→ Reply

6 years ago, # ^ |

yesterday was fine this one was really bad

→ Reply

teja349

6 years ago, # |

+17

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

→ Reply

6 years ago, # ^ |

-31

It can be done with simple dfs.

→ Reply

teja349

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

+12

Oh, sorry

→ Reply

https://ideone.com/dZbEb2

6 years ago, # ^ |

-27

That's my solution

→ Reply

BohdanPastuschak

6 years ago, # ^ |

+13

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

→ Reply

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

6 years ago, # ^ |

-17

You are right!

→ Reply

47Bananas

6 years ago, # ^ |

-22

I am NSArray, and yes, you are right.

→ Reply

SarvagyaAgarwal

6 years ago, # ^ |

+10

→ Reply

Danylo99

6 years ago, # |

+59

One of the best codeforces contests ever!!!

→ Reply

tourist314159

6 years ago, # |

Intuition for Question C?

→ Reply

renadeen

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

roll_no_1

6 years ago, # ^ |

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.

→ Reply

kkarnauk

6 years ago, # |

+36

The strong pretests. I like it :)

→ Reply

6 years ago, # |

+40

Thanks for the nice contest.

→ Reply

nilesh8757

6 years ago, # |

+69

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

→ Reply

lohit_97

6 years ago, # |

← Rev. 2 →

+22

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

→ Reply

ushagal0000

6 years ago, # ^ |

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

→ Reply

mohitk15

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # ^ |

+26

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

Logic
Constructive Algorithm
Greedy
Logic/DP (both were applicable)
Graph Theory/Bitmasks
Strings/DP

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

→ Reply

lohit_97

6 years ago, # ^ |

+19

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.

→ Reply

wery0

6 years ago, # |

+24

Nice tasks + nice pretests = super contest. Thanks)

→ Reply

Omar_Morsi

6 years ago, # |

+30

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.

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

VLamarca

6 years ago, # ^ |

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)

→ Reply

aryanc403

6 years ago, # ^ |

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.

→ Reply

antguz

6 years ago, # |

+18

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

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.

→ Reply

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

6 years ago, # ^ |

This testcase has been added to practice. Thank you!

→ Reply

VLamarca

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

antguz

6 years ago, # ^ |

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

→ Reply

zhoutb

6 years ago, # ^ |

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

→ Reply

ILoveDoraemon

6 years ago, # |

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

→ Reply

cdkrot

6 years ago, # ^ |

Ok, we will do it.

→ Reply

botanich

6 years ago, # |

Strong pretests? Wow, it darn good

→ Reply

nagasaisujan160998

6 years ago, # |

← Rev. 3 →

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

→ Reply

Wael.Al.Jamal

6 years ago, # |

+13

rating changes !!

→ Reply

csumanth98

6 years ago, # |

Hi, Are long and long long not same in codeforces GNU G++17 7.3.0 compiler?

→ Reply

lohit_97

6 years ago, # ^ |

long is 32 bits, long long is 64 bits.

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

→ Reply

csumanth98

6 years ago, # ^ |

← Rev. 2 →

#include <iostream>
#include <limits>
int main(int, char **) 
{
    std::cout
    
    << std::numeric_limits< long >::max() << "\n"
    
    << std::numeric_limits< long long >::max() << "\n";
    
}

Why are the max values of both same then?

→ Reply

6 years ago, # ^ |

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

→ Reply

kkarnauk

6 years ago, # ^ |

Long is the same as int in c++

→ Reply

Saat

6 years ago, # ^ |

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¹⁵ to 2¹⁵ - 1), long has at least 32 bits (from - 2³¹ to 2³¹ - 1) and long long has at least 64 bits (from - 2⁶³ to 2⁶³ - 1). Nevertheless, the individual compiler can assign more bits to a particular type.

→ Reply

kasper_askar

6 years ago, # |

Thanks for the great contest)

→ Reply

gryphon

6 years ago, # |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

tdkd

6 years ago, # |

Thank you for a very nice contest

→ Reply

sy_chen

6 years ago, # |

← Rev. 2 →

+24

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

→ Reply