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

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

Привет, Codeforces!

12 апреля 2015 года в 19:00 MSK состоится очередной раунд Codeforces Round #298, для участников из второго дивизиона. Участники первого дивизиона приглашаются поучаствовать вне конкурса.

Задачи для раунда подготовили Максим Мещеряков (Neon) и Данил Сагунов (danilka.pro). Надеемся, задачи покажутся вам интересными.

Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon и за идеи некоторых задач. Так же выражаем благодарность Виталию Аксёнову (Aksenov239) за прорешивание задач.

Участникам будет предложено шесть задач и два с половиной часа на их решение.

UPD: Распределение баллов 500-1000-1500-2000-2500-3000

UPD2: Соревнование завершено! Спасибо всем кто участвовал!

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

  1. xuanhien070594

  2. misis

  3. Mikagura_Seisa

  4. plem

  5. 11111111

UPD4: Добавлен разбор

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

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

Why minus ? When I wrote this comment, scoring system wasn't announced. Also there wasn't even a " scoring system will be announced later " message

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

Is it a new meta on CF to make 2.5 hours rounds?

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

It should be Dynamic Scoring :)

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

    So , people don't like dynamic scoring??
    Every new thing is hated in the beginning :p

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

:) Good luck

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

В рассылке написано что продолжительность раунда 2 часа. Кроме авторов и номера раунда иногда нужно менять и продолжительность)

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

I think it will be a good contest wish succes for every EXPERT

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

i hope you all know who is going to win this round!

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

I hope to participate in Round #299 with (div.1) :)

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

six problems.Time duration 2.5 hours.

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

Coding Time

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

GLHF guys :)

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

The statments was very dificult to understand. problems are good but it takes very large time to understand a problem. Agree : +1 Disagree : -1

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

    Disagree -1 XD
    It's so clear to me. But I can't solve problems. I'm a noob :(

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

      I will see you soon.......
      Every body, Ehsan.poursaeed wants that you give me -1 and give him +1. see his conspiracy. Don't give him +1. but if you like give me -1

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

The pretest #15 of problem E doesn't have the visited stop list sorted. This costs me 45 minutes :( Was any one affected by this?

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

I liked the problems :)

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

How to solve second problem?

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

    It's dynamic programming. DP[current second][last speed]. But I spent a lot of time on understanding the statement.

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

      You don't need the dynamic programming. You just need to run from zero to t and update the speed using greedy approach. Check out my solution.

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

        Exactly. You just need to always increase the speed until it's possible to get to the required final speed in the remaining time.

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

    V increasing while we can decrease V to Vlast

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

    print(sum(min(v1 + d * i, v2 + d * (t - i - 1)) for i in range(t)))
    increase our speed as fast as we can. Also with decreasing
    (can't code without brackets highlighting :( and forget we need sum it, not print :( )

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

    This problem can be solved without using dynammic programming .. just traverse first from left to right and then right to left maintain minimum of both side at each second . sum them up :)

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

    if v1 + (t-1)*d <= v2, we know the best way is to increase the velocity by d every second. Otherwise, the speed would first increase to a top speed, let's say Vmax, then decrease to v2. We can enumerate the top speed Vmax to find the answer.

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

    maintain 2 arrays of size t.

    first has first element as v1 and contain maximum speed that can be attained at any time by increasing previous element by d.

    second have last element as v2 and contain maximum speed that can is possible at any time by increasing later element by d.

    example- if v1=10 and v2=30, t=5 and d=4

    array1- 10 14 18 22 26 array2- 14 18 22 26 30

    add elements from array1 to answer untill array1[i]<=array2[i], then add elements from array2.

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

    int main(){ int v1,v2; cin >> v1 >> v2; int t,d; cin >> t; cin >> d; int ans=0;

    while(t--){
        ans+=v1;
        v1=min(v1+d,v2+((t-1)*d));
    }
    cout << ans << endl;
    return 0;
    

    }

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

    i did it without dp.... simply take a array 'A' of size t; A[1]=v1; A[t]=v2;

    for<- 2 to t-1 A[i]+=d;

    and traverse from back and check if abs(A[i]-A[i+1]>d) make abs exactly d...by changing A[i];

    then add all A[i];

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

    You can solve it by 2 pointers..

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

      arr[0] = v1; arr[t — 1] = v2; int s = 0, e = t — 1; for (int i = 0; i < t-2; i++) { if (arr[s] <= arr[e]) { arr[s + 1] = arr[s] + d; s++; } else { arr[e — 1] = arr[e] + d; e--; } } ll ans = 0; for (int i = 0; i < t; i++) ans += arr[i];

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

