ditoly's blog

Codeforces Round #511
By ditoly, history, 6 years ago, In English

Hello everybody!

I'm glad to invite you to Codeforces Round #511 which will take place on Sep/21/2018 17:35 (Moscow time).

There will be 7 different problems in total, and 5 problems in each division. You will be given 2 hours to solve them.

The problems are prepared by me (ditoly), FallDream and ACMLCZH.

Thanks to 300iq who helps a lot in the round coordination, vintage_Vlad_Makeev, V--o_o--V, demon1999, isaf27, cyand1317 for problem testing and MikeMirzayanov for the platform.

This is my first Codeforces round. Hope you can enjoy it. Good luck!

UPD: The scoring contribution:

Div.1 : 750 — 1000 — 1500 — 2000 — 2500

Div.2 : 500 — 1000 — 1750 — 2000 — 2500

UPD2: Congratulations to the winners!

Div. 1 :

  1. consecutivelimit

  2. scott_wu

  3. ohweonfire

  4. zemen

  5. ko_osaga

Div. 2 :

  1. Ranvan_Darkholme

  2. SqwrIwy

  3. senpai_notice_me

  4. Egor_Gornak

  5. PrinzEugen

UPD3: The editorial is published. There are many things about problem-setting in it. Do not miss it.

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

Comments Comments (213)
| Write comment?
»
6 years ago, # |
  Vote: I like it -79 Vote: I do not like it

Is it as hard as IOI?

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

A red problemsetter round, nice!

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

I hope I will come to Expert after this contest :3

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

Yet Another Chinese Round. :P

Sounds good!

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

I thought FallDream had retired :p

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

[deleted].

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

I have just become CM in Edu Round 51. Can I participate in this div.2 round as a official participant? (I knew that if there are div.1 and div.2 contests at the same time, I can only participate in div 1). I registered div.2 before the update rating of Edu Round 51.

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

    AFAIK people who registered for div2 in advance and then got promoted will get unregistered by the system sometime before the round starts.

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

Aren't Candidate Masters div2-div1, as it changed recently? I can't register for div2 contest

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

    You can register for a div 2 round if there is only one div-2 of this round. Current round has 2 divisions separately.

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

I bet there will be a 10 minutes delay

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

Good luck and have fun with the round!!!!!!!!!111111111

Upd. I mean, enjoy round #111111111

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

Good luck and happy Mid-Autumn Festival!

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

i'm coming expert , i wish i will not carry when can't solve B in contest and back to pupil xD

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

Update : Top 10 will be awarded a mooncake as a gift from Codeforces for Mid-Autumn Festival :D

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

Let's see what this CP thing is about. I've heard about it from some techs at the studio, so I thought "Hey! It'll be a nice distraction from acting", and here I am.

Oh, by the way, if you're near a cinema, go check out La Obra Maestra, a wonderful film with my personal friend (and great actor) Luis Brandoni.

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

https://i.postimg.cc/ZB9rzZ6n/Screenshot_from_2018-09-21_17-13-29.png

https://i.postimg.cc/sQt5V8Jc/Screenshot_from_2018-09-21_17-13-57.png

these are screenshots of registered users. Very strange utkarsh_7330 has registered twice. How could this happen?

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

I hope the problem statements will be just like this blog: short and sweet :)

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

    However, they're short, and with "love" (between little C and 3).

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

What do u guys do in the ~5 min before every contest?? I just keep refreshing and browsing CF.. I wonder if it's just me ... ? :D

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

Yeah looking forward to a nice set of problems.

A red problem setter. Wow !!

Best of luck for your first round as a problem setter ditoly

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

Why is the rating predictor not working?
UPD: It's working now

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

IDEJNIJ KONTEST, VERY INDEJNIY

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

why am i so bad lol

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

another mathforces or digitforces?

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

Looks like I'm gonna get hacked so hard :) . Please test cases be strong.

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

that moment when you waste one hour trying to find what's the mistake in your algorithm and in the end you just wrote one letter by mistake

edit:I'm gonna get Tle for a stupid '}' I'm out :)

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

C gets hacked... Meanwhile this!

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

The hell is the solution for problem C ?

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

    Strip the gcd off all the numbers. Now just find the largest set of numbers with gcd > 1. You can do this by looking for numbers divisible by a common prime factor.

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

read 4 first problems Mathforces confirmed.

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

