Блог пользователя danilka.pro

Автор danilka.pro, история, 9 лет назад, По-русски

Здравствуй, Codeforces!

Меня зовут Данил Сагунов, и когда-то я был красным... Впрочем, поздравляю всех со Второй Революцией!

Рад сообщить, что в эту субботу, 3 октября в 19:30 MSK состоится Codeforces Round #323 для обоих дивизионов. Задачи для вас придумывали и готовили я и Виталий gridnevvvit Гриднев. Это не первый раунд, в котором мы являемся авторами, и я уверен, что не последний.

В подготовке задач нам помогали мои друзья Максим Neon Мещеряков, Владимир vovuh Петров и Роман Roms Глазов, за что отдельное им спасибо. Благодарю Макса Zlobober Ахмедова за координаторскую деятельность, Михаила MikeMirzayanov Мирзаянова за создание и поддержку систем Codeforces и Polygon, благодаря которым проведение раунда стало возможным, и Марию Delinur Белову за перевод условий задач на английский язык.

Спасибо Владиславу winger Исенбаеву и Александру AlexFetisov Фетисову за прорешивание задач раунда!

Участникам обоих дивизионов будет предложено по 5 задач и 2 часа на их решение. Надеюсь, задачи покажутся вам интересными, а многие из вас сумеют вернуть свой цвет.

UPD В e-mail рассылке была указана неправильная продолжительность раунда. Соревнование будет длиться 2 часа.

UPD2 Раунд успешно завершен! Благодарим всех за участие.

Поздравляем победителей первого дивизиона:

  1. ecnerwala
  2. ikatanic
  3. uwi
  4. PavelKunyavskiy
  5. sd0061

И второго дивизиона:

  1. wrong_order
  2. ahwhlzz
  3. kefaa

Мои поздравления fotiIe96, единственному решившему задачу D!

UPD3 Разбор можно найти здесь

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

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

Автокомментарий: текст был обновлен пользователем danilka.pro (предыдущая версия, новая версия, сравнить).

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

Наконец-то Div1... Хотя для меня это уже значения не имеет :)

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

Предвидится новый рекорд по числу зарегистрированных пользователей)

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

used to be red :(

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

    I_love_Tanya_Romanova changed his bio on Quora to "Red on Codeforces" from "Winner of SEERC, ACM ICPC finalist" :D

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

      He participates at SEERC, not NEERC

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

      You are wrong — I didn't make any changes in last several days :) These bios are topic-wise, and I had red at CF/TC for CF and TC topics for a long time (while SEERC-related stuff was used for topics like "competitive programming" and "ACM ICPC").

      I still think that winning SEERC is not as easy as getting red, even after recent changes — at least you need some good team for SEERC, while for red CF color only your skill matters. Plus you have to solve harder problems :) Maybe our region is not as strong as NEERC, but still you have to compete against other reds...

      And I really like these changes — we'll see how it will work out... But right now it added value to red color. Now I have decent chances to lose it soon, while it sounded much harder several days ago :)

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

      Warm Up ACM ICPC finalist :D

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

        He is so humble, that most people don't appreciate him. I know he mostly says that he is not a genius, that he is not like those other guys who can reinvent an algorithm on the spot in a competition, but it hurts to see people interpret his humility as otherwise. He is damn talented. He is damn hardworking. And he is a very nice person. So please don't say things that seem like you're making fun of him. He under-speaks his achievements. But you shouldn't.

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

        Not Acm Icpc finallist,warm up for regional acm icpc.

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

    In which revolution?!

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

To be honest i don't like previous gridnevvvit's round . Mostly problem statements are not clear at all , non russian speaker like me had a real tough time on those rounds . But i must admit there is tremendous change in recent some Rounds . Problems statement are clear now with explanation . Hopefully it will continue . Recent change on Codeforces make both Div 1 & 2 more interesting . Eagerly waiting to see how rating will change after this round .

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

When half of the people who prepared the round are Div 2...

Anyway, I am an optimist about the new system. The distribution will get better in time.

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

my first palindroom contest!

good feeling :D!

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

Someone dare to ask "Which one is harder, becoming red on Topcoder or Codeforces " .

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

    A lot of reds have been saying its much easier to become red on CF, than being red on topcoder. MikeMirzayanov had a fitting reply to that, and most reds lost the color. So sad.

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

