Блог пользователя anup.kalbalia

Invitation to the July Cook-off on CodeChef
Автор anup.kalbalia, 13 лет назад, По-английски

CodeChef invites you to participate in the July CookOff Challenge at http://www.codechef.com/COOK12

Time: 2130 hrs 24th July 2011 to 0000 hrs, 25th July 2011 (Indian Standard Time - +5:30 GMT)
Details: http://www.codechef.com/COOK12/
Registration: Just need to have a CodeChef user id to participate. New users please register here
Problem Setter: Shilp Gupta

It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.

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

13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Just for convenience: we can see world time here
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Каким образом делается задача про матожидание скидки?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Считаем количество случаев, что i-я по цене вещь имеет j-ю по величине цену среди набора. Оно равно CijCitemCount - i - 1giftCount - j - 1. Тогда мы применяем j-ю по величине скидку. Суммируем по всем i, j. В конце надо поделить на число наборов - CitemCountgiftCount
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Понятно что большей суме нужна большая скидка
    Сортируем цены и скидки. Дальше ДП
    DP[i][j]- ожидаемая скидка, если среди первых i предметов, мы купили j. Переход делается с учотом того что предмет попадает в множесто с нужных нам j предметов, среди і, c вероятностью j/i
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Как обычно, пользуемся тем, что матожидание суммы равно сумме матожиданий даже для зависимых случайных величин.

    Отсортируем обе последовательности. Понятно, что большие цены нужно брать с большей скидкой.

    Рассмотрим отсортированный список всех чисел A и отсортированный список выбранных чисел B (общее количество различных списков B равно Total = С[n][k]). Посчитаем количество списков B, в которых i-е число списка A стоит на j-ом месте. Их количество равно Num = C[i][j] * C[n-i-1][k-j-1]. В ответ все такие ситуации добавляют A[i] * скидка[j] * (Num / Total).
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Очевидно, что любая вещь у нас имеет равную вероятность быть выбраной k/n. Отсортируем наши вещи в порядке убывания стоимостей, аналогично поступим со скидками. Очевидно, что среди вещей которые мы берем выгоднее всего взять большую скидку на более дорогой предмет. Т.е. заведем динамику с помощью которой посчитаем для каждого предмета вероятность того что он будет i-ым по величине среди взятых предметов.

    dp[i][j] - вероятность того что до этого было взято из i предметов j, p[i][j] - вероятность что i-ый предмет будет взят j-ым. Тогда очевидны следующие переходы:

    dp[i][j] = dp[i-1][j]*(1-p[i-1][j])+ dp[i-1][j-1]*p[i-1][j-1].

    А p[i][j] легко считается на основе dp[i][j]: p[i][j] = dp[i-1][j-1]*(число предметов которые надо взять)/(число оставшихся предметов).

    Суть я думаю ясна (надеюсь в формулах не ошибся).

    → Ответить