Anybody knows test 8 problem D(of course div2)??

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

IMO 2019?

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

Every time a chinese guy prepares a contest, I say to myself this chinese contest won't be as bad as the last one. And yet here we are!

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

Problem D div2 / B div1 was a very bad problem for me, what is the point of problems with no ideas but just conditions ?

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

    This problem included the idea, to figure out the conditions.

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

constraints of C is too strict. :(

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

    no

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

      I was unable to think a good solution... Can you tell me what is complexity of the expected solution?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it 
        max = 1.5 * 10 ^ 7
complexity
max * log(log(max)) to find least prime divisor
and
n * log(max) for finding prime divisor of every number
So complexity = O( max * log(log(max)) + n * log(max) )
        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Here is my solution. The idea is to find the cheapest cost for making the gcd a prime factor p greater, for each prime p ≤ amax. This is done by dividing all numbers by the initial gcd, and then counting how many numbers are missing a factor p.

        Factorization of the numbers can be done by precalculating an O(amax) prime sieve to find the smallest prime factor (SPF) of every number  ≤ 1.5 * 107. With SPF precalculated it is possible to factorize numbers in .

        All in all it has the time complexity .

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

I thought I registered for Codeforces contest, not Project Euler...

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

Can anyone tell me what is test case 8 for Problem D (Div-2) ?

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

How to solve Div2C and Div2D?

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

    GCD is min prime factorization for all number example : gcd (9 , 4 , 2) = 2^min(2 , 1 , 0) * 3^(min(2 , 0 , 0)) * 5 ^min(0 , 0 , 0) .. etc so to make gcd bigger you need to loop over every prime factorization and the answer for this prime frac is the number of number that not have this prime you can find it by find every prime frac for all number and add it for freq array then the ans for prime will we just in case n != freq[prime fac] n — freq[prime fac] — ( number of one ) ans = min for all frac don't forget to handle this case 1 2 3 4 => 1 remove (1) 3 3 3 9 9 => 3 remove (3 , 3,3) my solution https://ideone.com/zHLllz i wish it will not get WA at main test and sorry for my bad english

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

It's a pity that i can not hack myself.

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

Math Problems.

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

Look around, life has many interesting problems. But dude, you chose math :D

Good contest by the way.

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

how do you solve B?

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

    nvm, i see it is all casework like i expected, too bad

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

      can't believe i wasted an hour and a half on that and still got it wrong LOL

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

      There is no need to check all the tricky cases by hand. You can write bruteforce and find all of them.

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

        I don't understand how you get all tricky cases by bruteforce. Can you explain briefly? (maybe with code?)

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

          Recursive backtracking should be enough for very small grids.

          Alternatively, you can also find the max matching of the bipartite graph where each vertex is a square of the grid and two squares are connected iff their Manhattan Distance is 3 via Max Flow or any other matching algorithm.

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

    just a bunch of if conditions

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

      What is the better way of training for solving these problems?

      Also, what philosophy does one need to follow when solving them? Doing a bruteforce solution, then trying a bunch of test cases until one finds a pattern?

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

        i am really not the good person to ask :V but anyway if i didn't find any reasonable solution to a problem i make a bruteforce solution ans observe the pattern if there is one

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

It seems the pretests of problem div2.C are weak...

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

"that of all integers" Nah..

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

And just like that, you wasted 2 hours of my life!

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

In div1C, does the following hold?

We can divide the kingdom into sections with each having sum X, iff sum(tree)%X  =  0, and exactly sum(tree)  /  X subtrees T have sum(T)%x  =  0. The division can be done by cutting edges to the parent from such nodes.

I couldn't find a counterexample, but unfortunately didn't have time to code either.

Edit: Proof:

Clearly we need X divides sum(tree), and that there exist at least sum(tree) / X such subtrees, for X to work. Now assume that there are K such subtrees. Cut their parents. Now we have K different parts (one of the subtrees was our root), each of them has sum divisible by X, and of course holds . If K > sum(tree) / X, we have a contradiction. If , we have a contradiction. Therefore the sum of every part is X, and we're done.

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

    I've also thought of it, but I couldn't see a way to use this.

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

      I think if that holds, you can solve the problem pretty easily.

      1. Find sum(T) for every subtree T in the tree. Store these in vector subtree-sums
      2. subtree-sums <- gcd(subtree-sums, sum(tree))
      3. find all divisors of sum(tree), and index them
      4. Create subtree-counts, where subtree-counts[j] is the amount of appearances of divisor j of sum(tree) in subtree-sums
      5. do SOS-dynamic programming over this set, to set subtree-counts[i] <- amount of elements in subtree-sums such that divisor i divides them
      6. make array subtree-ans, where subtree-ans[i] = 1 iff subtree-counts[i] = sum(tree) / (divisor i)
      7. loop over all divisors i of sum(tree) from smallest to largest, and do subtree-ans[j] += subtree-ans[i] for all j, such that divisor-j / divisor-i = p for some prime p. Remember to take mod
      8. Output subtree-ans[i], where divisor-i = sum(tree)

      We use a few facts here:

      1. sum(tree) has at most like 1e5 divisors

      2. If X is a possible number, and Y is a possible number, and X % Y = 0, then we can first divide into X, then into Y. This follows from the way we select the nodes whose parents we cut.

      3. The way to cut the parents is unique for any value X

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

        It's even more easier. Let number x be "good" if you can divide T with subtree size sum(T) / x. dp[i] = 0 if i is not good, otherwise. Time complexity is using harmonic sums.

        Checking if is good can be done with similar way in , after you know gcd(sum(subtree), sum(T))

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

          Doesn't doing the harmonic sum naively with something like unordered maps give you complexity O(sum(tree) log(sum(tree))? How do you get it to n log n?

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

            The number in form of sum(T) / i for are only relevant, so you don't need unordered map, just an array of size N.

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

    Yes, your statement holds.

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

    The idea is probably correct, I have used it before on another problem. I couldn't really do anything with it though.

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

Div2C Converting all ll divisions to int divisions drastically changed the running time... How does it even affect though?

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

What happens if I resubmit a solution to a problem which I have already submitted a solution which passed the pretests?

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

    The first solution which passes the system tests is considered and any WA before that will be an unsuccessful submission as usual.

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

      That is not accured, the system ignore all submmits but the last one, you shoould read Skipped in the previos pretests passed.

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

What will be the approach for problem Div2 C (Enlarge GCD). I had TLE in 8th pretest.

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

    Did something like sieve. Only marginally avoided TLE. Wonder what will happen after systest.

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

      I used sieve and then calculated the minimum power of each prime in each number so as to evaluate the minimum number of terms to delete to get an enlarged GCD. How did you solve @from_bd_with_depression??

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

        Instead of calculating power, I just checked how many numbers are divisible by for all numbers > gcd

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

      Yes I also had the issue that if I use all primes upto MAX=1.5x10^7, then I got TLE on test case 8, whereas if I use numbers upto sqrt(MAX), then the pretests passed (but the solution is wrong, you have to take all primes upto MAX). Why do they keep such tight time limits?

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

        Use the O(NloglogN) sieve. I used it and ran C in merely 0.5 seconds. NlogN sieve will obviously be tight.

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

          I used sieve of eratosthenes, its complexity is nloglogn.

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

            Same as me then. How on earth did you TLE that out. I ran that sieve on custom test and it resulted in a mere 138ms EDIT: Nvm I just saw your complexity. Obviously you will TLE with that O(N * max(A)) algorithm, even with 5 seconds

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

              Okay I saw the editorial. I get the difference now. Thank you so much for the suggestions DrumpfTheGodEmperor :)

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

