By KAN, 3 years ago, translation, In English

Hi!

Tomorrow, at Nov/25/2018 19:35 (Moscow time) we will host the final round of Mail.Ru Cup 2018. The problems were authored and prepared by Codeforces team: me, Dmitry cdkrot Sayutin, Ildar 300iq Gainullin and Mike MikeMirzayanov Mirzayanov, and also Maxim Neon Mezhcheryakov. Huge thanks to Grigory vintage_Vlad_Makeev Reznikov abd Kamil Errichto Debowski for problems' testing!

This round is the final in the new championship called Mail.Ru Cup, you can learn more about it following the link. The round will be rated for everybody!

After the round we will know who will get the following prizes:

  • First place — Apple MacBook Air
  • Second and third place — Apple iPad
  • Fourth, fifth, sixth places — Samsung Gear S3
  • Traditionally, the top 100 championship participants will get cool T-shirts!

In each round, top 100 participants get prize points according to the table. The championship's result of a participant is the sum of the two largest results he gets on the three rounds. The results of the two first rounds are published here. In case of ties in the top six places, they will be broken by the sum of in-round scores in the corresponding (best for the participant) two rounds.

There will be eight problems and two and a half hours to solve them.

Good luck!

P. S. MikeMirzayanov invites everybody to the official Codeforces channel in Telegram: t.me/codeforces_official.

The round has finished, thanks everybody, hope you liked the problems!

Congratolations to the winners of the third round of Mail.Ru Cup 2018:

  1. Radewoosh
  2. V--o_o--V
  3. ch_egor
  4. ksun48
  5. RAVEman

The results of the Cup will be announced shortly.

The editorial is here.

Announcement of Mail.Ru Cup 2018 Round 3
 
 
 
 
  • Vote: I like it
  • +198
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I hope there isn't much controversy like today's contest.

»
3 years ago, # |
Rev. 2   Vote: I like it -49 Vote: I do not like it

I want to become Cyan :p

»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

There seems to be an unusually large amount of spam in the comments.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me figure out what is the motive behind the telegram channel? Do we have permission to write our comments there or we can just read?

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

    I think it's for admins to give announcements in case website crashes or something.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello MikeMirzayanov why my comment in this post is removed ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -43 Vote: I do not like it

    You have replied to a comment which got a lot of downvotes; such comments are hidden as well as replies to it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Two thanks to MikeMirzayanov?? Hope this round goes well. Thanks MikeMirzayanov

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Don't you want to post anything on that channel??? At least announcing the contests...

»
3 years ago, # |
  Vote: I like it -31 Vote: I do not like it

Is it rated? :D

»
3 years ago, # |
  Vote: I like it -39 Vote: I do not like it

We have all guys from top-10 registered for the contest except only tourist and Retired_MiFaFaOvO. Will they join and make competition really high and interesting?

»
3 years ago, # |
  Vote: I like it -16 Vote: I do not like it

die

like right now

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

tourist hasnt registered yet! i think mnbvmar going to be the first in rating

»
3 years ago, # |
  Vote: I like it -18 Vote: I do not like it

hello i live in a very rural part of yugoslavia and i would like to know if this contest is rated for me too. thank you

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No contest till 3 weeks! why?

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

    This is codeforces, wait for some days then you can see the list of the contests.

    so please be with codeforces.

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

    Contest in 3 days. Now that is CodeForces :)

»
3 years ago, # |
  Vote: I like it +69 Vote: I do not like it

You should fix the bug on the m1.codeforces.com (and m2,m3) platforms.

