Блог пользователя Ashishgup

Автор Ashishgup, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • +784
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Please put this blog into HOME.

»
6 лет назад, # |
  Проголосовать: нравится +183 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

this will be amazing

»
6 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

Sadly, another midnight contest for chinese participants.

»
6 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +38 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

Ashishgup i hope you saw round 507

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

All the best Ashishgup!

»
6 лет назад, # |
  Проголосовать: нравится +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 .

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +62 Проголосовать: не нравится

I am very excited about the contest by Ashishgup.

Because of this blog on Quora.

»
6 лет назад, # |
Rev. 7   Проголосовать: нравится +17 Проголосовать: не нравится

How to approach D?

»
6 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

congrats Ashishgup

»
6 лет назад, # |
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!

»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Hope for strong pretests. X3

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +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. :)

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится -11 Проголосовать: не нравится

strong pretest

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

CF so slow can't load other people submissions

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

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

How to solve D? :(

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Same here. please help

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    if all negative abs(sum) — 2 * max

    if all postive abs(sum) — 2 * min

    else abs(sum)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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  ± 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

    .

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, # ^ |
    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
6 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve D please ?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      what ! T_T

      hmm , any proof ?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

How to solve problem E? >_<

  • »
    »
    6 лет назад, # ^ |
    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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
6 лет назад, # |
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!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what is pretest 16 problem D

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the hack for D?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any "Hint" for problem E ?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +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?

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +35 Проголосовать: не нравится

Congrats for an amazing contest!

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What is case 15 in problem D?

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Can E be done with max cost max flow?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How about n = 5 and n = 6?

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          ???

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            You can test that with code like this:

            Test code

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          n=6 means Gcd=3

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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

»
6 лет назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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

Why this was a wrong/invalid hack? Link

»
6 лет назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

Nice problems by Ashishgup.

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

E is bitmask ,right?

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 ?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Please, SEND HELP!

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve E?

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why deleting one edge is enought?

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
6 лет назад, # |
  Проголосовать: нравится +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!!

»
6 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

One of the best codeforces contests ever!!!

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Intuition for Question C?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

The strong pretests. I like it :)

»
6 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

Thanks for the nice contest.

»
6 лет назад, # |
  Проголосовать: нравится +69 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +26 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +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.

»
6 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Nice tasks + nice pretests = super contest. Thanks)

»
6 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    This testcase has been added to practice. Thank you!

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Strong pretests? Wow, it darn good

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

rating changes !!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    long is 32 bits, long long is 64 bits.

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

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      #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?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Long is the same as int in c++

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Ну почему пересчёт рейтинга снова такой долгий?!

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Thanks for the great contest)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Thank you for a very nice contest

»
6 лет назад, # |
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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

    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)

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Can someone check the code for me?

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

Getting an error in Problem C in test case 58

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      My solution got accepted by making the changes you recommended.

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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