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

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

Hello denizens of Codeforces once again!

After our last two rounds, Yang Liu (desert97) and I (ksun48) are pleased to announce Codeforces Round #492, which will happen on June 24, 2018 at 19:35 MSK. There will be two versions of the contest, one for users in Division 1 and one for users in Division 2. Both versions will have six problems, with four problems shared between the versions.

The round will feature our friend and superstar member of ACM-ICPC team MIT TWO, Allen Liu (cliu568).

The scoring distribution will be visible once the contest begins. As usual, we'd like to thank our wonderful problem coordinator KAN and Codeforces administrator MikeMirzayanov, as well as the rest of the Codeforces staff for keeping this site an amazing place for competitive programming. Thanks also to our testy testers winger, AlexFetisov, and demon1999.

This round is in honor of uDebug who have supported Codeforces on its anniversary. Thank you, uDebug! uDebug is an enthusiastic community of competitive programmers who help each other out by answering questions on chat, providing hints and solutions to problems from several online judges, furnishing test input and sharing feedback. On uDebug, you can select a problem you’ve coded up a solution for, provide input, and get the "accepted" output. You can visit it by the link.

Good luck! As always, we encourage competitors to read all the problems.

(̶a̶l̶s̶o̶,̶ ̶I̶ ̶s̶e̶e̶m̶ ̶t̶o̶ ̶h̶a̶v̶e̶ ̶h̶e̶a̶r̶d̶ ̶s̶o̶m̶e̶ ̶r̶u̶m̶o̶r̶s̶ ̶f̶l̶o̶a̶t̶i̶n̶g̶ ̶a̶r̶o̶u̶n̶d̶ ̶a̶b̶o̶u̶t̶ ̶a̶ ̶s̶p̶e̶c̶i̶a̶l̶ ̶ ̶s̶u̶r̶p̶r̶i̶s̶e̶ ̶w̶h̶i̶c̶h̶ ̶m̶i̶g̶h̶t̶ ̶b̶e̶ ̶h̶a̶p̶p̶e̶n̶i̶n̶g̶ ̶d̶u̶r̶i̶n̶g̶ ̶s̶y̶s̶t̶e̶m̶ ̶t̶e̶s̶t̶i̶n̶g̶,̶ ̶s̶o̶ ̶k̶e̶e̶p̶ ̶y̶o̶u̶r̶ ̶e̶y̶e̶s̶ ̶p̶e̶e̶l̶e̶d̶!̶)̶

EDIT: And the rumors are confirmed! Go to http://codeforces.net/blog/entry/60176 after the contest is over to discuss the problems or voice your complaints along with scott_wu and ecnerwala!

EDIT: Due to some last minute changes, each version will have six problems, with four shared problems.

EDIT: The Div. 2 score distribution is 500-1000-1500-1750-2500-2750 and the Div. 1 score distribution is 500-750-1500-1750-2250-2500.

EDIT: Congratulations to the winners of the round!

Div. 1:

  1. jqdai0815

  2. Swistakk

  3. Um_nik

  4. bmerry

  5. ainta

Div. 2:

  1. Fortin

  2. Aleks5d

  3. KsCla

  4. hopcroftkarp

  5. davidberard

Thanks to everyone for participating! The editorial is available at http://codeforces.net/blog/entry/60217.

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

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

Auto comment: topic has been updated by ksun48 (previous revision, new revision, compare).

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

"a special surprise which might be happening during system testing"

fast system testing!

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

Yaaay

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

I had enough surprises after today's D problem :(

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

Its for me:

)

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

Can't wait to see that special surprise :)

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

Is it on english only or you have russian version of contest too?

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

    All official Codeforces Rounds have problems available in both Russian and English.

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

I heard that, as per this blog post, scott_wu and ecnerwala are going to call ksun48 immediately after the contest for a lively discussion about the contest.

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

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

why the score distribution will be revealed after the contest starts ?

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

I smell math problems.

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

is it rated?

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

How is scott_wu orange in your post? o_O

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

Why the 2 divisions are divided by 1900? Anyway I am glad to take part in Div.1.

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

I want to be the man with the worst contribution can you downvote me please?

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

Amazing email id: [email protected]

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

Will the conditions of tasks in the Russian language?

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

500-1000-1500-1750-2500-2750 not 500-100-1500-1750-2500-2750

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

Div.2 B = 100 points XD

EDT : Fixed

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

swap(C, D);

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

What exactly was the point of having a problem like div1 A which is conceptually pathetic but extremely cumbersome implementation?

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

