Блог пользователя Ripatti

Автор Ripatti, 12 лет назад, По-русски

Всем привет.

Это очередной 133й раунд Codeforces. Специально для 2го дивизиона, участники 1го дивизиона могут принять участие вне конкурса.

Раунд готовили Ripatti , Gerald , Aksenov239 , Delinur и MikeMirzayanov .

Раунд будет с динамической системой оценки задач. Задачи будут расположены в случайном порядке (см UPD1). Чтобы раунд был для вас максимально интересным, пожалуйста, прочитайте условия всех задач.

Удачи!

UPD1. Члены жюри посовещались и решили расположить задачи в предполагаемом порядке увеличения сложности.

UPD2. Контест окончен. Победители:
1. karensun522
2. stostap
3. sisterX
4. BiliBili
решили все 5 предложенных задач. Ура!

Разбор задач.

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

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

deleted

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

В прошлый раз гарантировалось, что "задача A будет в нем именно та, которую мы считаем наиболее простой". В этот раз это не гарантировано?

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

:)

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

133

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

Thanks so much for arranging the problems in expected order of difficulty.

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

Вновь жюри порадовали системой оценки и порядком расположения задач, спасибо.

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

Впервые попробовал взломать чужое решение. Сначала не влез тест в 250КБ. Тогда я сделал генератор – "таймаут 15сек". Пришлось сгенерировать не слишком сложный тест на 218кб – "Невозможно обработать взлом, попробуйте еще раз" – ну что за фигня? (

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

Задачи классные, хоть я и слил контест... :) Спасибо

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

Задачи сегодня какие-то очень тривиальные.

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

    Как я погляжу, ты все сдал за полчаса.. Или не все? Или вообще ничего? Прошу доказательства в студию

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

    Ну вы же не из Див 2. Посмотрите на баллы по задачам. Все очень адекватно. Я думаю, участникам из Див 2 было весело.

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

      Я никого не критикую, не подумайте. Я сам например больше такие люблю, чем идейные, как в последнем див1. Я, так сказать, просто подметил)

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

    По твоему результату не скажешь) Хотя да, мне тоже показалось сильно легче чем обычно

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

      В данном контексте слово "тривиальные" не тождественно понятию "легкие". В данном случае, я имел в виду что-то вроде "написать то, что просят", "ускорить очевидное решение" и т. п.

      Задача о гамельтоновом цикле в своей постановке тоже весьма тривиальна, но решение сложноватое:) Понимаешь о чем я?

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

        Ок, не понял значит тебя сразу)

        PS: обычно называют техническими, вроде бы

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

    Не скажи это про задачу А :) Да и задача Е, вроде, тоже не трив.

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

    Не согласен. И в "B", и в "C" надо увидеть довольно много не шибко очевидных мелочей.

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

Были ли у кого-то кроме меня проблемы с загрузкой страниц во время контеста?

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

    на начале контеста, потом вроде все стало нормально )

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

This contest started horribly for me (it took me a very long time to correctly deduce the formula for A, noob :P), but ended as my best placement ever (35th). I'm really happy, and I really enjoyed this entire competition, all the tasks were very interesting! Especially the Web one (even though the idea behind it is not that difficult, the formulation was very nice :D).

Gratz everyone!

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

First time used Yandex's notepads to solve problem A :D

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

so quickly rating!

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

Woohoo. Division 1. да, детка!

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

hard questions really! specially question A. I hope the editorial will be available soon. And really thanks to all of you who prepared this great contest.

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

Спасибо за задачи их авторам. Я, конечно, не претендовал на высокие места. Но обидно, что третья упала из-за маленьких размеров массива. И когда я в одном массиве увеличивал элементы и выходил за его пределы, я перескакивал на второй и там увеличивал. А увеличивал я... ответ. В итоге вместо 1 801 1601, я выдал 2 802 1602. Ну хоть 1, 2, 4 не свалились...

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

in the problem-B forming teams