13 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
These contests are getting worse every month, last two were literally impossible to solve for java coders.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Well, I had to optimise in "Please Chief", but I'm not sure C++ solution will pass wthout that optimisations...
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    I fully agree with you. Codechef becomes worse and worse. This month contests were about how to compress one's solution to get "Accepted".
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    I completely agree. I wonder why the admins are not doing anything about it. Especially with the time limits. The most obvious solution for "Please Chief" : http://www.codechef.com/viewsolution/605870 is accepted. I compared values for example of C[100][50] with Cdouble[100][50] and the difference was huge (many of last digits were 0). So I thought that it is wrong and tried to compute probability pr[i][j] that item i is on position j, and got TLE... http://www.codechef.com/viewsolution/605873


    Edit.: The point is that in my solution each value is correct and it's obvious that some rounding errors can occur at the last digits of the result, but they don't affect the first 3 digits. But it is tled and to get acc you should use incorrect values counted in Cdouble, with no idea how can the final result be correct.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      The values Cdouble are correct with relative error 1e-14. So when we multiply and divide them as in obvious solution the result also will be correct with relative error 1e-14 (or near). But since this value is now less then one. Then relative error becomes absolute. That's why answer is correct.
      → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    This is all because of me :P
    Last time I was the author.
    This time I am the tester.
    But I sure you that when I set the time limits I think that they are generous enough.
    I have no aims for the contestants do some nasty optimizations.
    I apologize for all inconviences.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      > I have any aims for the contestants do some nasty optimizations.
      Sometimes typos can tell us a lot ;) .
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        :) update it. It is all because of Russian constructions with two negations which have unsual translate in English.
        → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Dear Sir,

      Can you please help and check if my solution during the contest had the correct solution in java. I had used memoization. I got TLE. My complexity was O(N*K). I coded the same thing in C++ with memoization got TLE there too. Then with standard Dp again got TLE. Then I coded in C++ and used sliding window DP which passed in which I reduced the whole table to only 2 rows.


      My solution during contest.


      This solution passed in C++.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А дорешивание там есть ?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    потом задачи добавляют в Practice, если не ошибаюсь :)
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Есть, но задачи добавляют медленно (возможно завтра добавят).
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      да вроде в предыдущем раунде сразу почти добавили
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Более интересно, когда они откроют результаты)
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    есть, все задачи с раундов идут в архив
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Из тех кто сдал задачу про медианы, какое у неё решение?

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

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

    >> Далее надо как-то быстро посчитать все возможные достижие суммы из необходимого числа элементов левее и правее (так и не придумал). 
    я предрасчитывал f[i][sum] = mask, для каждой суммы из первых i элементов в mask отмечено какими количествами элементов ее можно добрать (рассчитать можно за N * maxSum), что-то типа f[i][a[i]] |= 1, f[i][j] |= f[i][j - 1], f[i][j + a[i]] |= f[i - 1][j] <<1;
    Но запихать по времени это не получилось, хотя на локальной машине работало меньше секунды (суммарная сложность у меня получилась N^2 * 1200 * T).
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Блииин! Так вот что надо было в биты запихать!
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Я делал так же, с трудом запихал. Использовал то, что сумма не больше 1200*30 (а не 60). Держал не двумерный [i][sum] массив лонглонгов (сейчас только понял, что достаточно интов), а одномерный, но после каждого прохода по нему копировал нужные биты в строку двумерного булевого массива. Ну и прочей фигней страдал :)
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      Такое решение и предполагалось.
      Но вы в своем решение ходите по многим лишним суммам.
      В момент просмотра первых i чисел нужны только суммы не большие суммы min(k/2,i) наибольших чисел из a[1], ..., a[i]. Это, конечно, не меняет асимптотику решения. но очень сильно уменьшает константу, раз в 6, наверно, при худших раскладах.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        А на CodeChef проблемсеттеры всегда стремятся к тому, чтобы хорошо оптимизировать константу, прежде чем выставлять TL?

        Хорошо хоть, ограничения указаны в условиях, в отличие от многих индусских контестов.

        Кстати, а почему время у некоторых не-TL (в том числе и Accepted) решений показывается больше, чем TL, указанный в условии? Пример: (задача) (статус).
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Время равно сумме времен по всем тестам. Там 11 тестов в медианах.
          Тайм лимит на самом деле в 7 больше моего решения. На зимней школе Дима Жуков тоже давал задачу, где все дело было в константе. Просто когда разные решения имеют константу отличающуюся больше чем скажем в 10 раз, то это уже нельзя игнорировать.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            Ну не то чтобы нельзя, скорее это дело автора.

            Когда в 10 раз — да, легко отсечь, а вот когда в два (ну или во столько, во сколько TL должен быть больше времени жюри) — начинаются нежелательные спецэффекты.
            → Ответить
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Как решать медианы? Писал перебор медианы и после этого дп рюкзак для каждой половины на множествах. Он валился по времени.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я тоже получил TL. Решал рюкзаком для двух половинок и затем методом двух указателей, получается 1200 * N^3 * мультитест. Но, похоже, это можно пропихнуть, вроде бы мне процентов 10 оставалось соптимизировать.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    Надо писать оптимизированный рюкзак. Наример, хранить достижимые суммы с помощью битсета. Но предполагалось немного другое решение: для каждой суммы s храним битмаску тех j, для которых s представляется в виде суммы j слагаемых из первых i чисел. Причем надо было посчитать эти множества заранее для префиксов и суффиксов, а потом уже идти по медианам.

    Я был тестером этого контеста, и придумал тест, где валится обычный рюкзак (это было не просто). Поэтому все так мучались с этой задачей, думая, что можно затолкать обычный рюкзак.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня был оптимизированный рюкзак с битсетами, но он как-то загадочно валился в WA. Потренируйтесь взламывать :)
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Красиво, да. Наверно, жестоким будет тест типа 1 2 4 8 16 32 64 128 256 512 1024, а дальше 1200 1199 1198 1197 и так далее. Так?

      А никто не пропихнул с обычным рюкзаком?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Нет там квадратичная зависимость от индекса
        n=60, k=30..37
        a[i] = (i<=30 ? i*i/3 : 1200-sqr(61-i)/3) + random_noise()
        1 <= i <=60.
        Я его вообще случайно придумал. До этого были тесты, где просто была обычная квадратичная зависимость, и они были в принципе ничего. Но этот их всех переплюнул.
        Еще есть один
        n=60, k=30..37
        a[i] = (i<=25 ? 208-sqr(26-i)/3 : 1200-sqr(61-i)/3) + random_noise().
        Тоже хороший.

        Но возможно со степенями двойки тоже будет хороший, я не пробовал.

        Просто эти тесты еще хороши тем, что там везде ответы ненулевые. Ведь очень хороший чит, отсекать как только нашли нулевой ответ. Но здесь это не поможет.

        Нет никто. Все три прошедших решения где-то битмаски заюзали.
        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А кто-нибудь в курсе, будет ли официальный разбор? И как решать Chefs Game?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
We agree that there have been time limit specific glitches in judging specially when it comes to non-native language submissions.

It is really nice of Anton to try and take all the blame on himself as he has a very deep sense of accountability towards the programming community. However, we do not believe that he is responsible in any way for the above glitches that you faced in the recent contests.

Let me admit that we at CodeChef are still learning the nuances of the short contest format. There have been issues which caused inconvenience to the community and we apologize to you all. We will certainly look into them and work towards resolving them. We hope to have you all there in the next contest. And please drop in a mail to [email protected] in case you feel we can do something to make things easier and better for you.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I have been competing on codechef for more than an year now. I have learnt a lot(thanks a lot for that) but sometimes codechef problems require nasty optimizations specially when it comes to java. For long contest its still ok but for short contest I seriously feel the only thing that should be checked should be the complexity of the solution. It already makes the contestants consume a lot of time in coming up with the solution (at least the new learning coders) if they have to do a lot of optimisations also its really difficult to perform well and it is a bit demoralizing when you see the correct solutions.
    → Ответить