Ashishgup's blog

Codeforces Round #508 (Div. 2)
By Ashishgup, history, 6 years ago, In English

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, cdkrot & 300iq for coordinating my round and Um_nik, craborac, vintage_Vlad_Makeev, 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

  • Vote: I like it
  • +784
  • Vote: I do not like it

Comments Comments (188)
| Write comment?
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Please put this blog into HOME.

→ Reply
»
6 years ago, # |
  Vote: I like it +183 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Indian coders make great problems in codechef :)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +143 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

this will be amazing

→ Reply
»
6 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Sadly, another midnight contest for chinese participants.

→ Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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   Vote: I like it +38 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Ashishgup i hope you saw round 507

→ Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

All the best Ashishgup!

→ Reply
»
6 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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
»
6 years ago, # |
← Rev. 2   Vote: I like it +62 Vote: I do not like it

I am very excited about the contest by Ashishgup.

Because of this blog on Quora.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    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
»
6 years ago, # |
← Rev. 7   Vote: I like it +17 Vote: I do not like it

How to approach D?

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

congrats Ashishgup

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +79 Vote: I do not like it

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
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Hope for strong pretests. X3

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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
»
6 years ago, # |
← Rev. 3   Vote: I like it -11 Vote: I do not like it

strong pretest

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

CF so slow can't load other people submissions

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +35 Vote: I do not like it

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

How to solve D? :(

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Same here. please help

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    if all negative abs(sum) — 2 * max

    if all postive abs(sum) — 2 * min

    else abs(sum)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    For n > 1, you can show that you can choose the order of the eatings in such a way that the final number is  ± a1 ± a2... ± an 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

    .

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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   Vote: I like it +12 Vote: I do not like it

    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
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like 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.

      → Reply
»
6 years ago, # |
  Vote: I like it +39 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D please ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what ! T_T

      hmm , any proof ?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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, # |
  Vote: I like it +17 Vote: I do not like it

How to solve problem E? >_<

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    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, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I agree with you.

      That's like my solution here.

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

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.net/contest/1038/submission/42595983

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +23 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

what is pretest 16 problem D

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the hack for D?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any "Hint" for problem E ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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, # |
  Vote: I like it +13 Vote: I do not like it

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, # |
← Rev. 3   Vote: I like it +35 Vote: I do not like it

Congrats for an amazing contest!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is case 15 in problem D?

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can E be done with max cost max flow?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How about n = 5 and n = 6?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ???

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You can test that with code like this:

            Test code

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

            → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          n=6 means Gcd=3

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

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 3   Vote: I like it +1 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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   Vote: I like it 0 Vote: I do not like it

              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
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it +1 Vote: I do not like it

        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
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

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

Why this was a wrong/invalid hack? Link

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it +54 Vote: I do not like it

Nice problems by Ashishgup.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

E is bitmask ,right?

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/contest/1038/submission/42588288 JUST LAST MINUTE THINGS !!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/contest/1038/submission/42582475

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Please, SEND HELP!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Oh, indeed.

          Thank you very much for pointing out!

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve E?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    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
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why deleting one edge is enought?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yesterday was fine this one was really bad

    → Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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, # |
  Vote: I like it +59 Vote: I do not like it

One of the best codeforces contests ever!!!

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Intuition for Question C?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it

The strong pretests. I like it :)

→ Reply
»
6 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Thanks for the nice contest.

→ Reply
»
6 years ago, # |
  Vote: I like it +69 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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, # ^ |
          Vote: I like it +26 Vote: I do not like it

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

        1. Logic
        2. Constructive Algorithm
        3. Greedy
        4. Logic/DP (both were applicable)
        5. Graph Theory/Bitmasks
        6. Strings/DP

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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +19 Vote: I do not like it

          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
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Nice tasks + nice pretests = super contest. Thanks)

→ Reply
»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    This testcase has been added to practice. Thank you!

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Strong pretests? Wow, it darn good

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

rating changes !!

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    long is 32 bits, long long is 64 bits.

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
      #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, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Long is the same as int in c++

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for the great contest)

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thank you for a very nice contest

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +26 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Can someone check the code for me?

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

Getting an error in Problem C in test case 58

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      My solution got accepted by making the changes you recommended.

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            there are coincidences in the world

            → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

I noticed that winner (Eccentricity) 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

→ Reply