How to solve D? I think that I got the idea but I had 4 unsuccessful attempts. I know that we have to change the remainders in order 0-1-2-0-1-2-0-1-2-... but maybe I implemented it wrong.

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

how to solve problem D handshakes ?

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

    Bipartite matching !!

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

      can you please explain the idea ?

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

        let's suppose the entering position are from 0 to n-1...

        since a team of 3 can be formed, so in general student with 'i' handshakes can go at positions i,i+3,i+6,i+9... (because additional 3's can form a team resulting in 'i' handshakes).. (make edges correspondingly to form bipartite) so Now the question reduces to bipartite maching of n students with n positions.. :)

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

    My kind of brute-force algorithm couldn't pass pretest 9 but I think the idea is correct.

    Store the people in an array of vector, where vector v[i] stores people shaking hands with i people, initialise current index of all vector to 0.

    Now start from 0, if current index of v[0] is less than v[0].size(), it means there is a person that can enter now.add this person to solution vector, increment 0 to 1 and repeat.

    If, current index becomes >= v[i].size(), then check for current index that are possible, eg. for i=7, other states possible are 7-3=4, 4-3=1 and so on.If you cant find any valid state that has current index < v[i].size(), break out of loop.

    Edit: The idea is correct.It passed the system test after removing a stupid bug.

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

    We only need to simulate the whole thing. But, we postpone groupings as late as possible.

    Let's say there is X ungrouped people and next one comes. First check if there is exists (remain) a person who shake hands with X people. If yes, allow him to shake hands with X people and add 1 to current no of ungrouped people.

    If not, form a group and try again, no of hand shakes becomes X = X - 3. Repeat if necessary. If ultimately not possible because there is not enough people to form groups anymore, output Impossible.

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

    D solution:

    Simple greedy: take the largest numbers first, e.g. 0 1 2 3 4 5 6 7, 5 6, 2 3 4, 0 1 2.

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

    I solved with greedy :D

    200000 stack

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

If in Problem 'A' n=4 testcase was not included in pretests, no. of hacks could be more!!

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

Тест 68 — очень хороший. Несколько TL по D, несколько WA по E, несколько TL по F.

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

I see several people, including me, failed on system test 50 for problem C. Any idea what it may have been?

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

Заполним бесконечный массив следующим образом: 0 1 2 ... N-1 N N-1 ... 1 0 1 ...

Можно ли в этом массиве выделить два отрезка длины M, сумма элементов на которых будет равна, но отрезки будут состоять из разных элементов?

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

    Ответ: нет.

    P.S. Не стоит жадничать на константы от которых не сильно изменяется время работы программы, но при этом может упасть решение.

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

I have done 4 problems and in my view, the difficulty level was C,D,A,B. Problem B just ruined my contest. -_- However, I have enjoyed the problem D very much. Thanks to the Almighty, thanks to the problem setters, thanks to all. :)

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

Ну вот как не сказать... Задачи просто КЛАСС...!!! Огромное спасибо авторам.

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

Can somebody explain why http://codeforces.me/contest/534/submission/10677423 submission passed test case no 50. The coder in the above solution has used int type for all the values and is still successfully dealing with large inputs. HOW? Costed me a unsuccessful hacking attempt.

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

    X + Y — Y would always result in X even if overflow occurs.

    As you can see in case 50 the answers are equal to the input.

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

