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

На старт, внимание, марш!

Настало время определить 50 участников, которые сразятся в финале Russian Code Cup в сентябре. Приглашаем тех, кто прошел квалификацию, принять участие в отборочном раунде в воскресенье, 14 мая 2017 года, в 13-00 по московскому времени. Раунд продлится 2 часа. Ждем всех на russiancodecup.ru, всем удачи!

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

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

T-shirts?

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

When you are one of the few people (3 to be exact) who solved F and you didn't get a T-shirt, because you forgot that in Russian Code Cup all problems are worth the same :')

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

"две непустые подпоследовательности"? Но зачем, КАРЛ?

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

В третьей задаче что же всё-таки было дано в задании? Условие говорит, что это копия сложенной фигуры, но судя по всему, там заданные области не связные, а значит это не может быть копия самой фигуры, а может быть, например, копия видимых закрашенных областей.

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

    по условию фигура полностью связана. И во входных данных тоже.

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

What's the intended solution for E? priority_queue for getting subarrays and binary search + hash for merging sequences get TL.

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

    There is a solution for n^2log. You check symbols one by one for nlogn and also keep in mind dp[x] = min{y, you could have finished known prefix with x-prefix of a and y-prefix of b}.

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

      So, you don't fix the number of elements chosen from each array?

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

        No, you just have not to get position (0,y) or (x,0) at the end (to make both subsequences not empty).

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

    I used min segment tree for creating subsequences and O(N * log(N)) suffix array to merge them and it passed.

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

    We just construe answer one by one and for each position in either array keep track of minimal position in the other array such that we can construe prefix of answer we have so far from corresponding prefixes of arrays

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

    My solution is O(N2), but it didn't pass test 9 because of the corner case.

    I greedily construct the answer one by one. I store the set of pairs of prefixes of a and b I used to construct the answer up till now. It has size O(N), because for each prefix of a we're only interested in the shortest prefix of b.

    For the given pair of prefixes, we can take any element, after which there's enough elements to construct the rest. We need the smallest, so we can take RMQ over the next allowed elements in O(1) for each pair, and find minimum over the pairs.

    Now, we need to advance the prefixes to reach the chosen element. To do that, we can just construct arrays of pointers to the next occurrence of this element in both arrays in O(N + M).

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

Нахватался бревён на первом тесте в D и не прошёл, потому что sqrt(x) >= sqrt(x) не верно. Ох уж эти виндовые компиляторы.

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

    Там все решается в целых числах (как и в большинстве задач на геометрию), зачем какой-то корень?

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

      я там сравнивал расстояния и по ошибке сравнил расстояния, вместо их квадратов. все остальное в целых.

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

    Прогнал локально, ожидаемо все тесты прошли.

    RussianCodeCup, нет планов поддержать инвокеры на других ОС?

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

      А почему компилятор / ОС виноваты?

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

        Не прав, безусловно, я тоже, но с этим мингв всё время разные проблемы.

        Ну а вообще, не удобно, когда нет возможности запустить все также, как в проверяющей системе, приходится вслепую искать баги (с этим бы запуск ещё помог, хотя и в меньшей степени)

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

Got WA#9 in problem E because missed the fact that both subsequences must be non-empty...

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

    Same. Quite atificial condition that we can get rid of just by adding following to the end:

            if (maxElement(answer) < minElement(b)) {
                answer[k - 1] = minElement(b);
            }
            if (maxElement(answer) < minElement(a)) {
                answer[k - 1] = minElement(a);
            }
    
    
»
5 месяцев назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

С попкорном жду выложенной тренировки на Codeforces. В задаче В не заходит решение через дейкстру, и я на 99.9% уверен, что оно зайдет на CF и на любой другой адекватной проверяющей системе.

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

    18 миллионов обращений к сету? Неплохо.

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

      А если посчитать поточнее, то 2000 раз граф из 2000 вершин и 3000 ребер, причем первые 1000 вершин просто добавятся в сет и останется граф из 1000 вершин и 2000 ребер, после чего еще 1000 вершин добавятся в сет и останется 1000 ребер. Так что будет миллионов шесть для сета из 1000 элементов. Вы правда думаете, что это ТЛит?

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

      Немного пруфлинков. Ideone выполнил ТЛ-тест за 1.29 секунды.

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

    У меня зашло через Дейкстру, когда я начал добавлять только одну (следующую) раскладку из состояния за раз, а не все возможные. Сначала был TL.

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

      Забыл уточнить. Речь идет о Дейкстре с сетом на C++. Дейкстра с очередью с приоритетами не выделяет память и, скорее всего, пройдет.

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

        Щас бы писать Дейкстру с сетом вместо PQ

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

    Пока тренировку не представляется возможным залить из-за внутренних проблем Codeforces. Как только починят — сразу выложу.

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

    И почему дейкстру? В динамике dp[i][j] = время нужно, чтобы набрать первих i знаков с актуальной раскладкой j, восможно взять массив 2N раскладок вместо цикла длины N; после имеем dp[i+1][k%N]=min(dp[i][k%N],dp[i][j%N]+a+(k-j-1)*b)+c для всех 0 ≤ j < k < 2N, k ≥ N, и это легко вычислить линейно.

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

      Я понимаю, что можно не использовать Дейкстру, я прекрасно вижу в структуре моего графа ациклическую компоненту и один цикл.

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

    Дейкстра с сетом получила тл22 на ркк, на кфе АС.

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

Is the final round online?

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

What is solution for D?

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

    Just count for every vertex v, number of pairs (u1<u2) ui!=v, such that Ang(u1-v-u2) < 90. Then you just need to subtract 2 * binom_coef(n,3).

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

Задача A была не очень java-friendly, я ловил несколько TL-ей, а решающей оптимизацией оказалось сокращение перебора в 2 раза условием if (mask <= revMask). Это так и задумывалось?

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

    Зашла с первой попытки.

    Что за mask <= revMask?

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

      Ну каждой маске соответствует другая маска, получающаяся заменой 0 на 1, а 1 на 0. Из каждой такой пары достаточно только одну чекать. (можно по-другому: например считать что первое число всегда входит в первую группу) А у тебя это решение на rcc зашло?

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

How to use the checker for problem C on my computer ?

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

    You can try DFS, you just need hash table to check point exists or not and same for visited.

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

      I mean how can I use the checker to check my solution on my computer. I don't see a main function in the checker, and I see a lot of "import ..." that I've never seen before.

      Sorry for my inexperience with Java.

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

Задача про остроугольные треугольники тот ещё свежак, конечно.

P.S. Пока пытался найти пруфы, вбил "number of acute triangles" в гугл, вот один из результатов на первой странице http://stackoverflow.com/questions/21953443/count-acute-triangles

P.P.S. По ссылке какая-то фигня, вместо решения, но всё же...

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

Will there be a place to submit solutions after the contest?

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

    0n25, already mentioned that Codeforces have internal error which not allow add problems to gym. They will be added after problem will be resolved.

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

Sorry for long delay, contest has been added (finally!) to gyms: 2017 Russian Code Cup (RCC 17), Elimination Round

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

Прошу прощения за очень долгую задержку, контест наконец-то добавлен в тренировки! 2017 Russian Code Cup (RCC 17), отборочный раунд