chrome's blog

Topcoder Single Round Match 646
By chrome, 9 years ago, translation, In English

Hi %username%!

Tomorrow at 05:00 MSK will be held Topcoder SRM 646

Let's discuss problems after contest

GL && HF

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

Comments Comments (22)
| Write comment?
»
9 years ago, # |
  Vote: I like it -16 Vote: I do not like it

>600pt problem
>4 samples

Just as I was complaining about weak samples last time. This has to be intentional! (How do you get MPSQAS to accept just 4 samples, even? I couldn't do that...)

Prepare for no points for that problem apart from hacking points and another bottom record in percentage of successful submissions.

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

    I got trapped with idea "we'll move to some cell in first few moves, and keep moving only straight to the right after that", which is completely wrong. And it seems that i am not the only one:) Adding 4 more small/obvious cases would not save me. So it's not only about the number of samples:) On the other hand, this problem would be too easy and straightforward if you'll add one more sample with that "million moves right-up-right", and maybe some samples against other wrong ideas, if they are possible:) Then most of solutions will pass, besides few with bugs — I resubmitted because I used 1e9 as INF:) In this problem it takes few seconds to get the idea of some solution, and not much more time to create a counterexample and new solution, in case somebody told you that your old idea is bad.

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

      Oh, it's not entirely incorrect. If you mean "up to k" by "few" :D

      What I did was: take all free cells neighbouring blocked cells, try to move only among them; if the top and left border of the rectangle formed by cells and is free, the shortest path between them is the obvious choice and can be easily computed; otherwise, just don't try it at all and try moving to cells that can lead through top and left borders. Dijkstra'd.

      I also proved it and it works, but I forgot about the possibility that the path LD->UR corners doesn't lead from to (it can be LR->UD as well). So just checking the whole border of that rectangle instead passes systests. Strangely, my original approach passes 70something-ish systests out of 90, while it should've failed quite quickly (it ignores half the cases, although the checked condition is pretty strong...).

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

        Sad story — by "few" i mean

        Great, just another problem with BFS on a 2D grid, why it costs 600 points?..

        (1 hour later) Wait a minute, what does this successfully challenged means?..

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

          Well, I thought "great, another problem with uselessly large coordinates". I don't like that type of problems very much...

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

      Maybe it's an issue I have with ad-hoc problems, but I truly believe this 600 pt problem was easier to get right than the 250 pt problem from the previos SRM.

      After reading the statement of this problem, I immediately thought "coordinates compression + dijkstra". The I coded it and got it accepted with 360 points. Obviously, I had to debug some stuff and be careful with a couple of things, like always including 0 and K as coordinates, handling "intermediate steps" inside the dijkstra, etc., but the thing is I got it accepted.

      The same didn't happen with the 250 pt problem from SRM 645. I had many approaches, coded all of them and they all turned out to be wrong. In fact, I still don't know what the correct greedy algorithm is.

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

        That wasn't ad-hoc, actually, it was a textbook greedy problem. I think the problem is many people dismiss studying greedy because "it's easy", but they forget that they need to be able to determine when greedy is correct and when it isn't.

        For this problem, once you have the correct greedy, it should be pretty easy for anyone familiar with correctness proofs to make an argument that it can't possibly be wrong. And if you have an incorrect greedy, a counterexample is usually easy to come up with.

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

Looking at decreasing number of participants at TopCoder — maybe somewhere in the future it will be enough just to register for round in order to be at top5 picture in Petr's blog...

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

    But the top 5 will be blue. Decreasing number of participants leads to decreasing ratings: user evima (no such handle on CF) in 31st place gained 25 rating points (2350->2375). That's horribly low.

    In the future, we'll compete to not lose too much rating.

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

      user evima (no such handle on CF)

      Check evima, for me looks very similar to evima :)

      in 31st place gained 25 rating points (2350->2375)

      Sort contestants by rating and you'll see that he is 34th among them by rating, and exactly 31st by rating among those who actually opened at least one problem. It gives us a rough approximation for his expected place. When there are only 30 contestants better than you, and your actual rank is 31st — you think that this should be rewarded by more points? This works only in Good Bye 2014 :)

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

        Hm, strange — the handle search on the rating page gave nothing.

        Yeah, but my point is that it shows how few people are participating. One would think that 31st place is awesome in something like TC SRM, and the actual rating increases are a bit underwhelming (or rating drops overwhelming).

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

    To be fair, this SRM had the worst time slot of them all for eastern countries (05:00 MSK). Look at the past SRMs at this time slot and you'll see very few people participated in them compared to nearby SRMs.

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

      Right, I know it.

      But even while comparing it with other SRM's at this time slot — number of participants is decreasing. Rounds 623, 630, 634, 638, 642 all were on this bad time slot — and number of participants during this sequence of rounds is going down.

      Maybe we'll see more participants when TCO will be about to start; but TC is clearly losing popularity. Maybe it is because of recent problems (few failed rounds, late announcement of January schedule etc.). Or maybe guys just switched to CodeForces, because it is better than TC right now:)

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

        Yes, that's true. I used to hate the people saying "Codeforces is better than TC", because CF had lots of room for improvement: Too many div 2 only rounds, time slot variety is nonexistant, TC's problems were a lot more creative, the pretests aren't hidden (there's no reason not to show them to you after you pass, so you can tell if they were weak or not without wild guessing). And don't get me started on "Codeforces is temporarily unavailable" during rounds.

        But recently TC has gotten indefensible. While I have seen some considerable progress here on basically all of the points I've listed except for pretest consistency, TC is only getting worse with an arena malfunction, poor samples and no editorials. If they don't want to die out, they need to step up quickly.

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

500 pt division 2

Does we have to find the x>=0 where it can reach at k steps .

Can we use dfs it is not working in last sample testcase. My code is

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

    I also tried DFS but failed miserably... Here it is

    I really don't understand why this is incorrect. My approach was to try all possible directions and store the maximum x-coordinate I visited. Any insight of why this solution is wrong?

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

      DFS does not look for a shortest path. You are not trying to optimize it in any way, you are just looking for any path, and when you found it — you don't try to optimize it anymore.

      It's a common mistake. You'll find some long path to one of key cells, call recursion from it with small value of k, and don't reach target cell as a result. BTW, here is an editorial.

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

      Guys, come on, why not to use ideone, where I can fork it and run it easily?

      I used BFS, read here.

      It seems, that you tejas.pandey misunderstood the question, you are checking max x only at the final position... Problem with both DFS I see, that you are marking the field visited even if it is not visited in shortest path — so you cannot continue from that field, when sorter path is found and you can miss some case...

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

        Betlista why is it so that BFS passes but not DFS.?

        I have used a similar approach as of yours mentioned in the editorial but just created a matrix of 2001x2001 size and did a dfs on it to search for the maximum x-coordinate attainable.

        Here's my solution using DFS with greedy strategy that failed system test.

        Could you spare some time helping me with that?

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

          This mat[1000-y[i]][1000+x[i]] = 'x'; is a typo, right? Should be 1000+y[i]?

          here is failing test case:

          xSx
x.x
xxx

          Your code returns -1, but 1 is correct answer, you did the same mmistake as tejas.pandey — valid move is also to stay at the position

          Also as I_love_Tanya_Romanova wrote above, DFS is not finding shortest path (I still didn't fonund the test case), you are also somehow mixing x and y — you returned q (=y) from DFS, while we want x, am I correct?

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

            No, that isn't a typo.

            Actually I have taken (1000,1000) i.e. centre of the matrix, as the starting point or origin in 2D coordinate system.

            You can see this below:

            Now, if I move one step right from the starting position I go to (1000, 1001) and the x co-ordinate at this point is represented by (columnNumber-1000) i.e. 1001-1000 = 1 , and hence I returned q instead of p everywhere.

            Similarly, if I have a cell with co-ordinates (a,b) as blocked, then I need to block the (1000-b, 1000+a) cell in my 2001x2001 matrix. This is all because as I go right, the columnNumber increases and hence the x-coordinate, as I move up, the rowNumber decreases and the y-coordinate increases.

            I have also fixed the flaw I found in my code, the flaw arised because of the same reason that I was not considering the case that staying at some point is also a valid move Here's the link. I have resubmitted it on Topcoder and this again gives me WA for a bigger testcase. I guess there is still some problem with my DFS, it's not backtracking properly actually with the correct value of k. Probably I will try this problem again using BFS.

            BTW, thanks Betlista for that pretty test case.

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

Can someone share solution for 1000pt problem? I've tried binary search + greedy, but it fails on a few tests.

→ Reply