hello i don't know my word is right or not bud div2 D problem was duplicated. here it's not a classic algorithm like shortest path it's the solution itself!

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

    How to solve this ?

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

      Let's take 3 vectors of length no more then L. Draw them and their negations from one point. Since there are 6 vectors there are two with angle no more then pi/3 between them. Their sum has length no more then L (use Law of cosines to prove).

      Then the solution looks like this: while we have at least 3 vectors, reduce the number of vectors using the statement above. When we have 1 or 2 vectors, it is trivial.

      To restore the answer you should build a tree of dependences and then run dfs.

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

        I had a much simple sol. first calculate x,y taking all vectors positive. Then if x>0&&y>0 then take a vector with xi > 0&yi > 0 and reverse it and calculate new x,y. do same thing in any 4 directions as need until we get required answer.

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

          I don't understand this.

          2
          999999 -1
          -1 999999

          is a countertest, right?

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

        Wow, that's beautiful! However I didn't have such nice ideas, so did simple local search (take 1 or 2 random vector and try negating them) and I think that actually it is rather impossible to make such solutions fail. Do you have any countertests on mind?

        EDIT: I got safe AC in 109ms

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

          What about lot of zeros/small vectors, and several large?

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

            Doesn't seem to be a problem. I even tested my solution locally on such tests. I will have low chance of looking at big vectors but I will also less work to do on them which kinda balances out.

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

              what if 2 vectors 1000000 0 and rest are 0 1. isn't there a chance that the 2 large vectors get never chosen?

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

                There is a chance. But it is something like 0.000000000000000000000000000000000001

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

          Looks hard. Try this:

          #include <iostream>
          #include <cstdio>
          #include <cstdlib>
          using namespace std;
          
          int main() {
          	printf("100000");
          	for (int i = 0; i < 100000; i++) {
          		int y = 900000 + i;
          		if (i % 4 == 1 || i % 4 == 2)
          			y *= -1;
          		printf("20 %d\n", y);
          	}
          
          	return 0;
          }
          
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I think I got it

          20 900000
          20 -100000 (x9)
          repeat 10000 times.

          This is a local minimum if you allow only changes in up to 9 vectors at once.

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

            My solution dealt with your first case using only 23 improvement phases and in second case using only 356 — which is eps. You are welcome to experiment with my code on your own and then tell me about results ;).

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

              Well, can you remove random initialization and run second case?) I don't think that I can do anything against random initialization but I'll try.

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

                Yeah, I agree that this breaks my solution if I remove random initialization of signs. I didn't look at ACed solutions, but there is positive probability that such test will break some of them, if authors didn't wonder about breaking such solution (but maybe they did, I don't know). However luckily my solution contained random initialization and it stands still :).

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

        very nice solution!

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

        Wasn't simulated annealing an appropriate solution? I got a TLE on system test 51, but otherwise it looked fine to me.

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

          What is 'fine'? Can you prove it or something?

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

            By "fine" I meant it looked the right approach to me, before discovering it failed :) I assumed, since the problem asked for "a" solution, not the "best" solution, that an approximate algorithm would do the job.

            Clearly this was not the right thinking! Could you please elaborate what do you mean by "prove" (I assumed the claim that a solution exists assured convergence) and how would you have considered or excluded this kind of solution?

            Thank you very much!

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

              By your definition it is you who should be asked if solution is fine. Did it look the right approach to you?

              It is true that this problem allows some approximate algorithms. If not proving the solution is OK with you — fine.

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

    I thought to start practicing acm.timus.ru, I hope I would have started. Maybe I would have done this problem.

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

maths too hard~~

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

I solved Tesla in a very roundabout way...

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

thanks for beautiful task F

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

Stream starting now! Check out https://www.twitch.tv/ttocs45 to discuss problems and watch tests.

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

[Edited] http://codeforces.net/contest/996/submission/39627469 can someone point out the mistake with this dp implementation of problem E ?

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

Не знаю почему, но мне было намного легче решить задачу С из второво дивизиона, чем задачу D. Чувствую многие со мной не согласятся :D

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

IMHO, some of last rounds really proved that codeforces reduced quality of problems required for contest. Div1A — very easy to solve, very hard and boring to implement. Div1B — super simple and super old classic problem, I would expect it for div2A-B, not even close to div1A-B, div1C — duplicated problem.

Don't know about other problems though.

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

how to host contest :-

randomly select problams from other platform

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

One of the best rounds lately (IMHO), except that Div1C is boyan.

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

I cowarded out of submitting div 1 B and C and then it turned out both solutions were correct

How do you learn to prove greedies?

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

Я не понимаю. Многие решили задачу B двойным циклом. Но хаки не проходят!!!! Как это понять?? 7 раз пытался хакнуть, всего лишь один раз удалось сделать.

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