Sorry, but it was one the worst contest I've ever seen (I saw rounds of GreenGrape)

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

I used custom test for my E before submitting it. It ran more than 10s when n = 21 on custom test. Then I spent about 30 min on how to squeeze my code in to TL, but failed. After that, I decided to submit one similar to my first code and it got PP in 499ms. Anyone knows what had just happened to me?

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

    From what you said, looks like you lost 300 pts, 30 min * 10 pts per minute and you got 9'th instead of 3'rd. That's what happened to you.

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

I was using this as generator to hack Div2 C:

https://ideone.com/6yWmn9

It kept giving me an invalid input error with the following:

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

Can someone tell me how to fix it?

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

    In my memory, you should give newline as endl(instead of '\n') in hack data generator code.

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

      I use printf("\n") without problem. The problem is that it should have a "return 0;"

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

        In this case cf should give a better error :/ Is there any way to test the generator now?

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

      Oh wow, I didn't know there was any difference between the two. Is there anyway I can test if replacing "\n" with endl would fix the generator now?

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

    You wrote if(i!=n); so it generates an extra space at the end of the second line.

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

      I don't get it? That was written specifically to avoid printing an extra space at the end of the last (nth) element.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it 
        if(1 > 2);
  cout << "1 is greater than 2";
        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh wow, just saw it, that was pretty stupid lol. Thank you guys for pointing it out!

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