Will this round follow the new rating formula developed by Mike and his team?

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

Michael MikeMirzayanov Mirzayanov :D

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

Tomorrow first day at university & contest round #323 ^^ Hope good rates :)

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

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

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

Я испытываю смешанные чувства при виде div1-раунда, который готовили один едва-едва оранжевый участник и четверо сине-фиолетовых. Чёртова революция...

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

Good luck to everyone!

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

First contest with new colors.. Hope this will brings us luck:)

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

Blue to Cyan....:-( But it looks really inspiring :-)

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

Back to the original color? I don't think it's a good news for tourist,Petr,vepifanov and rng_58.

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

Last Challenge was not that tough...Hoping for best for this challenge

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

More people in Div 2. Nice.

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

Хахахаха а я хотел на этом раунде стать фиолетовым(оставалось 25пт). Не судьба видимо!

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

Wow, only about 600 participants in div.1, the pressure is real :D

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

My new handle : I_lost_my_color

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

div 1: 600 div 2: 6000

6000 / 600 = 10 :) I love this numbers :)

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

Welcome back guys :D

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

Now there's no need for some of div1 users to make fake accounts to participate in div2 contest :D

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

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

I think this is the first time where div2 contest will be much challenging than div1. :P

Good luck everyone and may the best return to div1. :D

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

fight for being in div-1 got more interesting .

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

CRASH!? Or was that only with my computer/internet?

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

Отчего весь этот шум,
Отчего весь этот гам?
Одно идет мне на ум:
Похоже, сервер упал...

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

    песенка, которую до сих пор подпеваю. Ах как давно это было, ЛКШ:).

    P.S. вот ссылочка для тех кто не в теме — тыц

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

    да Вы прям поэт, я так посмотрю.

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

    на этот раз стишок не очень.

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

delayed ??? server is busy ??? what the **** ???

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

I should never expect Codeforces round starts on time. T^T.

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

Sever is too slow -_- hopefully it will be okay during contest time :)

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

I hate delay :|

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

Похоже сегодня будет горячо на контесте. Набежит over 100500 народу жаждущих веруть себе цвет/дивизион/уважение.

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

Is anyone else unable to access CodeForces at times right before a contest? I don't pretend to know the reason for this, but if the servers do not handle such large amounts of participants well, then we can start a Kickstarter or Patreon to fund for server upgrades. I'm sure many of us wouldn't mind giving a [insert monetary unit] or two for this project.

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

Scoring?

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

WOW!!!RECORD registered to Codeforces Round #323 (Div. 2) 7313:)

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

Am I the only one waiting for score distribution ??

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

8000 participants, nice. Was even 7000 reached before?

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

Увидел задачи

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

Задачи скучная математическая фигня. В следующий раз сделайте вместо задачи главу из учебника физики Ландау и Лифшица

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

How to solve Div-2 D

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

    I think we must find all flat parts in region [1,2*n]. Then do LIS in n^2 for each point and see if LIS upto this point+(t-2)*flatpart of this point is the highest

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

    My idea(which didn't pass pretest 2) was to split the problem into 2 cases:

    If T<=250, then just run LIS algorithm and get the answer.

    Otherwise, run the LIS algo on the first n * 250 numbers and get the sequence. Then pick some number close to the end(but not quite at the end): this is your "capped" value. You then treat the other T-250 periods as if the only numbers we selected in them were occurrences of this "capped" value. Then on the last period you can select higher numbers or whatever. This is probably wrong though :P

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

      This isn't wrong, I solved it like this.

      If T<=200 just solve with LIS. Else:

      For each different value v in the initial sequence, do a LIS in the first n*100 values which only considers values <= v. Then, just repeat v for the middle n*(t-200) numbers. Finally, run LIS for the last n*100 numbers considering only those >= v.

      It's pretty fast.

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

    Let us define a graph with 300 nodes with weight of edge (i, j) denoting the length of lis starting with beginning value (not the index) being i and ending value being j.

    Now, we want to find a maximum weight walk in the graph of length T. This can be done by matrix exponentiation.

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

      will this work in 1sec ?? . Complexcity of your approach will be (300*300*300)*log10^7 .

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

        Yes, I did make it work in time. You can check my submission.

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

        Notice that you may compress coordinates, it doesn't modifies complexity but will improve your speed by a big factor 3^3 = 27, so your code will be 27 times faster. BTW, My solution was O(n^3)

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

    If T <= 5000, then find the LIS for the A x T array by nlog(n).
    Else, find the answer for s1 = A x 5000 and for s2 = A x 5001, then X = s2 — s1.
    Result is s1 + (T — 5000) * X;
    13386622

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

Задачу 3 было легко взломать. Лично я набрал 6 успешных взломов. Просто многие пытались сделать невозможное: решить задачу про НОД без НОДа. :) Контр-тест:

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

    У меня третья задача решена без нода, и тест проходит верно. Но асимптотика у меня — n^4. Я ожидаю, что будет TL на финальных тестах.

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

