vovuh's blog

By vovuh, history, 2 years ago, translation, In English

<almost-copy-pasted-part>

Hello! Codeforces Round #582 (Div. 3) will start at Aug/30/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

UPD: Thanks to Artem Rox Plotkin for testing the round!

UPD2: Editorial is published!

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

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

[deleted]

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

I hope I will get some positive rating from the contest.

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

    YOU WILL NOT!!!!!!!!!!!!!!! I AM SURE THAT AFTER 5 CONTESTS YOUR RAITING WILL BE BELOW 750!!!!!!!!!!!!!!!!!!!!!1

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

      Why are you being mean?

      You are not even blue yet LMAO

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

        In my real account my raiting is 1700+

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

          No one cares..

          Just learn to be nice to people

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

            I am just trolling in all my comments(not in posts).my small contribution can proof this. But this comment is not trolling and is true

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

First,div3 after becoming expert hope my rating remains constant.

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

    your rating will remain constant because div.3 is unrated to experts and higher like you and me.

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

    Raiting does not matter, matter only nice girls!

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

Now I can say "I won't lose my rating ANYWAY!" proudly :D

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

    Now I can say "I won't gain any rating ANYWAY" sadly :(

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

This will be my first contest. I hope I will do well and good luck for everyone for the same....

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

Hope the ranking of problems be better from the last contest.

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

After this contest,I think I will be a expert.How excited I am!

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

I hope that rating Will increase somehow.

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

Vovuh...master of preparing div3 contests...

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

My Final exam is going on... But I won't miss div-3.. Div-3 is love..

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

Vovuh's rounds are always good!

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

Div 3 rounds are better than "Educational rounds" in teaching the most valuable skill for Codeforces, namely SPEED.

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

    Depending upon what your purpose. If you have high rating is seem not :)) But I like Div3 rounds too :3

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

Hopefully we will get some interesting problem. And always thanks to vovuh from arranging div3. Its always increase my rating. :)

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

Hopefully I will become back to expert soon. I have been very disappointing in myself recently.

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

First unrated contest for me. XD

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

Hello,Guys. This is my first contest after a lot of time. I studied Quantic Math in this period. I think that I can beat majority of the Div3 contestants even tough I am at 1361. :)

Letsssssss GOOOOOOOOOOOOOOOOOOOOOOOO

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

    LoOooOoOLoOOooOoLoOOoOoOOooOooOOLoOooOOoOOoOOL. ROFL. LMAO. You think majority of contestants can only solve less than 3 problems?

    ↑that's just bullshit

    All the best. The time I solved 5 problems I didn't really expected that. it was pure luck. one lucky contest will be enough to bring you up to specialist or even 1500+. Good luck and have fun! :)

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

Note that this is vovuh's round. It's likely to have problems with multiple queries. So guys, a notice for you, remember to clear the data of the last query before answering the queries!

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

Do I have to register to join this contest? (My current rating is under 1600)

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

    Of course. You have to register if you want to take part in a contest. For those rating equal or more than $$$1600$$$, they will be registered "Out of competition" for Div.3 contests. That is, their rating will remain unchanged after the round and they won't be listed in the official standing board.

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

      Alright, thanks for the information

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

    Yep

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

I have a great idea! Make div3 rated for (blues,) purples and yellows but update ratings only if the delta is negative.

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

    Why don't do the same thing to blues? They are unofficial for div.3 as well :(

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

      sorry, I thought blues are also div3.

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

Let's escape this division guys! :D

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

Finally, not a Mathforces Round.

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

P.S Here was bad info

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

D2 solution accepted with 1900ms

Me: heavy breathing for 14 hours

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

Unofficial editorial by me.

A (Chips Moving)

Explanation
Code

B (Bad Prices)

Explanation
Code

C (Book Reading)

Explanation
Code

D (Equalizing by Division)

Explanation
Code

E (Two Small Strings)

Explanation
Code

F (Unstable String Sort)