DIV. 1 B is the kind of problem that when you submit it you just pray you didn't forget any if -_-

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

Pretests of Div2 C was weak I think. I see some codes(including mine) which only calculates primes to sqrt(1.5*10^7), and they all passed. But the case above makes them broken:

3
100069 100069 1000103

These codes gives answer as "-1", while it is "1".

Hope to see a round with better constraints, and better pretests, of course.

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

what is wrong in this submission(DIV 2 B).43208324

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

    Test 3 4 0 5 You are actually calculating max distance from origin rather than max of sum of x+y because since two sides are equal the equation of third side is of the form x/a+y/a=1 we have to find a.

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

    All you had to do was print the max possible sum of coordinates.

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

How to solve Div2 D?

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

Really strange thing happened...

When I submitted A, it said I had submitted the same code before:

Then I tried to modify my code, and add some annotations, but it's no use. I tried B, still the same.

I don't know why but I came up with the idea of using VPN, and I found myself not registered yet, but I remembered that I had registered. However, I registered again, and I was able to submit my codes.

Later, I turned off the VPN, and I could not submit my codes again. I turned it on and I could submit again.

The most incredible thing is, I found that I had registered twice..

I just wanna know what happened?

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

    Codeforces got hacked after System Tests. Mike should find the bug of his code.

    JK

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

I am confusing...

I tried to hack the problem, but there no success.

Please see code link, this solution should be time limit exceeded, but codeforces system said everything ok and I got wrong hack attempt with this test 1 10^9 10^9. I tested it in my local computer, the code isn't working in IDE.

How can I understand?

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

    There were many cases source code in C++ works properly with complexity of O(n), when n ≤ 109.

    Try with 105 points instead.

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

Is it just me or do you also think this one for Div.1 was extra hard?

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

    You can usually anticipate super hard contest with Chinese authors. I especially like problem E, but my bit mojo is weak.

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

      I especially like problem E...

      I have only read A, B and C and solved nothing during the contest anyway. I think I came up with a solution for B during the contest and finished writing it a few minutes after the contest finished but I can only check after the system testing.

      Anyway, (if I were to finish and submit 'B' in time) I would probably only lose rating for the single problem solved few minutes before the finish.

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

For C, just divide the array elements by initial GCD, and then https://www.geeksforgeeks.org/largest-subsequence-gcd-greater-1/

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

    This method is the most intuitive IMO, thanks for this short solution :)

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

How to solve Div2-C?

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

    For C just find gcd and then use sieve to find numbers of multiples in given array for every number above this gcd. Now the maximum number of multiples among these numbers will remove minimum integers from array. However due to strict time limit we cant use this algo. So to optimize it we see that if we find number of multiples for a number then we dont need to check this for its multiples as number of their multiples will be less than or equal to this answer. this is my solution

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

Solved exactly div 1 E a few days back but didn't read it the whole contest. :)

Solution if anyone's interested: https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf

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

Div2C constraints aren't fair for Java users x)

Same solution in C++ passes in around ~600ms & around ~990ms in JAVA.

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