I saw many people hacked C div2. what is the test?

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

Люди из div1, как решили задачу B?

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

    я решал так: если T<=n , то просто найдем самую длинную подпоследовательность. Пусть T > n. найдем самую длинную такую подпоследовательность если T1 = n и T2 = n + 1. пусть diff = ans2 - ans1, где ans1 — ответ при T1, а ans2 при T2. тогда ответом будет (T - T1) * diff + ans1.

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

what on god sake is the 3rd pretest from div1B?

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

What was everyone's solution to Div2C/Div1A? Mine was a really questionable greedy which sorted all of the values descending, took the top 2 as the first 2 numbers, and then removed pairwise gcds, took the next descending number available, remove its pairwise gcds with all other chosen numbers, rinse and repeat.

I feel like there's some counterexample to this algorithm, but it passed pretests.

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

    I did the same.. and I think it is correct

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

    Did the same, but got TLE on 7 pretest.

    Could you tell some more on your implementation?

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

    what if the top number repeats ,like 6 6 4 2. Hope you handled that.

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

    That's what I did too, and I'm pretty sure it's correct. A not-very-well-explained proof: Consider the situation: You have a partial solution that is certain, and you need to sort the remaining numbers. If you don't put the biggest one on the diagonal in the table (i.e. as one of the numbers we're looking for), and pick some smaller one for all the cells there. Then you have to put the big number somewhere else. But the number on the diagonal in the same row/col as the biggest number has to be a multiple of that -> contradiction.

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

    It's correct. Notice that if you make the GCD table from the sorted array A, then the maximum element of (full table minus a square touching the bottom right corner) is the last diagonal element.

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

    I'ts definitely correct. I have most of an inductive proof on my scrap paper.

    I did precisely this with C++ multisets as my underlying data structure. Got TLE. I constructed the worst case on my computer and it runs in ~0.1 seconds. No clue what the problem is.

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

How to solve Div2 D/ Div1 B

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

The first time in my life that I failed all the problems. Look like I will have to go back to DIV2 soon...

Also, "Mathforces Round #323"?

Through, all the problems seem very interesting today. I wonder how to solve A and B.

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

    In first one we can make two arrays : one for horizontal and one for vertical and initialize them to zero. Then while taking input we can check if both are zero then we store the position at which input comes. After taking all input we print the stored values.

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

    Div1-A

    Sort the array. It's obvious that the biggest number in array is actually from answer (gcd(A, A) = A, gcd(A, B) <= min(A, B)). So you take the biggest number and store in some Ans array. Next biggest number in array (let's call it B) is actually the second number from answer because gcd(A, B) <= B and gcd(B, B) = B. So now you know that it's number from answer, you erase it from array and add to the answer. Now last move, you need to erase gcd(A, B) and gcd(B, A) from the array. Finally, at every step you take the biggest number, add it to the answer, erase it from the array and erase each gcd with other numbers in answer two times. That's all.

    My solution 13368755

    Div1-B

    It's kinda obvious that there will be some "plato" in answer subsequence. There will be one number (maybe on several positions) that will be taken in all copies of initial array in the "middle" of answer. So I checked if n * T is bigger than 10000 and if it is than I take Tnew copies of array such that n * Tnew <  = 10000. Now you can compute the length of the longest subsequence with the dummy quadratic algorithm and than you take two neighbor copies of array in the middle of answer. You take the biggest length of subsequence to them and say that difference between these lengths will be constant between each neighbor pair of arrays in the middle of the answer. So now you just add that difference multiplied to T - Tnew to the computed answer on Tnew copies.

    If n * T is less than 10000 you can use dummy algorithm to compute answer.

    My solution 13373614

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