Explanation (grindy)
Code (grindy)
Explanation (nice)
Code (nice)

G (Path Queries)

Explanation
Code
  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Is this official editorial? I am confused why its not part of the post.

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

    Your implementation of G has failed on a test in which function find makes $$$O(n)$$$ recursive steps. I believe it would be better to use rank heuristics here.

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

    In G, can you please slightly explain more what are components of edge and how are we merging them with a small walkthrough of an example?

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

    what about self loop in E?you are not considering it

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

You should've seen my face when I found the "error";

wrong submission: http://codeforces.com/contest/1213/submission/59756421

good one: http://codeforces.com/contest/1213/submission/59757102

hint: I removed the second if

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

thanks Vovuh, it was cool contest.

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

Hopefully I go back to blue after open hacking is done!

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

How does my D2 pass in time ? 59740108.

Isnt the complexity O(2*10^5 * K * log(K) ) while iterating the map since maximum numbers in map can be 2*10^5.

Am I missing something or are the test cases weak ?

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

    Heh. I'm TLEing when I really shouldn't be.

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

    No, your complexity analysis is wrong. The total number of elements across vectors in the map is at max Nlog(a[i]). So, you can say that your amortized time complexity is O(Nloga[i]logN)

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

Can anyone tell me why this Java solution for D2 is TLEing?: 59748534

Shouldn't my solution be NlogN?

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

In B i accidently took array smaller than the limits so i tried to hack myself and i can't hack it can anyone help me?

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

    Difficult to hack, only hackable if those memory locations are assigned next to OS memory locations. Keep trying :P

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

Can anyone tell me why my problem G TLE? I think it is O(N + M) (assuming that dsu operation is constant). Is there any infinite loop possibility?

59762107

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

    return (pr[x] == x ? x : root(pr[x]));

    this line needs to be

    return (pr[x] == x ? x : pr[x] = root(pr[x]));

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

      omg :( silly me

      Im actually used to code it like this

      return pr[x] = (pr[x] == x ? x : root(pr[x]));
      

      thank you XD, i think im just too tired right now..

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

 Sad for him :(((( be hacked 4 problems :<<

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

    Will those hack tests be included in final tests? What if my code fails in one or more of them?

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

      Yes, if you not pass all test, you will be hack. =)))))))))

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

      He is trolling lol. if your code fails in one of them, you get WA!

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

Problem E :

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

Solution for F

if d occurs at i position in a and j position in b then it can be said that
s[min(i,j)]=s[min(i,j)+1]=.......s[max(i,j)] make an array of intervals and add every [i,j] in it
sort the array
now merge the intervals which share common index
if length of the interval array is less than k then it is NO
else
if length of the interval is greater than 26 then merge all intervals from 26th index

assign letters from a to each interval
now sort intervals on the basis of their position in A.done AC

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

Why the following brute force solution for D1 gives WA in test 5. https://codeforces.com/contest/1213/submission/59764056. Can someone have a look.

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

русский Я очень люблю раунды vovuh. Спасибо! 1213E - Две маленькие строки удивительно.

Ελληνικά Μου αρέσουν πολύ οι γύροι vovuh. Ευχαριστώ! 1213E - Две маленькие строки είναι εκπληκτικό.

English I really like the rounds vovuh. Thanks! 1213E - Две маленькие строки is amazing.

Español Realmente me gustan las rondas vovuh. ¡Gracias! 1213E - Две маленькие строки es asombroso.

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

59776311

I try to use Golang to solve Problem B and complexity is O(Tn) but I got TLE. Can someone help me?

Maybe Huge IO?

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

This summer vacation I'v joined lots of cf's contests. before the new term , I wish I could be an 'expert'.

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

I submitted this code for the D2, got a TLE in the 5th case. Can anyone help. (For all possible numbers, I recorded the numbers those could be formed from the original numbers of the array and the operations required for the same, rest is self explanatory)

https://ideone.com/PKClD9