Впервые написал решение задачи D
@
Упало по времени — больше 1000ms
@
Меняешь vector на массив и cout на printf
@
AC за 124ms

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

    10685565
    я думал ну совсем все знают что делать...

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

    В решении с ТЛ ты удаляешь из начала вектора. erase() работает за O(N).

    Это же решение только будем удалять из конца вектора, а не из начала.

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

      А у меня вот нет Erase, но все равно TL :) Не подскажешь, почему? http://codeforces.me/contest/534/submission/10681843

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

        Вместо подсчета cnt нужно выпрыгивать из цикла сразу как не получилось найти следующего студента. Иначе на тесте скажем 0 1 ... 99999 0 0 0 0 0 0 ... 0 будет с 99999 пробегать до 0 на каждый 0 в списке (за квадрат).

        PS: у вектора есть метод .back() ;)

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

          Да, язык не причем, косяк исключительно алгоритмичекий, спасибо сенсей! :)

          И за back спасибо :) я в плюсах нуб, вот-вот с паскаля перешел :))

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

    У меня в решении по E достаточно было изменить 3 на 4 и WA68 превратилось в AC.

    UPD: Хотя то что решение заходит при 4 — это из-за слабых тестов. Моё решение бы упало при N = 200000, M < N / 2, и более менее нормальных остальных значениях.

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

Где разбор. Вот не понимаю этого отношения к делу в принципе. Неужели так трудно написать разбор до раунда?

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

    Вокруг есть добрые люди, которые могут объяснить задачу по лучше всякого разбора, если их вежливо об этом попросить.

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

      Вы, видимо, совсем не поняли, о чём я написал.

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

        Я понял. Но хороший разбор задач — это не только описание идеи решения, это еще и анализ решений, посланных во время контеста. Авторы задач не всегда знают все способы решения собственных задач. Во время проведения онсайт соревнований на разборе часто можно услышать "несколько команд пытались вот такое заслать и у кого-то даже получилось" или "одна команда нашла более простое решение, чем авторское". Но так как у нас онлайн соревнование и проанализировать посылки всех участников невозможно, то в разборе скорее просто может быть упомянуты идеи решений отличных от авторского.

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

Nice problem set can't wait to see tutorial of D

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

