ksun48's blog

Codeforces Round #492 [Thanks, uDebug!]
By ksun48, 6 years ago, In English

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.

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

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

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

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

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

fast system testing!

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

    Don't get your hopes up...

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

    maybe pretests = systests, so there is no system testing and nobody fails :)

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

      Yeah, and get 50+ pages queue during the round, would be nice.

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

        Then we will also have a special surprise during the whole contest.

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

          Maybe if you have passed pretests but failed systests you'll have half points for the problem.

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

        Of course not, Codeforces servers are too good!!!! Then can handle up to +10000 online judges at the same time... LOL, yesterday I could'nt even enter the problemset, because servers were so busy.

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

          It seems that when the comment is hidden, people are more likely to read and downvote...

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

            It seems sometimes people downvote just because the colour of your name isn't good enough!

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

              Here Downvoting is inversely proportional to your ratings

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

            it's like a self-fulfilling prophecy. The website says the post got negative feedback, so it gets more negative feedback.... lol

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

      Then there's no systest so there's maybe also no such 'during' system testing ? ;)

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

      Or maybe the surprise is that there are no/weak pretests o_O

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

        Or maybe there will be so many failed solution on SysTest

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

Yaaay

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

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

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

Its for me:

)

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

Can't wait to see that special surprise :)

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

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

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

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

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

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.

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

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

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

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

I smell math problems.

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

is it rated?

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

How is scott_wu orange in your post? o_O

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

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

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

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

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

Amazing email id: [email protected]

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

Will the conditions of tasks in the Russian language?

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

Wael.Al.Jamal

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

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

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

Div.2 B = 100 points XD

EDT : Fixed

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

swap(C, D);

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

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

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

    yep

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

      He is talking about Div1 A not Div2 A

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

        damn. div1 a/ div2 c was hell. I wonder if I'll be able to sleep peacefully after seeing it.

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

    I didnt think it was that cumbersome, just implement a rotation.

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

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!

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

div1C = http://acm.timus.ru/problem.aspx?space=1&num=1130&locale=en

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

    How to solve this ?

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

      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.

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

        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.

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

          I don't understand this.

          2
          999999 -1
          -1 999999

          is a countertest, right?

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

            you just take both of them as it is. 999998 999998 is a valid answer.

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

              Oh, I'm stupid

              Then repeat both vectors two times.

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

                my bad. I think i've actually missed some cases. probably it won't pass sys tests.

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

        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

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

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

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

            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.

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

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

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

                There is a chance. But it is something like 0.000000000000000000000000000000000001

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

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

          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.

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

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

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

              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.

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

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

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

                  Congrats on this :)

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

        very nice solution!

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

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

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

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

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

            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!

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

              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.

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

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

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

maths too hard~~

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

I solved Tesla in a very roundabout way...

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

thanks for beautiful task F

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

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

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

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

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

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.

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

how to host contest :-

randomly select problams from other platform

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

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

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

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?

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

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.

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

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

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

      For C, I random shuffled the vectors and choosed them greedily. Passed at 77 ms.link

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

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

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

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!

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

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.

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

    I did a very simple solution: greedily choose the sign, which gives the smallest radius at the current moment. I see that a few others also did a similar approach, for example, jqdai0815

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

      3
      1000000 0
      0 1000000
      600000 -600000

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

        the greedy gives -1 1 1, isn't this correct?

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

          what if it gives 1 1 1?

          chosing 1 at beginning and -1 gives same radius.

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

          OK, there you have free choice for second

          3
          100000 0
          -1 1000000
          600000 -600000

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

      I thought this solution wouldn't work?

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

        It shouldn't work. It gives WA 26 when sorting the array from largest to smallest, so there is a countertest like 26 but sorted

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

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?

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

    I completely agree. How this passes I do not understand. In my room a lot of people solved the problem in a double cycle, but no one could hack. It cost me a lot.

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

    I tried to hack this solution https://codeforces.net/contest/996/submission/39614615 using above testcase but it gave unsucccessful hacking attempt.

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

    Also I tried this testcase on my PC. It is taking easily 3-4 secs. Don't know what is happening here.

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

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

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

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

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

    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?

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

      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

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

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

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

div2C was frustrating.

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

    I think so too. I based my observation on this tc.

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

    After finish debugging my solution for Div 2C. The contest is over. :)

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

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)

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

can't understand div1.D QAQ

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

    Ya that was a pretty easy problem but I didn't get the problem statement so couldn't do it.

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

    It would have been much clearer if they explained 1st test case.

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

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.

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

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

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

    Same. I tried to hack 39618975 with

    2
1000000000 1000000000

    but the hack failed.

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

      What was the runtime?

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

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

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

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

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

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

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

            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

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

            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.

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

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

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

      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.

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

        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.

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

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

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

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

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

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

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

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

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

    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.

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

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.

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

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

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

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

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

    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.

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

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

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

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

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

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

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

Such a surprise, random system testing!

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

today many div2 b will be failed

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

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.

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

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

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

    I'm not sure if it's correct, but shouldn't the answer then be ?

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

      Yes. Got lost moving from my writings to latex

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

        Intuitively the solution looks correct and also Lewin's solution is the same. So I guess it's correct.

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

Expert for one day :D rip rating

Really enjoyed the set though :)

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

Your text to link here...

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

7 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

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

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!

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

    I got 2 unsuccessful hacks due to very fast custom testing computers I guess.

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

      Is not this the same surprise that they promised?

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

    it wont be 10^9, if it is a big number then you keep taking 100's and there can be atmost 10^7 of them

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

    Interestingly, some of them do fail with a TLE. That's probably not what the writers intended to happen, and it should be taken into account for future rounds.

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

      Interestingly this bruteforce submission gives TLE : 39630584 and this passses : 39630937

      only difference is that % operator isn't used in the second one.

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

        Very interesting, indeed.

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

The difficulty for me: FBDECA.

It seems the problems are randomly shuffled for me :/

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

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

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

    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.

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

      I think it's a very classic problem. I have seen tons of similar problems.

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

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?

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

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

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

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

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

      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

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

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

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

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

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

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

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

      Can you please explain your solution?

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

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

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

          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.

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

            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

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

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

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

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

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

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

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

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

I think problem Tesla was very hard

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

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

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

    Yes , Why not ?

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

      no i just want to know the answer for

      n = 100000

      and all vectors are x = 1 y = 2

      Edit : after asking ksun48 it showed out that problems are allowed to have multiple answers.

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

        there are many solution one of them is -> 1 -1 1 -1 1 -1 ......

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

          thats why I asked this question there is some AC gives only 1 for this test

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

    in the first example there are two vectors have the same x and y XD

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

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

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

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

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

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

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

Is the sample explanation for question E wrong?

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

    Yeah, we're wrong, it should be 1->2->3. We just fixed it.

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

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

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

div1B = Swap Pairing

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

EDIT: wrong contest

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contestInvitation/7b43f1bdfe15913f2ead227129417cbfa2fa08ee Залетайте!

→ Reply