is it not correct to just find the number of odd length cycles in graph described by 1..n??

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

    It's incorrect

    try test "5 0"

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

    it is correct (ofc with also removing one more player if the number of players left is odd), but look at the test which you failed:

    n = 4 3 -> 2 4 -> 2 4 -> 3

    There is one cycle here, and also this leaves us with an odd number of people left so we got to remove one more, rendering the final solution of 2. Your program outputs 0.

    My only conclusion could be that you implemented something wrongly. (since you passed the pretests I guess you already minded the case when the remaining number of players is odd)

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

      yeah... i saw that... i went wrong trying to implement the graph in a different way..

      anyways i think i corrected this and resubmitted after the contest...

      link --> 2013484

      still can't figure out what's wrong..? :(

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

    It's also necessary to check if there are the same number of people on the two groups

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

    After excluding exactly one element from each odd length cycle, you can get odd number of left (not excluded) students; in such case, we must exclude one more student.

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

sorry for this question(on this blog), but i am intrested why next round time is difference 08/18/2012 11:00AM

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

UPD: cout << (a+c-1)*(b+c-1)-c*(c-1) << endl;

You can see this submission 2013799.


some tips about problem A a=2 b=3 c=4 total=18 O O O O O O O O O O O O O O O O O O a=1 b=4 c=5 total=20 X:2 O:18 O O O O X O O O O O O O O O O X O O O O a=4 b=1 c=6 total=24 X:6 O:18 X X O O O O X O O O O O O O O O O X O O O O X X a=5 b=6 c=1 total=30 X:12 O:18 X X X X X X O O O O O O O O O O O O O O O O O O X X X X X X
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Instead of exact formula, use simple loop (I'm think that this is simplest solution :))

    example: http://codeforces.com/contest/216/submission/2007291 [w > 0 check is not necessary]

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

    In condition reads: (2 ≤ a, b, c ≤ 1000).

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

    it seems all of the solutions for problem A are different with each others !! there are no two same formula for this problem in AC codes :D

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

      i found a lot in O(1) solution :D

      (B*C) + (B+C-1)*(A-1)

      if we suppose we have an rectangle B*C(here A is 1) for any extra of A, we are adding a line containing B hexagons and line containing C hexagons that one of them overlaps each other, so total answer will be : B*C + (B+C-1:(one edge of B + one edge of C — one overlapped)) * ( A-1 :(for any extra of A))

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

Just for fun: задача с латвийской олимпиады. :)

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

Качественный контест! Спасибо!

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

Here is my submission to problem B: 2014265. It gives correct output on my system as well as ideone. But it fails on codeforces judge. Is there some problem with my code ? Comments are welcomed!!

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

    Function int cycle() doesn't always return a value. Maybe this is the bug you're looking for :)

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

My submission for Problem D results in runtime error at test case 35. i have no idea why this is happening. I am using the same concept as many other people during the contest.

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

    Perhaps there are some bugs in 69th line and 71th line, and the bug may be "Array index out of bounds". You shoud rewrite like this.

    while(lpos < threads[left].size() && threads[left][lpos] < threads[i][0]) lpos++; while(rpos < threads[right].size() && threads[right][rpos] < threads[i][0]) rpos++;

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

I am getting an incorrect answer for problem B on test case #18. I wish there were a way to get the test case (it's being truncated currently).

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

    Try using the information available, and you are very probably going to see your problem. Remember to change the value of M to the number of lines you have.

    You are probably partial visiting/coloring a component, check this case

    5 4

    1 2

    1 4

    3 5

    3 4

    Maybe it works for that case, but the idea is when you get to 4, if you didn't paint all the component, then 3 and 1 are visited, and it might think it's an odd cycle.

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

I have found a very easy approach for problem A. The idea is to calculate like this if a>1 && b>1 && c>1 //it means its a hexagon: so ans = ans + 2*(a+b+c)-6 (calculating the tiles on perimeter)...

else //i.e. a==1 || b==1 || c==1 it means its a square now... ans = ans + (a*b*c);

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

for those who couldn't AC Problem D : i prefer learning function upper_bound(first_iterator, last_iterator, data); (in C/C++) (which uses binary_search and it's order is O(logN))

i think CLEAN BruteForce algorithm gets AC too... but with this function, implementing is SO EASY, it does all the job...

all you have to do is find four upper_bounds(two for each side of cell) and calculate distances see if they are equal...

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

In Problem B,

This Test Case :

6 4

1 2

1 3

4 5

4 6

The expected ans is 0 but how will we make 3-3 pairs with this configuration ?