What IS pretest 3 on Div2 D :/ ( my code passes 4 10 1 1 1 2 => ans 31 )

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

Question.C (Div-II) was very ambiguous question.....Is ans not just diagonal as GCD(x, x) = x OR am I missing something ?...Can somebody please explain ?

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

What is pretest 3 on Div2D? My code passes (4 10 1 1 1 2 => 31)

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

I always thought that all the stl functions are pass by reference rather than pass by value. Wasted a lot of time in figuring out what was making my code slow.

slow code

 int fun(multiset st) {  multiset :: iterator it = st.end();  it--;  return it; } 

fast code

 int fun(multiset &st) {  multiset :: iterator it = st.end();  it--;  return it; } 

Only difference is in passing the arguments, in one I pass by value and in other by reference.

Can anybody please tell me whether this is the only stl container which has pass by value behavior or are there some more?

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

    You are still thinking in Java, everything in C++ is pass by value unless you explicitly pass a pointer/reference.

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

    Your st is the instance of multiset<...> template class, so when you pass it without a reference (&), you pass the whole structure. It applies to all STL containers, not only multiset so don't forget to pass the reference!

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

    Because when you declare parameter without a refrence you are saying "Please copy the whole stuff", which can be VERY slow.

    When you are passing by reference you just passing an pointer to the object, so nothing should be copied.

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

Is intended complexity for problem div1-D O(logp(A)^2*2*2) ?

If so, how is it possible to make it accepted in java?

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

Editorials??

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

When will the editorials be released ?

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

Assuming I didn't mess anything up, I think div1 D shouldn't be hard to solve with a simple DP, it's just annoying to implement. You need the following fact: the greatest power of p dividing is the number of carries when adding a + b in base p. So if A has n digits when written as an - 1... a1a0 in base p, we can recursively compute dp[i][j][k], the number of ways up to sum two a, b < pi, with j carries, with k = 0 if a + b < pi, and k = 1 otherwise (so 0 ≤ i < n, 0 ≤ j ≤ n, and 0 ≤ k ≤ 1). I believe the edge cases with a ≥ pn - 1 or b ≥ pn - 1 can be done with similar, more careful analysis.

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

Why you do this CF ?

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

    If you see something like this, write us a message and we'll ignore one of those two submissions. We have a system that detects double-submissions with zero diff, but sometimes it doesn't work properly :(

    I ignored the second of those two submissions.

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

      Thnx :)

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

      Hi, the div 1 status changed from Finished --> System testing, with 1 only pending submission 13368130 from ashish1610. And now we can't use practice mode. Did you make any mistake? :)

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

        Yes, you are right. I guess you should be able to upsolve now, sorry for that :)

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

      Now, I have -1 with pretests passed.

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

        Don't worry, we'll fix that. Looks like I accidentally broke something.

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

        Fixed! I had to run a micro-system-testing in order to fix your submit :)

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

          Thanks :)

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

          Is there any chance this could stall the rating changes as well, since the changes already took effect for Div 2 (a much larger contest)?

          Also now that we're on the topic, why do the rating changes generally take some time to take effect? They don't seem that hard to calculate, do you guys manually check some flagged submissions for cheating or something?

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

            The rating has been recalculated for both divisions, isn't it?

            There is a lot of manual work every time after the contest (including looking through some suspicious submissions, catching cheaters etc). This delays rating change as well as system testing sometimes.

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

Ёлки-палки! В 1 дивизионе теперь в 10 раз меньше народу, чем во 2.

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

div2 D, in O(n^3*log T) right?

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

    I solve in O(300 * n2)

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

    I solved it in O(min(108, (nt)2)) 13373614

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

    I solved it in O(n^2*logn)

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

    I had the same complexity. I observed that for a LIS,I need maximum n periodic arrays where an element changes(from x to y ,y>x) ,the others contain only an element. But I fixed the number of periodic arrays needed,So I have (n +n^2+..+n*n)*log.

    I didn't see that the case with n*n(or t if n>t) includes all of the others,so if there is an answer when I need just x<n arrays,it will include also that :P

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

I feel like 2 hours is too little for this Div 1 problemset. 2.5 hours would be better.

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