Is something with std::set solution wrong or just mine is incorrect (why?)? I got TLE on test #46 ;-; http://codeforces.me/contest/534/submission/10685572

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

    you used std::lower_bound, which has linear complexity
    use set::lower_bound and you get AC: 10685831

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

    use s.lower_bound(x) instead of lower_bound(s.begin(), s.end(), x)

    This have been discussed many many many times in Codeforces

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

      Thank you so much :)

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

      Could you refer me a blog where this has been discussed?

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

        I've seen this discussion couple of times on similar situation: some guys ask why his solution fail, another reply that lower_bound(s.begin(), s.end(), x) has linear complexity. But it's hard to find comments, so I can't give you links.

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

          I couldn't find anything on google search as well.Maybe we can formalise it here. So what it means is that lower_bound(), upper_bound() have linear complexity(I highly doubt that) but s.lower_bound(x) has O(logn). But I have passed programs having O(n*logn) with n<=10^6 using lower_bound().If lower_bound() is linear then complexity would have been O(n^2) (impossible to pass).Is this valid for set only or is it true for vector, array also?Is its complexity based on array configuration or what?

          And one more thing, as far as I know c++ stl is highly optimised. So how come lower_bound() is linear, because I sure can implement this in O(logn)?

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

            I'm pretty sure lower_bound() is O(log) for vector and array (but of course it is assumed that the vector/array is sorted).

            The thing with lower_bound() on set is that, you do not have random access in O(1), so probably it was implemented in a way that makes it O(N). I think it is stupid design of this C++ STL that allows people to use the library wrongly like that.

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

    I have a TLE on system tests, but I used 3 smaller multimaps(each element only in one multimap, depending on shakes[i]%3 and I cycled between them) and used insert, lower_bound ( s.lower_bound) , erase, empty operations. What could go wrong? Isn`t is supposed to be N*log N solution? Or is it not good enough? http://codeforces.me/contest/534/submission/10675989

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

      You gave link to another solution.

      For your D, it looks like good, but it gets TL on N=113 which is weird. I ran your solution locally and it spits error in free(). I guess it's because you access myit while lower_bound can return a.end() (so myit does not point to an element) and then you erase myit -> undefined behaviour. Very strange it gets TL on CF...

      Add check myit != a.end() and I hope it will pass.

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

        Thank you. Changing one of "Impossible" conditions from (a.empty()) to (myit == a.end()) helped. It was my first time using map, I will watch out for it in future.

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

Хорошие задачи, спасибо авторам за раунд! Но дорешивание то откройте=)

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

فارسی زبونا همیات کنین

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

Why this solution gives WA for problem-B? Plz, help me--> 10682655

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

    When calculating DP you are setting your initial ret value to be 0. However, your recursive call can return you negative infinity, because there is no solution. Since you update ret to be a max of a previous ret value i+get(...), you lose that information. So for a state that doesn't lead anywhere, you will return 0, which is wrong. As a result, when the correct solution is 1+2+3+4+5+6+5+3+2+1, your program can do 1+2+3+4+5+6+7+8+9+0 (10 can't reach 1, so we use 0).

    Change line 50 from ret=0LL; to ret=-inf; and you'll get an AC :)

    Good luck!

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

D:Different teams could start writing contest at different times. the number of student -3 or -3*t(t=1.2...) it take me long time to understand the problem

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

Where can I find the rules for the scoring? Thanks in advance.

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

Thanks for the problems. It was a great contest with very nice problems.

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

Can someone explain why my code for C TLEd? http://codeforces.me/contest/534/submission/10682828 Shouldn't it be O(n)? Or do you need to somehow print more efficiently?

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

    As far as I can tell you just need to switch to faster i/o methods.

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

    Scanner.nextInt and Scanner.nextLong() is REALLY slow. You should use Integer.parseInt(sc.next()) and Long.parseLong(sc.next()).
    If it is not sufficient, you must implement method to parse integer.

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

:\ :\

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

For problem A — Exam why is the following output wrong for input 6?

6 Output 5 2 4 1 3 6 Answer 6 5 3 1 6 4 2 Checker Log wrong answer Jury has better result: 6>5

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

Мне кажется, в задаче F довольно слабые тесты. Удивился, что у меня решение отработало всего за 140мс, решил посмотреть тесты. Во-первых, вероятно, для некоторых решений самым сложным тестом будет:

5 20
10 10 10 10 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

но этого теста нету в тестсете. Во-вторых, там вообще нет тестов, где a[i]=10, а такой тест может не только быть сложным по времени, но и отследить некоторые ошибки (например, использование десятичной системы счисления для хранения состояния массива a[i]). Думаю, надо подобные тесты добавить хотя бы в дорешивание.

UPD: авторы добавили 3 теста с подобными числами, спасибо!

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

    А как ее вообще решать?

    Я написал какой-то перебор с запоминанием и тупыми отсечениями (если уже поставили слишком много/мало групп, выходим) и получил TL. Неужто выпиливание векторов правда все ускорит?

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

      Я писал ленивую динамику с состоянием из трех чисел bool D(Col,Mask,Val) — True, если мы можем расставить клетки, начиная со столбца Col, в предыдущем столбце мы закрасили клетки, соответствующие значению Mask (по одному биту на клетку, итого, максимум 2^N значений), а в строчке i мы должны создать еще C[i] групп, где C[i] — i-я цифра в разложении Val в системе счисления по основанию 11 (т.е. Val соответствует массиву из N чисел). Соответственно, перебираем, какую маску поставим в текущий столбец (неплохо бы заранее посчитать, какие маски для него подходят, т.е. соответствуют значению b[i]), пересчитываем Val (если начали новую группу черных клеток в строке) и переходим к Col+1. Итого, M*2^N*(M/2+1)^N состояний и пересчет за 2^N*N. Получается огромное число (порядка 1.6*10^10), но, во-первых, не все маски подходят под b[i], во-вторых, за счет "ленивости" динамики куча состояний не обрабатывается, в-третьих, гарантируется, что ответ существует, поэтому можно надеяться, что он найдется намного раньше, чем мы пройдемся по всем состояниям.

      Думаю, если вместо одного числа (Val) использовать вектор, да еще и состояния хранить в Map, например, то такое решение получит TLE.

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

        Да, я так и делал и получил TL :)

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

        У меня такое же решение. С одним отсечением, когда количество блоков уже больше чем надо, не прошло (TL). Добавил отсечение, когда блоков слишком мало (а можем добавить не более (W-x)/2+1 где W-ширина, а x — текущая ячейка) — зашло за 436мс.

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

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

          Под "ленивой" я имел ввиду следующий подход: сначала вызовем функцию поиска ответа для начального состояния (столбец 0, маска 0, значение Val соответствует изначальному массиву a[i]), потом находим все возможные переходы в (P+1,Col',Val') и рекурсивно вызываем функцию поиска ответа для этих состояний. Тогда мы обработаем только те состояния, до которых можно добраться из начального.

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

        Удивительно, насколько изменится время работы, поменяв мапу на массив и вектор на число. Если раньше всё это у меня падало на 16 претесте, то сейчас зашло за 31 мс (+ если уже не сможем в строке добавить оставшиеся группы — выходим).

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

When will the editorial be published?

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

Is there a problem with submitting? Why can't I submit now?

Edit: It is fix.

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

I seem to be getting TLE on case #72 of problem D: Handshakes. I am using a Hashmap<Integer, ArrayList> which stores the keys as hand shakes and indexes of people in the arraylist. Code runs perfectly. Its based on the same idea as @_spartan has written. Any optimizations?

Edit: As hellman1908 suggested, the complexity increases. So i changes the ArrayList to a Stack since the order does not matter and VOILA, AC :D

http://codeforces.me/contest/534/submission/10687311

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

    You remove elements from the beginning of it. In ArrayList I guess it's O(n) so total complexity is O(n2). Remove last element and it will pass

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

Is there any editorial links for the contest? sorry if I missed one thanks :)

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

How to solve Problem 'A'?

What is Logic behind it?

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

    Adjacent elements should differ by at least two, so if you enumerate first the odd numbers and then the even numbers you have a correct solution. For example, n = 5: 1 3 5 2 4

    This algorithm doesn't work when n < 5. In these cases, solve it on paper and hardcode into your source.

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

where i can read analysis ??

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

My accepted solution for Problem — 'C' used binary search: http://codeforces.me/contest/534/submission/10684361. As far as I can see, no one else had used binary search to solve this problem. I am not able to digest this. What obvious thing am I missing?

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

    Probably you would do better if you think the problem in two cases: + when all the other dices do their best + when all the other dices do their worst (summing 1 each)

    this give you a range of points you need on the a_i dice you are working on (once at a time), and of course tells you the amount of points (or faces on the dice) that you will never see to accomplish A points.

    Hope this helps http://codeforces.me/contest/534/submission/10679438

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

      I applied exactly the same concept as you are mentioning, if you look into my code, it's doing the same thing — finding minVals for all dices and then maxVals for all dices.

      To get those minVals (and maxVals), I have used binary search (and you are saying that the minVals would simply be 1 for each die). Can there not be a case when the minVal for a die be more than 1? (I could not come up with a proof that there cannot be such a case. If someone has any, then please let me know.) To be certain of the correct answer, I used binary search to get the minimum values for each die and then the maximum values..

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

        think about this example

        1 8 9

        I hope I am getting your point, but if you are asking for a counter example where the lower value a dice MUST have this is the easiest case, obviously your lower value is 8, so your upper value, giving you 8-8+1 possible valid dice' faces (thus 9-valid = 8 not used faces).

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

    you did the same job as others! but your time complexity is O(log(n)) and other's is O(1)

    :D

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

Great round, I like how many variants people wrote to solve problem D, really creative.

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

In case of Problem-B it is given "the absolute value of difference of speeds between any two adjacent seconds doesn't exceed d."

and this also " Assuming that at each of the seconds the speed is constant, and between seconds the speed can change at most by d meters per second in absolute value "

so for first case is it also possible that speed will be constant after 2 second I mean 5+6+6+6=23 2nd second value change by 1 and after that speed not change could be answar

Am I wrong?

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

    You are right, but the task wants you to output maximum possible value, and your 23 is certainly less than correct 26.

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

How to solve the problem F? Who can help me ?

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

    Notice that in a given row there can be maximum of 10 blocks (because we have at most 20 columns, and each block must be separated from next and previous block by at least one free cell). Also notice that we can encode any tiling by m integers as bitmasks (so that 0-th bit of every integer gives us the first row, 1-st bit gives second row, and so on) up to 25.

    Given that, let's do dynamic programming: dp[num_placed][r1][r2][r3][r4][r5][last] = true or false. It means, that we've already filled num_placed leftmost columns, and we must build r1 more blocks in first row, r2 more blocks in second row, ..., r5 more blocks in the fifth row; and last is the bitmask of last placed column. Let's estimate number of states: 21 * 115 * 32 = 108. Not all possible states are reachable.

    Instead of doing dp, I've made a backtracking, because it effectively visits all reachable states, with memoization it is done only once, and with some heuristics (for example, if we must place 5 blocks in some row and there are only 3 columns left, we can say 'goodbye' to this state immediately) it works even faster.

    But if you prefer dp approach, the main observation here is to encode [r1][r2][r3][r4][r5] as a single integer in numeral system base 11 (because each ri have possible values from 0 to 10), that makes coding more convenient.

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

      oh!Thank you very much.Your analysis is so distinct.And the search with memoization is more convenient to write.

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

In case of Problem-C

for the case 2 3
2 3

will not answar be 1,1

instead of 0,1 If second dice could not show 3 then this condition also apply for 1st dice too can't show 3 also?

I think then s=d1+d2+d3...dn condition will not satisfy

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

    1st dice cannot show 3 by definition: d1 = 2, so it can only show 1 or 2 (but not 3, 4, 5 or any greater value).

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

      by mean defination you mean this line?

      "s = d1 + d2 + ... + dn."

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

        No, I mean second sentence from the problem: "The i-th dice shows numbers from 1 to di".

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

Tutorial ?!

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

    What was this word "Tutorial"?

    Let's hope that the author haven't posted it yet because he wants to make it more understandable and detailed :)

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

Please anyone tell me , why this solution for problem-D is WA on test-9 ? Isn't it a correct order ?.. Sol:-> 10692139

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

    No, it isn't a correct order because if 2 shakes hands with 0 guys, then 7 will shake hands with 1 guy instead of 4 guys :)

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

Think Problem A pretests without test 5 -> Hacksss :)))

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

In problem 534D - Рукопожатия my code got AC 10687529 but when I try this test case : 5 0 1 2 0 4 it says Impossible but I think it should be possible with answer 1 2 3 4 5

How come?!!!!!!!

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

My code in problem 534D - Handshakes got AC 10687529 but when I try the test case n=5 - [0 1 2 0 4] it's output is Impossible but it should be possible 1 2 3 4 5 How come?!!!!!!

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

    No, it is impossible. If 4 handshakes with nobody, then 5 could not handshakes with 4 people. "At any time any three students could join together and start participating in a team contest, which lasted until the end of the day. " "so when another student came in and greeted those who were present, he did not shake hands with the members of the contest writing team." You assume the 1 2 3 formed a team so 4 handshakes with nobody then 5 can only handshakes with 4. So it is impossible. Sorry for my bad English

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

    If the 4th person shook hands with 0 people, how could the 5th person shake hands with 4 people?

    The answer is indeed Impossible.

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

where are the editorials

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

Please publish the editorials for the round!!

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

Ребят, подскажите идею для E. Есть мысль пытаться каким то волшебным образом определять для каждой станции, может ли она быть начальной/конечной, но эта мысль мне как-то не особо нравится

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

    А по-моему, это хорошая идея. Стоит лишь заметить, что тип точки (начальная/конечная) не так важен. Пусть все такие 'волшебные' точки будут начальными, остается перебрать лишь направление движения на старте.

    Теперь нужно всего лишь написать функцию, которая проверяет совпадает ли путь для заданной стартовой вершины и направления с путем, указанным во входных данных. Эта функция также может попутно считать длину пути. Вышеуказанную функцию можно реализовать за O(N).

    Остается лишь заметить, что 'волшебных' точек лишь O(1).

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

How to solve Problem-D

I mean from where I should start?

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

    First,You should count a[i]. a[i] is the number of students who shook hands i times. We define cur .cur is the number of student who we can shake hands with now. In the beginning cur=0.

    1. if a[cur] > 0 , it tells us we can add a student who will shake hands cur times in the permutation.And than a[cur]--(because we use a person)

    2. else cur-=3 (3 student start writing a contest) until (cur<3 or a[cur]>0)..

       2.1 if (a[cur]>0) is same as 1.

       2.2 cur < 3 it means the sought order of students doesn't exist.

    My english is very poor. You can see my code 10681578..I hope you can deal with it!

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

Here is the editorial, but for some reason it is not attached to the contest

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

Sorry,wrong contest.

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

hello I am tired , trying D problem

someone can help me !!!!! why does it give me runtime error on case 46 ??? 10733747

that is my code

thanks for advance everyone

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

Спасибо за раунд, он мне очень понравился