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

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

Всем привет!

Мне выпала честь открыть четвертую сотню раундов на Codeforces. К сожалению, мы с друзьями пока что не смогли придумать сложных задач, так это всего лишь Div. 2 раунд. Но мы обязательно сделаем общий раунд когда-нибудь в будущем! Как всегда, благодарю Zlobober за помощь в подготовке задач, Delinur за перевод и MikeMirzayanov за сам Codeforces.

Для участников из первого дивизиона задачи должны быть совсем простыми, поэтому давайте поставим челлендж: красные должны все решить за 30 минут, желтые — за час, а фиолетовые — за полтора часа. Интересно, как много народу сможет управиться?

Разбалловка будет стандартная. Всем полных решений и успешных взломов!

UPD 1. Поздравляю победителей в официальном зачете:

  1. PauGra
  2. cuvwqe496
  3. tgehr

и в неофициальном:

  1. niyaznigmatul
  2. I_love_Tanya_Romanova
  3. dreamoon_love_AA

UPD 2. Разбор лежит тут: /blog/entry/17643.

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

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

Needs to put in main page.

Hope for high rating!

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

Thanx

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

And Div. 1 guys do not make new accounts

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

You didn't deserve +1 for a 'quick' announcement, first I'll look at tasks :)

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

I think this post must be in home page...

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

За выполнение челенджа, забустишь ммр в доте?)

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

I Hope to find many hacks :D

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

0100100001100001011100000111000001111001 0100100001100001011100000111000001111001 !!!
P.S Hey people who put minus let brainstorm a little. I want to say "Happy Coding"...

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

А кто главный герой на этом контесте ? (персонаж)

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

    Я некоторое время назад понял, что вводить общих персонажей или сеттинг для задач не очень хорошо. Потому что, как правило, некоторые задачи приходится подгонять под сеттинг, а это не всегда можно сделать. Так что никаких главных героев. Как задачу придумал — так на контест ее и дал.

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

      С одной стороны скучно, с другой стороны не придется привыкать. Все еще ненавижу Таваса с его карафасами — 5 минут я просто пытался думать этими названиями.

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

      Ну попробуем =)

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

Удачи всем. вперед

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

Ваш первый контест?)

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

    Это первый контест с полностью моими задачами. Прошлые мои раунды я вместе с ACM-тиммейтами делал.

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

      Поздравляю! Чтобы решить такой контест, надо думать как автор.)

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

Such a interesting challenge...

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

"How much people will be able to make a success?"

I think "many people" is grammatically correct, not "much people".

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

I hope I can get a better score than before.

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

Еще припишите: черные должны все решить за 15 минут, думаю, около сотни управится

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

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

I Hope this contest will stop/break my declination !!

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

It's my First Round on CodeForces,Hope we will enjoy together ;)

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

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

As you say : violets solve everything in 1 hour and a half.

But I think : I will solve these problems in 2 hour.

And more importantly : Until the contest over, I still haven't finished all problems.

Becausee : I am Stupid-Dog.

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

fourth hundred!!! isn't this the #301 Round

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

Если задачи очень простые можно намеренно сделать слабые претесты (например, не рассматривать частные случаи), чтобы можно было взломами занять участников, которые всё решили.

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

I wish I could join Round #302 with div 1 :D

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

Как Delinur перевела, если :

Последнее посещение: 6 месяцев назад...

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

Good luck to all of you guys in Conetests_)

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

I have missed the Registration -_- :3

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

