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

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

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

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

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

T-shirts?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • »
    »
    3 месяца назад, # ^ |
    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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Is the final round online?

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

What is solution for D?

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

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

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

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

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

    Что за mask <= revMask?

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

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

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

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

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

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

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

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

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

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

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

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

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

  • »
    »
    3 месяца назад, # ^ |
    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.

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

Sorry for long delay, contest has been added (finally!) to gyms: 2017 Russian Code Cup (RCC 17), отборочный раунд

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

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