Despite known C, I really liked the problems. 'maintain sum of numbers in array' for div1D (and which takes 20 minutes to solve) is bold. F is beautiful. I also really liked B, nice easy problem.

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

    Oh, and I hope that E has proved beautiful solution and not my randomized garbage. And that randomized solutions for C will get WA.

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

    Hey Um_nik I didn't get the editorial for Div1D. What's the point of maximising and minimising the xi's. What I get is that there is just some numbers, which are changing in each step, one at a time, and we need to find expected value of them at every stage.

    But what was the point that Allen want's to maximise and minimise and all. Please can you explain...

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

I found B-F questions really nice, but it was totally ruined by that A, to the extent that I did not even take part. Loved the B-F problems though!

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

Is this idea for C correct?

Let the angle between two vector (a, b) the smaller one between (a, b) and (a,  - b)

Case n = 2 is trivial.

If n ≥ 3, then there are at least two vector i and j with angle smaller than 60 degree. And |i - j| or |i + j| will be smaller than or equal to max(|i|, |j|). So we can just add (or substract) these two vector up and we will have a similar problem with size n - 1. We can randomly choose any two vector until we find a pair that work.

I got WA on pretest 6 because I only do the random choice one instead of doing a loop (in a moment of panic), so I don't know if my idea is correct.

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

See this solution for problem B — http://codeforces.net/contest/996/submission/39628153 How is this passing the following testcase without TLE: 2 1000000000 1000000000 Can someone explain?

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

div2.C:toooooo difficult but 1500 div2.D:toooooo easy (than C) but 1750 div2.F:toooooo easy (than E and C) but 2750!!

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

I really think D gonna be a disaster. I am not even sure why my solution passed

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

    For D: my solution was taking the leftmost unpaired person and moving the other person left till they meet. And repeat. I think my algorithm's correct.

    What was yours?

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

      What i did was mapped each element again to some integer like say my array was 2 1 2 1 i made it 1 2 1 2. And then did inversion count. Dont know if its correct

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

    Even I think so. Probably, there will be a lot of failed system tests. Appears too easy to be div2 d.

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

div2C was frustrating.

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

It's not an often case for me when DEF have better ratio points/needed time than ABC :p (especially A which took me longest time XD)

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

can't understand div1.D QAQ

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

For Div 2 B, I failed to hack a solution with the case N = 2 and maximum a[i] values, when it directly simulated the problem situation. Can someone explains how this magician bamboozled me this badly?

P.S. This solution failed when run on the case on my own computer.

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

    haha i even found a similar solution in my room and even his code runs for 1000 1e9s smoothly. weird :/

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

    Same. I tried to hack 39618975 with

    2
    1000000000 1000000000
    

    but the hack failed.

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

      What was the runtime?

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

        717ms only. Looks like Mike has got supercomputers now.

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

        I successfully hacked 3 TLE solutions, so not sure what's up. Could be some C++ optimizations?

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

          http://codeforces.net/contest/996/submission/39617181

          The man passed system testing. How?

          EDIT: Some people keep citing compiler optimizations, but the extent of that should not allow someone with the most naive solution idea to pass system tests (which included max case).

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

            I think the testing machines got faster, and now there is a problem setting proper time limit in order to TLE O(n) complexity. Check out this comment

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

            Looks like compiler optimization also plays some role: I ran this on my laptop with and without -O2, and got 0.8s and 5s runtimes. If I replace the increment of i with increment modulo n (using %), then runtimes are 8s and 10s. So, optimization doesn't optimize as well if there is a % involved.

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

    ksun48 Many people have this doubt. Can you please explain how a 10^9 solution can pass?

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

      This is explained each time a 10^9 hack fails. It's almost always due to compiler optimizations, which can do magic if the operations are not too complicated, AFAIK.

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

        Can you or do you know someone who can elaborate on this? This came as a shock... Any sort of link to any article/CF blog or stack overflow relating to this may also be useful. Please.

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

        This time the ones that get ACs get them with runtimes of more than 800ms, so optimizations seem less likely than faster testing machines.

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

How to solve div 2 B ? I saw alot of bruteforce B that passed pretest

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

    how did the brute force passed....i am also wondering ..

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

    i dont even know .... just watch some pretest passed guy on the leaderboard... alot of them using bruteforce

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

    EDIT: that was about div2 D, sorry

    It's more greedy than bruteforce. If there are k people between two people in a couple, they will need to do do at least k swaps in any case. If you start with the couples for which at least one member is close to the left or right end of the line, you will not be adding distance to other couples.

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