niyaznigmatul почти выполнил challenge :(

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

Срочно нужен челлендж "лох дня"!

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

А на чем все ломали C?

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

      Ответ же "YES"?

      UPD: уже понял, на чем этот тест ловит. Видимо, надо сначала найти кратчайший путь до финиша, а не какой-нибудь.

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

        У половины комнаты было NO; у меня так и осталось:) Проверки в стиле "если клетка с точкой, то должно быть хотя бы 2 соседа с точкой" падают на случае, когда начальная и конечная точка являются соседями.

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

        Да вроде любой путь работает. Нужно только начальную клетку занулить

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

          Просто моя прога тут пошла не сразу вверх, а вправо-вверх-влево, и потом вообще не нашла свободного соседа. А чем тут поможет точка в стартовой клетке?

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

            Ну видимо зависит от решения.

            Во многих решениях(втч моем) проверяется наличие какого-то пути по белым клеткам и то, что у конечной вершины есть хотя бы 2 соседа(если она сама белая) — чтобы мы могли прийти как-то — выйти по незанятой и вернуться назад.

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

      типа стартовая клетка не учитывалась при подсчете кол-ва соседей?

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

        Мое решение хакнули потому что я смотрел только соседей точек :(

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

what was the hack on B and C ??

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

I guess I didn't understand D, or there are bug in my code :(

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

How to solve D ?

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

    Dynamic programming, by stepnumber/cur_r/cur_s. cur_p each time can be calculated from other values.

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

    Consider the dp[i][j][k], which denotes probability of having i rocks, j scissors and k papers remaining.

    From this we can calculate,

    dp[i-1][j][k] = dp[i][j][k] * ((i*k)/(i*j + j*k + k*i));
    
    dp[i][j-1][k] = dp[i][j][k] * ((i*j)/(i*j + j*k + k*i));
    
    dp[i][j][k-1] = dp[i][j][k] * ((j*k)/(i*j + j*k + k*i));
    

    where i*j + j*k * k*i is the total number of ways to choose two different species, and each term from this sum denotes the number of ways to choose (r,s), (s,p) and (r,p)

    The simply sum over, all dp[i][0][0] for all i = 1 to r for rocks, all dp[0][i][0] for scissors all i = 1 to s for scissors all dp[0][0][i] for paper for all i = 1 to p for papers

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

      instead of ((i*k)/(i*j + j*k + k*i)) I tried to use , (i/(i+j+k))*(k/(i+j+k-1). I know its wrong , but can't really understand why?

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

        I used the same but then you need to normalize probabilities. (because these sums miss when two of the same type are selected).

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

How to solve the problem E.

I think use set and binary indexed tree, but my code is bug.

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

    I calculated number of inversions in modified elements separately. Then for each modified element you calculate how many elements to the left of it are larger it, minus number of modified elements in the same interval plus similar thing for the right side. To calculate number of modified elements in range I used binary search on array of modified positions.

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
vector<int> a;
...
int dist = upper_bound(a.begin(), a.end(), x) - lower_bound(a.begin(), a.end(), x);

Distance between iterators is O(1) or O(N)?

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

For me,it wasn't enough time to solve all problems,It's ok,I will practice and I will do my best in next rounds ;)

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

Why so many people finish Problem B in Div2 quickly,while I spend a lot of time? Is there some tricks or I am stupid?

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

    I think it's a greedy problem, you must practice a lot of greedy problems to be able to solve it pretty fast :D

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

    Solved A, spent 20 mins on B, solved C in like 10 mins, read D realised it was dp so meh... read E realised it was bit with some normalization and map usage so I went back to B and after anthoner 20 mins I finally solved it . Hope you feel better.

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

I not accepted challenge: to D spent an hour. But I have included worse style in the past 5 minutes.

UPD: 7/10 (hacking by my) solutions not passed system tests. Why I did not choose the right test =(

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

For D, I was using the following recurrence to calculate the probability that rock wins.

total = r + s + p
// rock loses against paper
rock(r, s, p) += ((r / total) * (p / (total - 1)) + (p / total) * (r / (total - 1))) * rock(r - 1, s, p)
// scissor loses against rock
rock(r, s, p) += (r / total) * (s / (total - 1)) + (s / total) * (r / (total - 1)) * rock(r, s - 1, p)
// paper loses against scissor.
rock(r, s, p) += (s / total) * (p / (total - 1)) + (p / total) * (s / (total - 1)) * rock(r, s, p - 1)

And handled the base cases when r = 0, s = 0, p = 0 as

r = 0 return 0
s = 0 return 0
p = 0 return 1

Where did I go wrong?

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

    why did you Added ((r / total) * (p / (total — 1)) ?

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

    I don't really understand your probabilities. I think it should be

    r * p /(rp + rs + sp) for the first case and similar for others. (maybe its equivalent)

    And note that you shouldn't divide integer by integer if you do. Cast to double one of them first

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

      Please check my reply to jibon_ebong_shomoy. Why is my reasoning incorrect?

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

        Aha, I understood your reasoning and it seems to be correct.

        UPD: you don't consider the cases RR, PP, SS, so all you probabilities are to low. One way to fix is to divide result by 1 — p(RR) — p(PP) — p(SS)

        Note about integer division still stands, throught

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

          If we are in state rock(r, s, p) (this is winning probability for rock), and if we get RR, SS or PP, we are left in the same state, so I ignored it. Why can't we ignore that?

          Also I didn't understand your point about dividing result by 1 — p(RR) — p(PP) — p(SS). Could you please elaborate? Thanks.

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

            so the recurrent is something like

            rock(r, s, p ) = p(rp) * rock(r — 1. s, p) + p(rs) * rock(r,s — 1, p) + p(sp) * rock(r, s, p — 1) + p(rr) * rock(r, s, p ) + p(ss) * rock(r, s, p ) + p(pp) * rock(r, s, p )

            Note, rock(r,s,p) is calculated using itself.

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

              Isn't that an infinite loop? Using rock(r, s, p) to calculate rock(r, s, p)?

              And when you used , you find the fraction of times an rp battle takes place out of rp, rs, ps battles. But even in this, rr, ss, pp battles are ignored. Why does this work?

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

                Well, in that equation you may move all rock(r,s,p) to the left and divide by adequate coefficient

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

На B можно было вроде ловить, не напрягаясь, ибо у меня прошел претесты код, который вообще выводит не то количество цифр, которое надо (Как итог: глупейшая ошибка, и дай Бог, хотя бы A решил)

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

Как решать Е?

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

    Давайте разделим последовательность на две группы:
    1. U — Те позиций a[x] = x
    2. C — Те позиций a[x] != x

    Теперь есть три случая (a[i] < a[j] && j < i).
    Т.е когда мы находим инверсий, мы фиксируем две позиций:
    1. CC (a[j] != j, a[i] != i)
    2. UC (a[j] = j, a[i] != i)
    3. CU (a[j] != j, a[i] = i)

    Все C можно запихать в массив (найти их можно map'ом).
    Сумма всех CC — кол-во инверсий в нашем массиве.
    А для нахождения UC или CU перебираем C а U можно найти бинпоиском. Для этого надо реализовать функцию calcU(l, r) — количество позиций a[i] == i (l <= i <= r). calcU(l, r) = r — l + 1 — calcC(l, r). calcC(l, r) — количество позиций a[i] != i. (если у нас есть все позиций в массиве all, то calcC(l, r) = upper_bound(r) — lower_bound(l)).

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

As you say : reds should solve everything in 30 minutes.

But I can see : the person who finished first (only pretest pass, not Accepted) is 33 minutes (this is niyaznigmatul)

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

" The problems must be pretty easy for Div. 1 " they said,

" reds should solve everything in 30 minutes " they said.

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

    tourist , we need you)

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

    reds should solve everithing in 30 minutes and then failed systests on 1-2 problems.

    For example task B. The complexity of this task even can't be recalculated to Div1. )

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
yellows — in 1 hour

zld3794955 managed to solve everything in 1:00:21, does it counts? :)

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

    This one's so damn close. But I guess that there's no success in the challenge. Regardless the result of the challenge zld3794955 had solved all the problems, that's very good, imo.

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

    GUYS THERE IS SOME YELLOW GUY WHO FINISHED THE CONTEST IN 12 MINUTES!!!!

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

Sad Story. I finished coding C at 11:45, and started debugging. I was using DFS so it was I kinda hard to find the bug. I found the bug at 11:59 and when I try to submit, contest is over :'(.

Later when I submitted that solution, it was Accepted. I could've been 15th instead of 49th.

The bug I was facing was that, I had written:

else if(!cracked[r][c] >= 2) return false;

instead of

else if(!cracked[r][c] && visit_count[r][c] >= 2) return false;
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

When rating will be updated

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

can someone write recursive dp+memoization solution for prolem D bad luck island. bottom up DP solution just looks like magic to me.i dont understand it. please provide some explanation also for the recursive code. pleaseeet

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

Классный контест, авторы молодцы.

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

У кого-то на Е зашло решение за O(n * log2(n))?

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

What was the catch for problem C?

I wrote recursive DFS which obviously overflowed memory.

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

    :|| man you shouldn't pass a whole n*n matrix to some recursive function of course you will get MLE you should've used a global matrix

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

      Oh shit! I screwed it for myself! Anyway a lot to learn.

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

      I had problems with recursive DFS and I didn't think of not passing a n*n matrix and using a global one so I implemented a iterative DFS with a queue T_T worst time from all the passed solutions but it is the first time I've solved a problem C

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

        If you used a queue, it's a BFS, which is better in this case because if there's a path you'll find the shortest one. By the way, time is not really important if your algorithm complexity is good enough.

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

          Oh you're right, didnt think about the order that the vertexes were visited, it was a bfs indeed

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

    Wrote a recursive DFS as well:

    See 10951361

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

      Thanks! I didn't use a global matrix because I had to pass the changed(updated) matrix every time to the recursive call. Couldn't think of way to do that with global matrix. Let me check out how you made that :)

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

        You don't need a visited matrix,

        Never really used that in any conditional statements.

        You can reuse the string array my making '.' to 'X'.

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

I wrote recursive Dfs function for problem C but was getting segmentation fault. Any help will be appreciated code

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

Огромное спасибо вам dalex за этот замечательный контест я так счастлив потому что я стал экспертом вы даже не представляете сколько я этого ждал сколько я трудился чтобы достичь этой цели Я благодарю всех кто мне помогал учил

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

Solved A,B. I took WA in C for a small wrong,but now accepted too. Very nice contest,and second time I am blue :) Thank you dalex

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