How I feel about number of div2 participants:

(╯°□°)╯︵ ʇsǝʇsʎs

I'm joking, of course, thanks for the round and work which went into the new rating system!

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

Why is the system testing taking this long? Oh, because too many people in div2.

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

Nice contest

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

can someone tell me why my div1 c submission got tle13381594

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

What's the point that the system doesn't show test-cases during the system test?

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

Damn ! Man div 1 C had a tight timelimit !
my solution was of O(d(n) * n) damn ;D

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

Okhhh!! Finally got «C» after years :~

Probably missing the witching Cyan! :|

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

Thank you for this round — it felt great solving the problems. Especially problem D, with having to go on a hunch of doing LIS from two sides for some number of copies of the array, even though I wasn't able to prove on-the-fly that this will work.

Hopefully I'll be back to div1 now. :)

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

Ranks are about to be updated!

My rating is most probably going to decrease. But still

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

Wonder why the problemset page still 'temporarily blocked' ?

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

Eagerly waiting for Editorial...Its 1:16am in India :)

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

eagerly waiting for the rating change!

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

Where is editorial???

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

I lol'ed after seeing vitux Solution

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

Could someone explain please why this solution is ac? http://codeforces.net/contest/583/submission/13385298

Vectors have not enough length. Weak tests? I noticed this at the end of contest and lost 250 score to fix this. It was senselessly ;(

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

    He has written:

     vertical = vector<bool> (n, false);
     horizontal = vector<bool> (n, false);
    
  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    If you are talking about +-1 error in your solution than it is actually rare to crash because of this. It's like chances that A[n] will cause an Runtime error are very small (but they exist) and it's often better to leave the solution as it is.

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

      I think it is better to lost some score than to lost everything) And i thought that vertical[n] == horizontal[0] ;( And in test where first numbers are n it can cause error.

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

        You can't say anything because vector is not an array, so you don't really know how much space is allocated, is there something after your data in vector class by design etc (only if you haven't profound knowledge in C++). And about correcting mistake, I'm saying that it's unnecessary because I haven't ever seen program failing because of that error while using vectors.

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

    Vector [] operator doesn't check if the index is out of bounds. Using it with index outside the bounds is undefined behavior. Vectors may also allocate more memory than necessary so that new elements may be added without reallocation.

    You aren't going very far our of the bounds anyway.

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

Suddenly everything in codeforces turned into russian language for me :D

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

It seems like there is an "anti-cheating" pass, or something similar, after systest?

I noticed my rank increase from 83 to 81 already :D

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

.

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

Why it work? 13382543

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

the new formula seems to be so painful(

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

my contest rating is 1608 and still i'm Specialist

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

Why codeforces use 32-bit system?

Main problem is multiplication: http://goo.gl/VVVWsN

  • It's really annoying always use int32_t and upcast-downcast it in 2015.
  • call __moddi3 . It's really slow.
»
9 лет назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

Formula feels a bit weird (don't know if it's new one or not). I though I did ok, Top 60 out of 4.7k (top 1.3%), but I'll need to do this at least another 2 times like this to get div 1 :(.

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

    Also only -91 (so cyan) for last place (with -600 points) seems weird. My natural instinct would've said gray, maybe low green.

    Edit: I guess that happened before too, looking at http://codeforces.net/profile/worse my bad :P (though worse was 2k, and this was 4.7, so maybe it's not actually the same)

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

      I think the new formula makes it harder that only one contest affects your rating like what was happening before in goodbye contests for example.

      I'm the 5th today and hardly made it out of div2.

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

      Admins, please rejudge with old formula.

      We haven't said goodbye to it, it's not polite. ;(

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

My rating before this contest was very low(1954), I took 53 place, and earned only +118.

It seems like it would be hard to escape from violet(

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

Разбор?

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

Oh wow, congrats to div 2 winner wrong_order I just realized he solved all of the problems in reverse and still managed to win, talk about relevant username.

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

Ouch, just debugged my 2C to find the problem on Test 23. A one-word typo for a corner case can ruin the whole solution! >:[.

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

Будет ли разбор задач?

UPD: уже выложили здесь

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

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

http://codeforces.net/contest/583/standings/participant/5798484#p5798484 This guy decided to copy all solutions and submit them during virtual participation... what a bummer.