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

Автор oversolver, 10 лет назад, По-русски

Привет сообществу CodeForces! Рад сообщить о предстоящем 256-м раунде, который пройдёт для представителей второго дивизиона. Представители первого дивизиона смогут поучаствовать вне конкурса.

Надеюсь, для всех это юбилейный раунд. Для меня же это первый раунд, в котором я являюсь автором, по-этому я буду рад видеть всех. Хочу поблагодарить Gerald'а, который помог с подготовкой контеста, Delinur за перевод условий, и конечно MikeMirzayanov за сам проект CodeForces.

Я сам из Красноярска, а героем задач будет наш незаменимый командный талисман Бизон-Чемпион. Надеюсь, вам понравится провести с ним время:) До встречи и удачи!

UPD. До начала соревнования осталось несколько часов. Стоимость задач будет динамической (подробнее об этом можно почитать здесь).

UPD. Раунд завершился, разбор можно прочитать здесь.

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

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

    Я не понимаю, как это связано с раундом или с автором?

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

      ну типа его комментарий от том что нужно будет в будущем сделать раунд(или что то типа того) и вот мы видим раунд от него!

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

        Извини, но твоя ссылка меня отправило на английский пост и там нету никакого комментария от автора, надо было сюда делать ссылку)

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

Your forgot to say something about the score distribution :)

This famous sentence in Codeforces community: Score distribution will be announced later.

Good Luck.

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

Such a significant round without T-Shirts? How real is this? :)

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

Why not codeforces round (1<<8) :[

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

I hope, for all this anniversary round.

What does this even mean?

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

It's very SPECIAL round! next 2x round will be 256 contests later, it means 256 * 4 = 1024 days, ~3 years!

UPDATE: It's last 2^2^2^2^2... round you will ever seen in your life :( next such round will be 65280 round later, it means 65280 * 4 = 261120 days later, ~800 years. still no T-shirts?

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

Give T-shirts to top 256 contestants who are not unrated ?

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

Again, please take the time to write a meaningful editorial.

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

Надо же, как я удачно потерял в прошлом раунде 2 очка (1701->1699) теперь раунд будет рейтинговым))

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

Oh... A codeforces round by a BUG MAN (oversolver)
God bless us... :D

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

Please don't make the pretests too strong so that hacking is possible .

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

It's a special Round. I think it will be an interesting round.

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

To be honest I was gray for nearly two months.Really upset story... So I just want to be unrated again and see if I can rise up from this new beginnig...

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

    You mustn't create more than one account. See Help.

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

      Yeah,you are right. I am so sorry to the whole CF community. I will turn to that original account :) though it has been gray for more than one month :P

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

        You participated in the round with this fake account . This account should be banned !

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

What happened to CodeForces ? Why the rounds are not beginning from 19.30 ? :( Why all the contests are starting from 18:00, 17:00.. 19:30 was good :)

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

    For some eastern countries 19:30 is not comfortable, because contest ends too late. However I would like 19:30, too)

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

Since this round is sharply before the "NOI" Contest in China, some use their minor account to participate in this round>_<

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

А как размещены задачи в раунде? Они идут по возрастанию сложности или случайным образом?

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

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

hope an easy contest ! :)

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

Top 20 this time around. No doubt about that.

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

From my experience I'm not lucky in dynamic score :(

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

More than 4000 people have registered! Isn't this the highest till date?

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

    Bang! Not exactly. A more ' popular' one is Zepto Code Rush which 4663 participants took part in :)

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

Я конечно все понимаю, но этого я не понимаю! Хреновая какая-то динамичная разбалловка получилась...

500 — 500 — 2000 — 2000 — 3000

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

    посмотрим, что будет после финального тестирования))

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

      Получилось еще интереснее)

      500 — 500 — 2500 — 2000 — 3000...

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

Very interesting problems which cover a lot of fields! And it seems that if you think deeply, you' ll get AC. What a pity that I waste too much time on D( and can' t ensure I' m right) which means can' t think over C and E :)

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

Напишите пожалуйста кто-как решал C(Div 2)?

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

The pretests for the suffix question were too strong ! Not even a single hack

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

in D, shouldn't the problem ask for the k-th smallest number (not k-th largest)?

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

Is it possible to solve C with segment tree? This was my idea:

Find the minvalue of the segment [1-N] and number of elements which are equal to minvalue, lets call it mincount. If, minvalue is smaller than mincount, it is better to brush horizontally. That way we remove mincount of numbers for only minvalue cost. Otherwise, better to do vertical brush.

If we are successful with horizontal brush, then we subtract minvalue from the segment. After that, some elements will be come 0. We the split the segment over the positions of 0 and repeat for the above for each new segment created.