Very ambiguous description of problem C. -_-

The word 'down' should have been explained properly.

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

For problem C, what would be the answer for test case?

3 3

XXX

XXX

XXX

1 3

2 2

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

    The answer is NO. You can move only between cells that share a common side (to the left, right, top or bottom).

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

      when we move from (1,3)-->(1,2) ,

      (1,2) will open which in turn opens (2,2),

      so wouldn't it be "YES"???

      or I didn't understand question yet??

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

        (1 2) is already cracked, so when you move there, you will immediately fall.

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

          yeah, so falling through (1,2) will make us fall through (2,2) which was our objective !!!

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

            Well, you misunderstood the statement. The map given in the input is the view of one level of the cave from above. The falling is not falling down to the next row of the input, it's falling out the level of the cave.

            The statement says: "The level of the cave where you are is a rectangular square grid of n rows and m columns." I think it's clear that only one level of the cave is described by that grid.

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

красные должны все решить за 30 минут, желтые — за час, а фиолетовые — за полтора часа. Интересно, как много народу сможет управиться?

Из красных ближе всех был niyaznigmatul: 33 минуты.

Из жёлтых: zld3794955: 1:00, но это значит что отправка была уже после окончания первого часа.

Из остальных: PauGra: 1:30, тоже не хватило менее минуты до полутора часов. Притом это новый юзер.