I got TL on test 15 in A :( isn't it too harsh to set n = 300000, MAX = 15000000 for A?

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

So many math problems... This contest is not friendly to me at all

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

I'm not good in Mathematics, so I used bipartite matching in div1B. It was terrible for me. :(

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

Div2C/Div1A should have had 1 more second time limit

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

After C — that memory in right corner

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

really you can define array of size 1.5 * 1e7 when i am define array with size 1e6 the codeblocks became slow, That's why I did not think about sieve and get TLE in case 10!!!

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

I'm the only one who solved the problem div2 B with Binary Search by answer? I dont understand solutions

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

    You have to search the point further to the point (0,0) whit this point (x,y) we need to know which is the begining of the hipotenuse of the triangle that passes fot that point and this is (0,x+y) and the end is (x+y,0)

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

    It's very simple, you need to cover all n points with an isosceles triangle that uses X and Y axis as sides, so you will use a line y = mx + b such that the points (0, x) and (x, 0) belong to it for any x.

    We see that x = b and m =  - 1, and also notice that the sides in the axis are the smallest ones from the triangle, so we only need to find b and it will be our answer.

    Now, if we set an "order" to the points by using the b they would generate, we notice that the maximum b generated will cover all of the points, so that's what we do.

    We compute the b by using , that's why all do something like this:

    int ans = 0;
for(int i=0; i<n; i++){
   ans = max(ans,x[i]+y[i]);
}
printf("%d\n",ans);
    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    My first thought was that too

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

Hey guys. This two guys cheated on problem C. Just check these two submissions. http://mirror.codeforces.com/contest/1047/submission/43207716 http://mirror.codeforces.com/contest/1047/submission/43197339 The first submission is really similar to the second

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

    Codeforces before the update of ratings search for similary solutions and if codeforces find some solutions similary all the participants except the first participant who uploaded the solution are disqualified from the contest

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

Hey guys, I really want to improve my problem solving skills. During the competition, I had no idea what to do for Div 1B/Div 2D and gave up.

I noticed a lot of accepted solutions were if-else statements. Could I kindly ask for advice on strategies to reach these solutions?

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

    Solve it for n, m ≤ 20 with max flow, then make a spreadsheet of all these values and recognize the pattern.

    Solution

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

      Or just use pen and paper — thought it might be a little slower.

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

        Hey, thanks for your reply! Yeah, I was trying to do that, but couldn't see any patterns... I also stopped solving it by hand at around N = 4, M = 6 -ish.

        Could I ask how many examples you did by hand?

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

      Awesome, thanks so much Ben! I guess I spent too much time trying to think of insights instead of analyzing the patterns haha

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

        If you don't want to analyze the pattern, you could make an educated guess that since 1 × 6 grid can be completely covered so it is likely that for larger grids you can delete 6 × m or n × 6 blocks from it and the answer will remain the same. Thus, you can keep subtracting n and m by 6 until you reach a small enough value where you can solve it via max flow.

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

          Hey zscoder! Thanks so much for that advice, that really makes a lot of sense to me!

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

          I got your point. But missing few things. Can you please tell me, what are source node and target node for Max Flow execution? As well as, what will be the flows on edges?

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

Is there anyone solve problem C with java ?

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

does anyone have the test case #44 of Div1 C/ Div2 A. I got WA on this test :((

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

Despite losing rating again, well, I can proudly say that I've succeeded in achieving something (maybe) no Codeforces users have done before :D

(Look at the execution time of my C solution, it even overrides time limit LOL)

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

--Del--

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

you know a contest is bad when 100 points=2000 position difference

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

The constraints for C are plain bullshit. Spoiled the contest for me.

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

    You created the sieve needlessly large (MAXN = 2e7+5). But I agree, the time limit should have definitely been 2s.

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

      The time constraint was the only thing that made this problem interesting. With some optimization in sieve we can easily pass this problem in 1s.

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

        Does copy-pasting linear sieve really make problem more interesting? Not sure about it

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

    I didn't even try to optimize my sieve, still pass

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

A had a faulty description, which I needed a clarification to solve. and I didn't liked problem B.

However, after then the problems were interesting (especially D). Too bad my optimal strategy was just bashing hacks.

Thank you for the great problems!

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

Screencast of the round(div2). https://youtu.be/NMyhboAp0DI problems solved: A, B, C

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

Funny fact, My friend place at standing and mine difference is 3 our score differs by 3 and he accepted C 3 minutes after me I guess Little C really loves 3 :)

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

http://mirror.codeforces.com/contest/1047/submission/43216650

http://mirror.codeforces.com/contest/1047/submission/43220019

Find the difference.

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

missed many test cases in div2C... Done :(

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

    I dont know about the test but i read your code i know what the problem is,

    When you want find the div you go till 320 which isnt the square root of 15e6 clearly you’re trying pass the timelimit with a solution that is completely time

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

      checking with the 1st 320 primes is enough to find the factors of a number <=10^7.. i guess.. my code passed with just 320 primes..

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        No, it is not. For example it is not enough to find prime factors of 4553947. It is 2131*2137, multiplication of 321th and 322th prime numbers. Your solution fails on the following test case:


3
2137 4541161 4553947

2137 = 322th prime number
4541161 = square of 321th prime number
4553947 = multiplication of 231th and 232th prime numbers
Your program outputs 2, whereas right answer is 1(we can delete 2137).

P.S. You are very lucky as I hacked your wrong solution after the contest:)
        → Reply