Solution for Div2D available ( https://www.geeksforgeeks.org/minimum-number-of-swaps-required-for-arranging-pairs-adjacent-to-each-other/ )

And the google query to get to this page was "minimum adjacent swaps to pair same elements".

It's ok if there are duplicated ideas, but if they are googlable by such easy keywords it is unfair.

Please take care so that it isn't repeated in future rounds.

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

    That runs in O(2^N) which would TLE since N <= 100

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

    Not the same problem. In the problem, you can only swap adjacent element rather in the link you can swap any two elements.

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

    I guess that problem's a bit different than Div2 D... here the only swaps allowed are 'Adjacent Swaps' but there swaps between any two positions are allowed.

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

    Please take care so that it isn't useless comment in future comments.

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

My solution for div 2 B: http://codeforces.net/contest/996/submission/39614836 Will it fail?

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

Even there is several "strange solutions" for many tasks, thank you for great round ! It was really interesting solving this tasks :)

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

Such a surprise, random system testing!

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

today many div2 b will be failed

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

Even through my rating will go to hell after this round, and issue with A's difficulty and duplicated C, I enjoyed the problemset. Want to see more round where problems requires creative idea like this one on Codeforces in the future.

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

Can someone check my div1-F (didnt solve in time though).

Let dpn, d be a way to pay a subtree with root in n using a set of d different values. It's rather trivially constructed as

If d < n — that's the answer.

Otherwise lets construct Ek — number of ways to pay everyone using exactly k values.

And finally answer is

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

Expert for one day :D rip rating

Really enjoyed the set though :)

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

Your text to link here...

In which hell can these code pass the below test case?

7 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

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

How can a 10^9 solution pass in a sec? This is quite unfair. The simulation takes no thinking and about 2-3 minutes to code and there's no chance of making a mistake. Many people got WA in system testing just trying to do it in the right way. Trying to hack thinking it'll get a TLE and getting "Unsuccessful Hack" is also unfair!

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

The difficulty for me: FBDECA.

It seems the problems are randomly shuffled for me :/

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

    Well, you are very good at math, congrats :)
    F was hard for me, and D wasn't easy.

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

    I bet that F was so so similar to some SRM problem in the past, which also involves the Lagrange interpolation. That's why F is also very easy for me even though I don't remember the exact problem from SRM.

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

So I got accepted in E div1 but couldn't find any submission having the same approach.

My approach is to go from u to 0 to v. Treat u as a fraction p/q, the operations transform (p,q) to (p-q,q), (p+q,q) or (q,p) which are basically operations of Euclid's algorithm. Then I have to pick some q such that applying Euclid to (q*u%p,q) takes less than 100 steps.

I was sure that there are a LOT of q which satisfy the condition, so I chose it randomly. However, can anyone prove it, or at least give a lower bound of number of satisfying q?

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

I somehow managed to get AC on Div2E/Div1C by greedy...

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

    You should count yourself extremely lucky :/ I iterated from 0 to n — 1 instead and got WA on test 76 :/

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

      Yea, I knew there were countertests but was counting on them not adding any starting from the back. Very surprised that all of 105 tests were correct

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

        Yep, I think the system tests could be improved further, but I understand this is a hard problem to write tests for.

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

Can anyone explain to me why the solution for Div2D is what it is. I cant understand

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

    I think there is more than one solution. For example i did O(n)

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

      Can you please explain your solution?

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

        O shit sorry. I thought that solved it O(n) but did (n^2) )))0))0))

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

          Did you do something similar to this — http://p.ip.fi/2xsx.

          I saw tons of code who did something like that. If so can you tell me why its correct? I cant figure it out.

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

            I did the following.

            Consider one pair that needs to be connected. I counted distance between them and added it to ans also i counted number of such pairs that one item of pair lies exactly between choosen pair but outer item lies exactly outside choosen pair and added this value to bad. Result is ans - bad / 2. Think this idea can be improved to O(n * log(n)). But i stucked with formal proof. Very naive intuition is that you extract bad because you do such swap only ones but count it twice in ans. My thoughs was based on well-known fact that number of swaps you need to solve permutation is number of inversions

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

Can please someone tell me how are the solutions that are counting till a[I]-cnt <0 increasing count by one in each step are not getting tle when hacked ? I had two unsuccessful hacks due to this !! Not fair codeforces !!!

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

"a special surprise which might be happening during system testing"

I was really surprised! I have never thought my solution could pass system tests!

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

Crazy contest ToT. I am nearly become candidate master :((

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

I think problem Tesla was very hard

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

In Div.1 C Div.2 E can two vectors have the same x and y

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

http://codeforces.net/blog/entry/58229#comment-419511 — 2nd_places++ (recently also ++'ed on CSA) and still no 1st places anywhere xd

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

Just why geometric when we have a lot of good tags!!??

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

Div2 F/Div1 D is the most troll question on all of CF lmao

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

Is the sample explanation for question E wrong?

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

Can someone prove why this solution passed for Div.2 E? And if not provide a counter case that would disprove this.

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

div1B = Swap Pairing

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

EDIT: wrong contest