awoo's blog

By awoo, history, 7 years ago, In English

Hello Codeforces!

On August 21, 18:05 MSK Educational Codeforces Round 27 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

The round will be unrated for all users and will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Ivan BledDest Androsov, Vladimir vovuh Petrov, Mike MikeMirzayanov Mirzayanov and me.

Good luck to all participants!

Harbour.Space also has a word for you:

We are delighted to welcome the 2017 ACM-ICPC World Champions, ITMO, to our 2nd Hello Barcelona Programming Bootcamp in collaboration with Moscow Workshops ACM ICPC starting September 27.

All the top Russian teams are coming, including St. Petersburg State University, MIPT, Ural Federal University, Tomsk, Novosibirsk, Saratov and Perm, as well as the world’s top universities such as Waterloo, Central Florida, Hangzhou Dianzi, Singapore, KTH and dozens of others — so far teams from 30 countries have signed up.

The event’s gold sponsor is Sberbank, the biggest commercial and investment bank of Eastern Europe and Russia. Thanks to their support we expect that the top participants will be awarded valuable prizes, alongside high-profile internship and job opportunities.

We can’t wait to see all of you coming to learn, practice and compete on the international stage, smoothing your road towards April World Finals in Beijing.

Ps. Registrations close on September 1.

UPD: Editorial is published

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 uwi 7 288
2 quailty 7 314
3 Andrei1998 7 318
4 rajat1603 7 374
5 fatego 7 374

Congratulations to the best hackers:

Rank Competitor Hack Count
1 uwi 455:-11
2 halyavin 305:-4
3 STommydx 103:-2
4 Lhtie 48:-2
5 step_by_step 44:-28

1326 successful hacks and 300 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A ksun48 0:01
B ygmngm817 0:03
C markysha 0:03
D EKGMA 0:10
E halyavin 0:37
F eddy1021 0:34
G const_int_magic 0:08

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

| Write comment?
»
7 years ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

why is the Announcement too late?

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

I want nothing but a clear problem set.

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

Is it rated?

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

    Lucky for you, it is!

    "Educational rounds" are a GREAT way to increase your rating!

    I wish you high rating in every upcoming educational contest!

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

What is high-profile internship?

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

"After the exam Polycarp can justify his rule violations by telling the driving instructor that he just didn't notice some of the signs."

Unfunny meme amirite

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

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

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

How to solve E and F?

Is this a valid approach for E:

2D ternary search to find the placement of the (k + 1)th center of ignition and then binary search to find minimal time. The complexity will be which is about 300 mln operations and should fit in TL. The only thing I'm curious is if the ternary search will be correct.

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

    for E
    Consider binary search on answer
    Find leftmost line which will have atleast 1 unvisited cell , similarly find rightmost , topmost line and bottom-most line
    This is valid if (right — left) <= 2 * x and (bottom — top) <= 2 * x if we are checking for x.

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

      How to find leftmost line and other 3? You find leftmost of these k burning points, and then k — x but problem is if k — x < 0, i mean if that point is pretty close to left border.

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

    for F If N > M just transpose it
    So now N ≤ 15 , so just do dp with bitmask

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

could anyone explain to me the first test in D ?

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

I got WA at Test Case #8 in problem D. Couldn't figure out why?

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

    When you get new speed of car, you cant only check last speed limit. You need to have stack with speed limits. Example you have signs with speed limits of 100,120,150 respectively. Then , you drive 160 and you only check last speed limit which is 150. But you also must care about signs 100 120. So , maintain a stack of speeds, go back while speed.top() < curr_speed and increase counter. You can see my solution at my profile.

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

      So by that, you mean with this test case

      4 1 50 3 50 3 100 1 60

      The ans 0 instead of 1? Could you explain to make more sense to me or point out which part of the problem exactly define this criteria? Thanks

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

        Of course answer is 0, how can it be 1? You drive 50 while limit IS 50 so its OK, then you switch to 60 while limit is 100, thats OK as well.

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

          I mean when the speed limits are 100, 120, and 150, and you drive 160, the 100 and 120 is included in the violated signs, right?

          But, why when the speed limits are 50, 100, you drive 60, the 50 limits doesn't noticed too (unlike above)?

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

            Never mind, I've understood it. Thanks anyway

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

problem G is this with Q = 1

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

4

1 100

3 50

3 50

1 50 why is the ans 2

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

    You only need to remove (or "didn't notice") two road signs to drive without violation

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

      even 1 can be the ans because after the second sign he changed the speed!!

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

        Yeah, I agree that one is more make sense. But, I've clarified similar question to the problem setter, see below.

        Question: 3 1 100 3 50 3 50 The ans is 2

        Question: 3 3 50 3 50 1 100

        The ans is 2

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

    Because you are passing two signs with maximum 50 with speed 100.

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

