anup.kalbalia's blog

Invitation to the June 2012 Cook-off on CodeChef

By anup.kalbalia, 12 years ago, In English

CodeChef invites you to participate in the June 2012 CookOff at http://www.codechef.com/COOK23

Time: 2130 hrs 17th June 2012 to 0000 hrs, 18th June 2012 (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: http://www.codechef.com/COOK23/
Registration: Just need to have a CodeChef user id to participate. New users please register here
Problem Setter: Anil Kishore
Problem Tester: Hiroto Sekido

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Is it possible to solve "Alien Chefs" in Java? My solution TLs, and the same solution translated to C++ gets AC. It seems that the issue is because of server's performance (which is terrible — I don't know why the solutions are tested on such an ancient hardware). Do jury have a Java solution for this problem?

Upd: Oh, I see EgorK managed to do it in Java. It's interesting what magic optimizations are required for this :)

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I just leave this here.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When I used C++, performance issues were not this terrible (maybe because jury has C++ solutions and TLs are set with respect to them) — it was always possible to optimize program enough. But seems that it is not the case with Java. I'll add the suggested comment in my template for the next Cook-off :)

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I actually do not have any magic optimizations. All my TLs were due to slow algorithm (). When I finally got it right () it passed time limit instantly. It actually can further be optimized to . You can view it here

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My solution is very simple and has complexity O((n + kq)log(n + kq)). You can view it here.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Interesting... My solution was , and still it got TL (while locally it worked 1sec for max-test). Maybe it failed because I abused ArrayList's too much or for some other java-specific reason... Thanks for the reply, I'll try to do some experiments.

      → Reply
»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Ну что такое. На 25 минут уже продлили. Я увидел, что за 10 минут не напишу 5-ую и забил. А так...

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

А кто как решал Connecting Soldiers? У меня получилось только предпросчитать и забить константный массив для каждого n отрезок, на котором ответ 0.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Это английская ветка.

    Я сгенерил отрезки [min, max] брутфорсом до N = 10, увидел закономерность и отправил.

    UPD: код.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    У меня спокойно (n^2m^2) c бряком залез.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ну динамикой, и кучей оптимизаций. Типо заметить что максимульная сумма, которую можно получить, меньше 500. Значит динамика 30*500 а не 30*1000. Еще можно заметить, что в динамике не надо перебирать эквивалентные состояния, то указатель куда мы ставим текущего солдата тоже перебираем до середины. Вроде это все оптимизации, и да на Java мне кажется вообще без вариантов.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    как-то так

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Я сказал, что раз N ≤ 30, то можно хранить строчку динамики в int (динамика true/false). И тогда пересчёт не за O(nm), а за O(m).

    → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Please check the editorials here: http://discuss.codechef.com/tags/cook23/

→ Reply