So, perhaps doing this greedy was wrong? I got WA of Pretest 4.

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

    your implementation might have some issues, the greedy strategy is fine :)

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

    I did exactly the same and it passed pretests. By the way, it can be done (and it's easier this way) without segment trees.
    One my friend got WA4 because he didn't repeat the procedure for the rightmost segment created if its right coordinate was equal to the original segment's right coordinate.

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

    Seems like my assumption for using horizontal stroke only when minvalue <= mincount is wrong. Apparently, res = min ( using horizontal brush even when minvalue > mincount, using vertical brush ).

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

Мой решение задачи В не прошло шестой тест. Можете дать тест

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

there was a ghost in the 5th pretest of B! what is the solution of B???

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

No spoiler but please give some idea about intended solution for C and D.

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

    d — binsearch

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

    For D my solution is simple... I tried to devide the whole map into three right triangles, and sort all the numbers between two adjacent triangles... Well it' s a little bit complex to explain the progress( and can' t make sure that it' s correct)

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

can anybody please explain how to solve D.. thanks

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

    General idea is binary search. You need to guess what whether a number X is the kth smallest number in the multiplication table. Hence, you need to count the total number of elements in the multiplication table which is smaller or equals to X.

    On the first row, there are min(X, M) numbers which are less than or equals to X. On the second row , there are min(X/2, M) numbers which are less than or equals to X. Generally, on row i, there are min(X/i, M) numbers less than or equals to X. Compute this number for every row to find out the total number of elements smaller than X.

    With the above calculation, we conduct binary search from 1 to 500000^2 to find the first number which has k numbers smaller than or equals to it.

    Something like 7137779

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

    This problem is a classic problem . It's called Young tableau , you can search it on the internet :)

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

Has anyone see someone hack problem B ? i didn't see a single one

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

thanks for the fast system tests

I am happy to know that B's points became 1000 rather than only 500

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

Финальное тестирование за 2 минуты!Почаще бы так!

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

Changing Score is unfair!!

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

First time in top 20 ;)

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

Добавил в Д для спокойствия иф с выводом ответа, а он оказался не правильным))

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

Найдите 10 отличий!

Вот в этой комнате, между вот этими кодами:

  1. 7127854 && 7136545

  2. 7124532 && 7137613

  3. 7133054 && 7132985

Бонус: Можете насладится чрезвычайно интересными взломами задач А и B этого же участника. Это же надо такие тупые баги в коде допускать по типу "if(n==15) cout<<"NO";"

Серьезно???Никто ничего не сделал, и рейтинг обновили как положено....

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

Simple round but I messed it up big time!

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

Why hasn't the new rating been updated yet?

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

Буква Т-Тормоз: правильно придумал решение C, но затупил в реализации, поставив ноль в неправильном месте. Контест хороший, задачи были интересные.

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

.....So unlucky.....The "Verdict" is "skipped"....The all..

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

    Did you copy and submit someone else's code?Admins will change a user's all submission to skipped if the user cheated in the contest.

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

In problem B I was printing "automation" instead of "automaton". I was not able to debug this during contest :(

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

kindly improve your test cases for PRETESTS. For problem a(that was the easiest problem) i did a blunder still pretests passed. Look at the last line of this code.

if(cup%5==0)
s1=cup/5;

else if(cup%5!=0)
s1=cup/5 + 1;

if(med%10==0)
s2=med/10;

else if(med%10!=0)
s2=cup/10 + 1;

s2=cup/10 + 1; i was supposed to write s2=med/10 + 1; but in hurry i did this blunder. MAIN concern is that this code PASSED all PRETESTS. I think this is harsh. I know my mistake. But still this is really very harsh.

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

    since this didn't pass the system tests, you can't really complain too much.
    PS: this happens, don't get demotivated. u found ur mistake, that's the most important thing. :)

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

As usual, Country wise standings here [Unofficial participants not included]. Hugs and Bugs here.

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

Please make the pretests more comprehensive i.e introduce at least 10 pretests.

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

whats wrong with test case 36: boosss osos output is: both

test case 5: abacaba aaaa output is: automaton i think in test case 5: answer should be "both" instead of automaton my submission id is 7141893 plz correct me if i am wrong.

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

    By applying Automaton you can delete a single char. Now if we apply automaton on abacaba 3 times and delete b,c,b the resulting string will be aaaa. So by applying only automaton we can transform abacaba to aaaa.

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

Why my problem B only submitted once and pretest passed, but my submission was skipped?

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

I receive a TLE from my D solution. I have no idea how to make it better. Who can help me on the problem? My submission in the match: 7137602 I improved it later, but still TLE 7138146

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

    Oh, I have realized there is something wrong in my binarysearch, which leads to an endless iteration.

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

There are a lot of unrated participants in the top of the rank list again ! I think codeforces must have some rules like this : "Unrated persons cant take part in Div2 only contests."

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

Edit: I wanted to comment this in round 257