I was able to lock problem D and then resubmit it. My second submission must of course be skipped, and the same should happen to all contestants that took advantage of that bug.

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

    Is this the reason why so many submissions on D or is it a very standard problem????

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

      D was very basic graph/tree problem. So i dont think that is the reason.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What is the hack for D?

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

    Seems like n = 1.

    My code fails on this case, nobody hacked me :(

    RIP my rating.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      What is the answer?

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

        It should be 1.

        But my code doesn't even output anything lol.

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

      UH OH

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it +10 Vote: I do not like it

      In problem D hack attempt: input: n = 1, giving status: invalid_input, I think it is a valid case 1 <= N <= 100000.

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

        This happened to me too, but I fixed it by inputting an empty line after the 1.

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

          hack validation script might not handling the empty line.

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

            Well, it seemed to handle my empty line with no problems so I think the script can :)

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

      Holy smoke.. if there is n = 1 in systests then FML

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve B ?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If you can count number of numbers with remainder i, it's easy to calculate number of x*x % m = i.

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

    We just have to store the values of (i*i)%m for i=1 to m, the values repeat thereafter.So maintain an array which will store number of values for a particular mod value(0 to m-1). a[(i*i)%m]+=(n/m) for i=1 to m and then compute for remaining values(i=(n/m)*m+1 to n). Then,loop through all values of mod such that mod value k can pair with mod value (m-k).

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

    How to solve D ?

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

      For every node, count the number of leafs in its subtree. Store this number in an array, let's call it numleafs. Then sort numleafs in non-decreasing order (smallest element first). For every k from 1 to n, the answer is numleafs[k-1].

      You can count the number of leafs in a node's subtree with a "simple" dfs.

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

    If we knew the number of elements in range [12, 22, ..., n 2] that are divisible by m with remainder i (where, 0 <  = i < m), we can esily count the result, that is, the number of pairs of squares elements that are their sum is divisible by m (without remainder).

    To know that, we should know:

    1) how to find the number of elements in range [1, 2, ..., n] that are divisible by m with remainder i (where, 0 <  = i < m).

    2) how to transform from [1, 2, ..., n] to [12, 22, ..., n 2].

    This is my submission for more details.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wth is pretest 5 in B

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide test 7 for E? Got runtime error :(

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

    I got RTE on 5 because didn't use long long for some multiplications, maybe that's your case?

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

      Yes, yes already got it. Is int overflow considered runtime error?

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

        Yeah, at least in my case that was the error.

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

          Cool, anyway thank for help.

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

    Big strings' sizes i think. My solution failed because of overflow. Used long long and it passed.

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

I can't wait till the system testing finishes. Has anybody an idea what is pretest 17 of problem E??

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

    I think anti hash.. I changed my hash function and it passed for me..

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

      I tried hashing with 2 bases (29 and 31) mod 2^64 but still got WA :(

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

        You should never hash with 2^64!

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

        hashing mod 2^64 can be made to fail. I did the same thing. U need to change it to something not of form 2^n

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

          I did not know about that. So I guess hashing with 2 or 3 big primes is the only option.

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

            I dont think hashing with primes is necessary. non-primes should work too.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            if you pick your primes from here then you won't get WA because of anti hsash

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

        my hash solution of MOD 2^64 failed test 17 too,maybe test 17 is a speciallly structured test case

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +32 Vote: I do not like it
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I guess today's contest will serve as a good reminder for me.

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

      Exactly, this is a test against 264 hashes.

      Of course we are not retarded enough to generate anti-hash tests to default modulos/p's, but hashes against 264 is a known vulnerability with easy antitest.

»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

What's pretest 2 in F?

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

    Probably some random test case, but looks like I can only pass by switching to using binary search / ternary search instead of analytic solutions.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 4   Vote: I like it +16 Vote: I do not like it

      I switched to ternary search as well but no luck.

      My solution was to find with DP the minimum of achievable for a fixed k and total number of points P. Then we can minimize and check whether it fits under time.

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

        I have the same one! And I don't have any reasons why my solution doesn't work.

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

          I passed pretest 2 when realized that t must be non-negative. So I took t = 0 if f(t) is minimum at negative t (but I got wa56 then and I have to clue about it)

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

            Your INF is too small

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

              Oh, shit! Thanks! I was so close to achieving red color and a T-shirt...

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

            Oh, i’ve just skipped if t < 0

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I did the same thing and failed to the same test :(

        This is one thing I hate about math problems: The idea is often trivial but in the implementation you have to do so much math that it's inevitable you'll get bug :/

        EDIT: my bugs were the following:

        1. I calculated the optimal x (time spent training) as x = max((ld)0, -b/2*a), when it should be (2*a)

        2. Knapsack looped from bottom to top, allowing the same item to be used twice

        ... how this even passed the first test, I'm not sure

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Okay I had a major fuck-up which didn't trigger samples (never does): applied rearrangement inequality in reverse direction. Sorting the array in reverse direction worked.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I think the problem with analytic solutions might be that the value of t which minimizes the function comes to be negative. That seems to be the only thing I missed in my solution.

        EDIT : Yes, that was the only fault in my solution.

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

        Look at mine: 46228777

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

      I also lost about 50 minutes due to the same issue , but I've no idea WTH is wrong with it. Does anyone knows why this happens?

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

        What did you change?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I changed the O(1) formula to find the maximum value in a concave function to a O(log(T)) ternary search and passed the pretests.

          By the way if anyone is interested , here's a counter test :

          1

          4

          1.000 11.112

          4 9

          12 3

          1 3

          1 5

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

            I had that as well but it was because the formula gave me a negative value for t. It worked when I maxed it with 0.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please guide for B and D

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

    For D: count the number of leaves in every subtree, then sort.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This was my first time solving D but I failed to solve B >:(

Can someone please tel me how to solve B?

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

    How to solve D?

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

    ((i*i) + (j*j))%k can be written as ((i%k*i%k)%k + (j%k*j%k)%k)%k. Keep count of number of i's such that (i%k) = j for all j from 0 to (k-1). Similarly using this count array, construct (i*i)%k mapping to j, let this be arr. Now for every i,j such that 0<=i<k and 0<=j<k if (i*i + j*j)%k == 0 add the value of arr[i]*arr[j].

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

      Thanks! Simplifying the problem using modular arithmetic was really smart.

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

    Instead of thinking of the coordinates as numbers from 1 to n, think of it as several consecutive periods of numbers from 1 to m.

    Traverse an integer i from 1 to m. With each value, calculate two value:

    • cnt: number of periods that contains i within range [1, n].
    • r: the remainder of i 2 when divided by m.

    Make an array RemCnt[], and with each i, add cnt to RemCnt[r].

    After this, we can safely do a O(m 2) traverse to find out the number of pairs (i, j) such as i + j is divisible by m.

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

      Thanks I understand how to do it now :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B was a fantastic problem.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D hack attempt: input: n = 1, giving status: invalid_input, I think it is a valid case 1 <= N <= 100000 .

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

    What's output for n=1?

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

      I think the output should be: 1 (since root node == leaf node).

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

    Probably you forgot to print an empty line, remember that the array of parents must be printed in a different line.

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

whats the test case 7 in C ??

»
3 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Tfw you're worried AF about system tests in E because you used a single and standard hash :(

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

    Haha, May the force be with us all :P

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

    No reason to be afraid of system tests if you survived hacking phase, I didn't have that luck ;_;

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

    I'm using an insanely weird modular number, yet the "single" property still makes me worried as hell, especially seeing Swistakk got hacked...

    What I've used
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Can you explain your solution for E?

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

      Loop length of the string replacing zeroes, calculate length of string replacing ones, and check if this configuration works with hashes. Complexity is O(n log n) since you do n + n/2 + ... + n/n = O(n log n) work.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys, what is the tricky part in problem C, i get wrong answer on test 7. :(

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Probably the query you are accidentally printing is the value of the player itself and not the index. I got a WA on test case 7 for that one.

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

    I think for optimal solution you have to take special pairs of heroes first. I also got WA on test 7..... I fix this and pretest passed.

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

    Simply you were getting the strategy wrong.

    If you have a turn and not being obliged by anything, you can choose one pair of special heroes, pick the stronger one, therefore forcing your opponent to pick the weak one, and give you back your turn again. It's a clear win-win, so whenever you have a chance to freely choose heroes, repeat that process until there's no special heroes' pairs left unchosen.

    After that being done, we return to the normal, maximum-prioritized strategy.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D,Sample test 2

At k = 4 why is the node 3 happy? considering that subtree of node 3 consists of (3,4,5) we only colored (4,5) what about 3(it can't be colored) but shouldn't be counted as colored?

A happy junction is such a junction t that all light bulbs in the subtree of t have different colors.

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

    We color leaves only.

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

    "all the lights" so the nodes with no lights are ignored, every junction is concerned only with the "lights" in its subtree.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

what is the hack for D ?

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

fast system testing running...

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

why can't you fcking include n = 1 in pretests?

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

    Because it is corner case and it should be quite obvious to check before submitting solution. So if you didn't that — it's your fcking problem.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -48 Vote: I do not like it

      If it's my problem then don't fcking reply me

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

      Yeah I feel bad for not trying it but at least I learned a valuable lesson.

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it -21 Vote: I do not like it

    Depending on how you implemented it, n=1 is not even a corner case; it can be handled by the general case. If you consider the sole node in n=1 to be a leaf and begin processing nodes at the leaves, you shouldn't run into an error with n=1, and you don't need a special case for it either.

»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

This has to be the Fastest System Test ever.

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Thanks for fast system testing!

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

codeforces system testing rocks...

fastest ever.

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

No n = 1 in pretests for D? Are you kidding me!?!?!?!?!

»
3 years ago, # |
Rev. 2   Vote: I like it +29 Vote: I do not like it

Open it for practice please Edit: Its open now, wonder why the delay.

»
3 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Was that the fastest System testing in Codeforces history :D

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

How long after the contest can we submit solutions again?

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

mnbvmar gonna win Apple MacBook Air.

»
3 years ago, # |
  Vote: I like it -28 Vote: I do not like it

Very bad problemset for div.2. >5k registered users, >3k users participated (made submissions), about 1.3k participants solved A. And only 1.7k solved more than A (or at least B or C). So if you were participant of div.2 level, you probably read problems' A statement, almost immediately submitted an answer, and then you could leave contest, and your place will be determined only by comparing submission speed (and speed of overcoming of starting 502 Bad gateway) of problem A comparing with thousand other same level participants. I want to emphasize that there were no announcement about difficulty of the problemset, only it was said that this round is for all (so it means for div.1 + div.2 + div.3). And there were "АЖ" 8 problems. 7 of them were for 2/3 participants. In my opinion, better were to offer for all participants: about 2 problems of div.3 level, about 2 problems of div.2 B-C level, and about 4 more difficult problems.

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

    The only thing you should do is to stop complaining and improve yourself, and you will find out that pB is trivial enough.

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

    rsFalse has a point here. B, C, D felt of the same difficulty, which isn't good already. For div. 1 guys they all felt easy, and for div. 2 guys they were all medium. Making B easier and D harder would've been appreciated by more people as then B would've been solvable by more div. 2 and div. 3 people, while D would've been more interesting for div. 1 participants. Problems of the same difficulty really create issues, but this is difficult to avoid when preparing a contest.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B ??

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

    For a given n and m you have to count how many i, j are there where (i^2 + j^2) = 0 (mod m). You can easily see that i^2 mod m and j^2 mod m ( i, j from 1,..., n) forms a cycle.So, ans will be equal cnt[i^2 mod m] * cnt[m — ( i^2 mod m)]. Check my submission 46215431

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

By the way, why is the next competition three weeks away?

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

    Maybe they are just taking care of new problems/competitions before posting them.

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

congratulation to yashChandnani to become a red coder.

such an inspiring rating graph.

»
3 years ago, # |
Rev. 2   Vote: I like it +44 Vote: I do not like it

Is there a reason for the tight time limit on problem H of 1 second, when n is 300000 and the intended solution is O(n sqrt(n))? Were there any unintended solutions you wanted to keep out with this time limit?

EDIT: sorry, I referred to the wrong problem

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    ? Time Limit is 3sec, n is 1e6 and intended solution is n.

    Did you mean H?

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it
46235526

Problem A TEST 10. My answer is correct and the test result is incorrect. How can I pass the test?

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

    You answer is incorrect since you have 64.

    Notice the first numbers from 2nd line and so on indicate the number of stops in that line and it is not a stop itself.

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

      I misunderstood that part. Thanks for the correction!

»
3 years ago, # |
  Vote: I like it -20 Vote: I do not like it

i don't care