Автор RussianCodeCup, история, 7 недель назад, По-русски,

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

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

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

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

T-shirts?

»
6 недель назад, # |
  Проголосовать: нравится +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 :')

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

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

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

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

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

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

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

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

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 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}.

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

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

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

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

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

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

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +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

  • »
    »
    6 недель назад, # ^ |
    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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 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);
            }
    
    
»
6 недель назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +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, и это легко вычислить линейно.

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

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

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

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

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

Is the final round online?

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

What is solution for D?

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 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).

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

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

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

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

    Что за mask <= revMask?

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

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

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

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

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

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

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

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

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

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

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

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

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

  • »
    »
    6 недель назад, # ^ |
    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.

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

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

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

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