how to solve G ?

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

    If there is a cycle in the graph with cost C, for every path of cost x, there is one with cost x^C.
    So you can check out all the costs of simple cycles (get a spanning tree and check for each edge) and the shortest paths will be x^C1^C2... where x is the cost of any route you can find.
    To find the minimum of this value we can translate the problem to linear algebra, the XOR is the same as the addition in Z/2 space, so if we treat these costs as a vector, then we can find a linearly independent set which generate these vectors in the ZMXBITS/2 linear space using gaussian elimination.
    Now we can simply get any distance from 1 to n, and XOR with the elements of the basis greedily from the most significant bit to the least.

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

      what do you mean by "Z/2 space",please?

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

        The Integer modulus 2 vector space

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

          Is this advanced usage of linear algebra or some bacics? Are problems where u need to use linear algebra conceptually hard (for example this one) or, when u learn linear algebra, its natural after some thinking? Because when I see linear algebra im like wtf who can come up with solution for this

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

      Can you please explain me one thing....i understand that gaussian elimination method for minimising xor value but how can we say that number of simple cycles will be atmost 30...because gaussian elimination will take n^2logn(rows=n columns=30 bits)..

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

Alert!!! Alert!!! UWI started hacking!!!

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

    How can he hack so fast? Just because he is on the leader board of HackerRank?(joking)

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

    When you have more successful hacks than penalty!

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

Anyone could kindly explain why Wrong Answer on Test Case 8? Thanks

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

    in case if t==3 you might be changing previously increased speed in query 1 to -inf and than you pushed the speed limit in stack;

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

    Try this test case-
    5
    1 80
    3 120
    3 130
    3 140
    1 150

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

Can anyone tell me how there are this many solutions for G? I saw solution uses linear algebra. Isnt it really advanced topic for competitive programming? Anyone has any materials with codes for linear algebra?

Problem E is much easier in my opinion, but has less AC. Also, this is maybe the case because problem G appeared on codechef before (in even harder version).

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

4 1 100 3 50 3 50 1 50 who agrees with me that the answer should have been 1??

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

    No one. You drive with speed of 100. You see a sign with limit 50, you dont give a shit, so res++ You see one more sign with limit 50, you dont give a shit again, res++

    Totally, you must lie about 2 signs, because you didnt slow down TWICE, not ONCE. Result is therefore 2.

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

      the second time i see it and change the speed!! i could just say that i didnt see the first sign but as soon as i saw the second one i changed the speed after that!

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

        He changes the speed only when there is a type 1 event, otherwise he keeps the same speed.

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

          ok so is it like this that i should change my speed before the next speedlimit sign comes?

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

            Yes, exactly.

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

            Yes. When type 3 appears, it means you already passed sign with given limit. So you need to change speed BEFORE you see a sign.

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

    If you eliminate one of the speed signals you are left with 4 1 100 3 50 1 50 which is still a violation of the rules (when you cross the 50 limit you are travelling at 100). You need 2.

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

Why there's no sample explanation in problem A,B,C.

Thinking a harder version of the easy problems took up most of my time just because I misunderstood the problems!

:(

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

    Or maybe I'm too careless.....

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

      Careless I would say xD I solved first 3 problems in half an hour. This is my best contest ever (place 212. and you see how bad my rating is). So, If u just read carefully...

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

Help me, please!

Here is my program for problem D: http://codeforces.net/contest/845/submission/29666261. I tried to solve it using the vector of speed limits. But I get "Wrong_Answer" when the number of events was great.

Can you, please, tell me what I'm doing wrong.

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

Almost everone solved problem G in same fashion ( finding basis and all ), is this some standard method for dealing with this type of problems? can anyone give any link to some theory and more problems on it.

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

Me Right Now..

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

7 1 20 2 6 4 6 6 2 In the third example Polycarp should say he didn't notice both "no overtake allowed" that came after "overtake is allowed" sign. Any explain for me? I think it doesn't makes sense.

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

    If he doesn't say that, then the last overtake would violate the rules (he overtook another racer when overtakes weren't allowed)

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

Now its halyavin.. :3

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

Can someone provide a test for which this doesn't work? http://codeforces.net/contest/845/submission/29651836

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

Full test cases are visible even when 24 hour hacking phase is running, but they should not be visible.

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

Could someone point out where my code for problem-D is giving error? Link is https://www.ideone.com/VjSB5c Thank you.

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

    It's not enough sometimes to delete the previous sign. For e. g. if there is a speed limit sign of 50, then a speed limit sign of 30, and after that he goes with 100 speed, then in your code he only has to say he didn't see the 30 sign, but then he should think the speed limit is 50, so he is still speeding.

    Also you don't reset the speed limit after deleting a sign, so if there is a 30 sign, he goes with 50, then he goes with 70, then you add 2 to ans instead of 1.

    Solution: