dalex's blog

Codeforces Round #301 (Div. 2)
By dalex, 10 years ago, translation, In English

Hi all,

I was honored to open the fourth hundred of Codeforces Rounds. Unfornunately, neither I nor my friends couldn't invent any hard problems, so it's only a Div. 2 Round. But we'll definitely prepare a full round in the future! As always, I thank Zlobober for his help in preparing the problems, Delinur for English translations and MikeMirzayanov for the Codeforces itself.

The problems must be pretty easy for Div. 1 guys, so let's start a challenge: reds should solve everything in 30 minutes, yellows — in 1 hour, and violets — in 1 hour and a half. How many people will be able to make a success?

The score distribution will be standard. Wish you accepted solutions and successful hacks!

UPD 1. Congratulations to the winners in Div. 2:

  1. PauGra
  2. cuvwqe496
  3. tgehr

and in Div. 1:

  1. niyaznigmatul
  2. I_love_Tanya_Romanova
  3. dreamoon_love_AA

UPD 2. This is the editorial: /blog/entry/17643.

  • Vote: I like it
  • +351
  • Vote: I do not like it

Comments Comments (127)
| Write comment?
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Needs to put in main page.

Hope for high rating!

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

And Div. 1 guys do not make new accounts

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

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

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

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

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

I Hope to find many hacks :D

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -51 Vote: I do not like it

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

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

Such a interesting challenge...

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

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

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

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

I hope I can get a better score than before.

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

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

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

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

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

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

    Good Luck & Have Fun my friends :)

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

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

    Wishing you successful Challenges , and Accepteds :) pardon the wordplay.

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

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.

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

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

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

    it's like centuries, 301 year belongs to 4 century. Century is 100 years

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

    Maybe the author counts the non-regular rounds as well

    e.g. ZeptoLab Code Rush, Rockethon, etc.

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

    and in which hundred the first round is? and 101st?

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

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

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

I have missed the Registration -_- :3

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

what was the hack on B and C ??

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

    Tricky case for C:

    2 2
..
X.
2 1
1 1

    There were lot of possible mistakes in B, it seems that most common of them is not checking that median of final array is large enough:

    9 8 10 90 2
1 1 1 1 1 1 1 1
    → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

How to solve D ?

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

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

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

    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

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

      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?

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

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

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

How to solve the problem E.

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

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

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it 
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)?

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

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 ;)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -46 Vote: I do not like it

    I wish you luck anus <3 or uranus <3 or whatever is your name <3

    (xo dezle var boshyo)

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

      I have no idea,what you mean my friend,but anyway best wishes from me :)

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

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?

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

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

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

    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.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

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 =(

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

    It does not count when you are participating unofficially:)

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

    Eh, I solved all with 1:47 but B failed systest :/

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

      LOL that's why B failed:

      if len(arr) > n:
    print "first"
    print -1
    quit()
      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

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

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

    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

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

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

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

        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

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

          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.

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

            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.

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

              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?

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

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

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

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)

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

    Oh, niyaznigmatul get Accepted all 5 problems with 33 minutes.

    33 minutes > 30 minutes (failed challenge)

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

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

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

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

    tourist , we need you)

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

    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. )

    → Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it
yellows — in 1 hour

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

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

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

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

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

      NO, it's a Virtual participation .

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

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;
→ Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

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

    Here you go!

    There are 3 recursive functions in my solution. recurse1 is for the rocks, recurse2 is for the scissors and recurse3 is for the papers :)

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

      Nice idea you can copy paste that easily but on the other hand my code... http://paste.ubuntu.com/10955206/

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

      You don't need 3 recursive functions, you can just rearrange your parameters. http://codeforces.me/contest/540/submission/10944961

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

        please explain this part of ur code:

        int rs = r*s; int pr = p*r; int sp = s*p; int tot = rs + pr + sp; if (s) dp[r][s][p] += getdp(r, s-1, p) * rs / tot; if (r) dp[r][s][p] += getdp(r-1, s, p) * pr / tot; if (p) dp[r][s][p] += getdp(r, s, p-1) * sp / tot;

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

          If we have r rocks and s scissors, then the number of possible rock-scissor pairs is r*s, and similarly for the paper-rock and scissor-paper pairs. The probability that a rock-scissor pair is chosen is rs / tot. In the rock-scissor pair, scissor always loses, so now we want the probability that rock wins if there is one less scissor, which is getdp(r, s-1, p), and we do the same thing for the other pairs.

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

    I think my solution is quite concise: http://codeforces.me/contest/540/submission/10954948

    EDIT: yzyz's solution above my comment is simpler

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

What was the catch for problem C?

I wrote recursive DFS which obviously overflowed memory.

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

    :|| 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

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

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

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

      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

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

        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.

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

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

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

    Wrote a recursive DFS as well:

    See 10951361

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

      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 :)

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

        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'.

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

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

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

    don't go to dfs if visited is true?

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

      Can you explain how ?

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

        write in ur dfs function if(visited[i][j]) return;

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    if(grid[i][j-1]==c && condition(i,j-1))
        DFS(i,j-1);

    you should let the condition() before checking the grid

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

      Thanks now it's working, Can you explain?

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

        Because first u check grid[i][j-1] == c where (j — 1) can ne negative.

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

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

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

Very ambiguous description of problem C. -_-

The word 'down' should have been explained properly.

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

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

3 3

XXX

XXX

XXX

1 3

2 2

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

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

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

      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??

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

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

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

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

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

            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.

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

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
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

      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.

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

        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.

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

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

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

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

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

    Your code really has some bug. I tried to modify the code, and got ac now. you can see this code.10960015 good luck!

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

Thank you for B and C — very nice problems.

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

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

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

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?

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

    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.

    → Reply