»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Hi,

My submission, abhisheksince97/43197368 has been flagged for coinciding with solutions vbbvaddd79506/43196786, priyasen54/43197486, fibo1/43201480, gennadykorotkevichaz/43202067, cpp19/43202087, milanmas/43202887.

I can prove that the solution is mine and the others have copied it. You can open all my recent past submissions, I have used the same template for .cpp file as I have done in this one. The rest have clearly copied.

Also, the solution that I have written is available on geeksforgeeks (https://www.geeksforgeeks.org/largest-subsequence-gcd-greater-1/). This could also be the reason for the match.

I was really foolish and naive to have tested my code on ideone. Please verify that I am the true author of this solution and please let this contest be rated for me as I put a lot of effort into it. I have never done such a mistake before and wont do it ever again.

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

    you can't copy/past code from geeksforgeeks or some other site, am sure many users did the same and got skipped like you.

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

      "If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details." This is the message that I got from Codeforeces System. Above, I have provided a conclusive evidence that the coincidence has occurred because of a similar problem on geeksforgeeks. If you put a little bit of effort, you will be able to see that the exact problem on geeksforgeeks is different from the question asked in the Round. I used the approach taken by the geeksforgeeks solution.

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

      Can we use code from Emaxx?

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

      you can't copy/past code from geeksforgeeks or some other site, am sure many users did the same and got skipped like you. Actually, you can do that as long as that code is published before contest and it's not copyrighted.

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

        You are right, its my mistake, actually every thing is clear here

        However, anyone should try to solve the problem by his eforts, goggling the solution wont help anyone improve.

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

Where is editorial?:c

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

I think these guys cheated and got away with it.
http://mirror.codeforces.com/contest/1047/submission/43211821
http://mirror.codeforces.com/contest/1047/submission/43209970

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

Can someone help me with my solution. I am not able to figure why it failed in system tests. solution

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

Around 180 soln of C/D failed in top 380.

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

WTF, wasn't packing product (E) really never asked before?

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

Old and kind div2 contests, where is possible to come up with only two first problems... Mmm, i have missed it too long

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

Little C is so cute(qwq)...But this round looks like a math round and it's a little difficult

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

I'm the one who suggested raising the constraints of 2C/1A. The original version had 1e7, and a simpler solution exists (see code below) which the author doesn't intend to accept. Thus the final version had 1.5e7 with a higher TL.

Though I wouldn't consider it good to let make a difference, I did nothing afterwards in attempts to improve the situation. If the current limits ever causes unintended FSTs, I'm the de facto person to bring about all these.

O(A log A)

Some may say the problems don't fit a CF round well, but I've spend 4+ hours on the problems only as a tester (not to say authors and coordinators) and I don't feel it's been wasted. Maybe my time isn't as valuable as yours, but isn't it nice just to have some intellectual challenges?

Round #111111111 draws the curtain on the good old 9-bit days. Wish you can get your affected rating (if any) back in the new era! :)

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

Thank you for the simplify of the problem discription!!! It is easy to understand it! A nice math round!(Even though the pretest C is weak :D)

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

I just finished coding div1-C but the queue is too long and it doesn't seem to progress...

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

Div2 C, I think the number of the remaining integers must be two at least because gcd needs two or more integers. (https://en.wikipedia.org/wiki/Greatest_common_divisor) So, I think the answer of pretest 4 is not 1, but -1. Is this wrong?

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

for D(div2)why(n=7;m=1)answer is 6?

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

MikeMirzayanov, why is the queue so long, when will the submissions start getting judged ? Please look into the matter at the earliest :(

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

So where is the editorial?

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

I think this round is not a good round.ABCD is easy and E is hard.If you code very fast,you'll get a satisfying rank.In fact,this round has little discrimination.

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

Waiting for Editorial ! Can anyone help with Div 2 Problem C ?

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

From the past contests we all apreciate codeforces for organize frequent contests and fast editorials .I think they misplaced their track but right now they are on their track so guys editorial will be in 2-3 days...hullaaaaaa

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

How to solve Div1 C / Div2 E ??

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

Low memory solution for Div.2C / Div.1A

http://mirror.codeforces.com/contest/1047/submission/43263896

Btw, maybe you guys can add some more optimizations for this solution(except custom i/o), i'd appreciate it.

→ Reply