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

Автор vovuh, история, 9 месяцев назад, По-русски,

<almost-copy-pasted-part>

Привет! В 30.08.2019 17:35 (Московское время) начнётся Codeforces Round #582 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.

Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу PikMike Пикляеву, Максиму Ne0n25 Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.

Удачи!

Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.

</almost-copy-pasted-part>

UPD: Спасибо Артему Rox Плоткину за тестирование раунда!

UPD2: Разбор опубликован!

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

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

[deleted]

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

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

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

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

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

      Why are you being mean?

      You are not even blue yet LMAO

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

        In my real account my raiting is 1700+

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

          No one cares..

          Just learn to be nice to people

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

            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

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

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

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

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

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

    Raiting does not matter, matter only nice girls!

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

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

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

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

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

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

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

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

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

I hope that rating Will increase somehow.

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

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

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

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

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

Vovuh's rounds are always good!

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

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

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

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

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

The contests that you created is really good <3 Thank Vovuh.

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

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

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

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

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

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

First unrated contest for me. XD

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

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

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

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

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

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!

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

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

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

    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.

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

    Yep

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

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

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

Let's escape this division guys! :D

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

Finally, not a Mathforces Round.

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

Whoa LGM and all around god Benq is writing this Div 3 contest :O

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

P.S Here was bad info

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

D2 solution accepted with 1900ms

Me: heavy breathing for 14 hours

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

Ооочень хороший кантест спасибо!!

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

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
  • »
    »
    9 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

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

    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.

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

    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?

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

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

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

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

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

thanks Vovuh, it was cool contest.

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

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

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

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 ?

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

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

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

    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)

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

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

Shouldn't my solution be NlogN?

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

G — кайф, С — не кайф

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

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?

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

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

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

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

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

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

    this line needs to be

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

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

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

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

 Sad for him :(((

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

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

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

Problem E :

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

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

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

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.

»
9 месяцев назад, # |
Rev. 4   Проголосовать: нравится -9 Проголосовать: не нравится

русский Я очень люблю раунды Vovuh. Спасибо! 1213E - Two Small Strings удивительно.

Ελληνικά Μου αρέσουν πολύ οι γύροι Vovuh. Ευχαριστώ! 1213E - Two Small Strings είναι εκπληκτικό.

English I really like the rounds Vovuh. Thanks! 1213E - Two Small Strings is amazing.

Español Realmente me gustan las rondas Vovuh. ¡Gracias! 1213E - Two Small Strings es asombroso.

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

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?

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

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

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

Очередной настоящий, качественный educational раунд для div3. Спасибо!

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

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