Из остальных, исключая новых: tgehr: 1:41.

Я никого не пропустил? Может быть, всё же есть хоть один осиливший?

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

    Кажется, что нет. Но все цвета были очень близки к цели!

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

Can someone please help me understand how the answer to this case(test 5) is NO for problem C. I think it should be a YES.

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

    You are not allowed to jump on the tile to make it crack, so to that you have to leave the tile and come back to it. Since there's just one tile in this case, you cannot leave anywhere, which means you won't be able to advance.

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

      I get your point, but in this case I think we need not move at all because the player is standing at the exit itself and can directly exit from there.

      Please correct me if I am wrong.

      Thanks.

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

        Yeah, but if he just keeps standing, he won't fall down. You only fall down if you move to a cracked ice. You can sort of assume that the ice under you was OK (.) and then you magically appeared on it, causing it to crack (X). However, to proceed to the next level you sort of need to crack it again. The sequence is . -> X -> advance.

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

I first tried solving problem C using BFS: 10948640. However, I got memory limit exceeded on test 14. When I implemented the same exact code but switched to recursive DFS, it passed all the tests with no problem.

The problem limit is 500, and that doesn't come anywhere near 256MB, so I can't figure out what happened. Can someone take a look and give me a suggestion?

Thanks

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

I'm not able to figure out where the bug is in problem B. Please help! here's my solution to Codeforces Round 301 (B) School Marks: CF301_Prob_B

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

Thank you for B and C — very nice problems.

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

This Contest made me BLUE :D :D Will Remember #301 ......

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

Umm i may have grossly misunderstood problem C here. Probably the word 'side adjacent' or 'fall down'. Help me out here. I used the BFS in a grid technique to get my answer. However, my code gives me 'YES' for example testcase 2. According to my logic, that should right.

Here is the case:

5 4 .X.. ...X X.X. .... .XX. 5 3 1 1

We can go to 1,1 from 5,3 as follows

(5,3)->(4,3)->(4,2)->(3,2)->(2,2)->(2,1)->(1,1)

Here is my code: http://ideone.com/JS4OAU

What's the flaw?

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

    You need to fall down through the cell (r2, c2) since the exit to the next level is there.

    The cell (1,1) is intact before you step on it,so you wouldn't fall down through that,and you can't jump on that cell to that cell to make yourself fall.