rotoZOOM's blog

TCO15 Round2C
By rotoZOOM, history, 9 years ago, In English

Just a friendly reminder about TCO15 Round2C. It'll take place in the Japan and online. Time and Date.

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

»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

since the round starts in a few hours...

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

Another great day for a competitive programmer! 0 problems solved ( ͡° ͜ʖ ͡°) (even 0 compilations :P)

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

    The 500 pointer was a very, VERY bad fit for a contest with systests after the contest and virtually no pretests. Not saying such problems can't appear, but I'd sure prefer it not being there.

    You could've still tried hacking, btw.

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

      Could you elaborate why was it that bad? I see that it got ~4% acceptance rate, which is not too high to say so... Was it because there were just many stupid cases or all people just submitted some shit?

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

        More like 0.4% acceptance rate. The number of submits is meaningless since there are many wrong solutions that pass a small subset of tests.

        It's because there were no cases. The real solution (most likely) tries all ways to seat all subsets of people (their permutations); for each permutation, it's fairly easy to construct a bunch of inequalities describing the starts of some two intervals / start / end have to have distance  ≥ x or  < y". If all such pairs of inequalities are possible, then (probably) the last person in the subset can sit down. And something much simpler for the other half of the problem.

        But people would think it can be solved more simply. If the most obvious thing fails some pretest... okay, let's find out why and add a check against that type of situations. It's not easy to find out that your solution is wrong by custom testing, since the cases where a strong casework solution fails are hard to find if you don't realise why your solution won't work already. And this leads to a lot of wrong submissions.

        Still, seeing as I didn't solve it, maybe there's even more to it or I'm completely wrong?

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

          Let me state this clearly — you say that it was "very, VERY bad fit", because people coming up with some shitty solution without any proof didn't get instant feedback that it is wrong --__--.....???

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

            Yes, that's correct :D

            Well, not precisely. People coming up with a solution with a faulty proof didn't get feedback that it's incorrect (or they wouldn't have submitted). And people coming up with a "shitty" solution probably did get proper feedback on samples; the problem is that there are ideas which seem good and yet fail, because they're just patching up a wrong solution (tactically good, strategically bad). And that's hard to see, especially when you're short on time and it didn't seem like a hard problem at first.

            Note that I'm not saying it was a bad problem. While I prefer less old-ACM style "only a bruteforce works" (except this time it wasn't disguised by fairly high constraints, see B and G), this troll-aspect provides a good learning experience at least.

            Ultimately, the fault for not solving the problem is ours (everyone's). If you think about it, we're pretty stupid — we're failing to solve problems that have known solutions, even after solving thousands of other ones. And even then, we need a lot of hints. Problem placement/points is a hint. Samples are a big hint, many samples/pretests are a massive hint. More time counts as one, too. And for this problem, it seems we desperately needed more hints to solve it.

            What I mean by the problem being a bad fit for the contest is:

            1. the contest would've been more balanced if the 500-pointer had "more hints" as above, or had more alotted points

            2. the problem would've had more solutions in such a situation, and that difference is considerably bigger than for a typical 500-pointer

            Do you disagree with one or both of these points, or do you think it isn't good to prefer more balanced contests?

            Also generally directed at people who downvote this and didn't reply(yet) — do you disagree, if so, then why? Try joining a debate instead of giving le upboats/downboats. Pic related.

            Of course, I'm not trying to blame anyone. I'm aware that we see it all just in retrospect. Nobody expected the Spanish Inquisition 2 solutions, I'm sure. Anyway, this doesn't matter for the two claims I present.

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

          That seems to solve the problem, from a (somewhat lengthy) discussion we had in our room post-contest.

          The fact that it's TCO probably contributed to the low acceptance: if you can't solve a problem you usually submit whatever random stuff that passes the pretests, because you really want to advance. If there is a 0,00001% chance that it is correct, it's probably worth trying...

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

          Can you provide a test case where the easy solution fails, so that I can understand your point?

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

            >_>

            Try it yourself in practice, that'd be better. If there was a "the" easy solution, it'd be the one when you assume exactly and only people for whom you answered "sit" or "unsure" sit down; it fails on samples. Then, you can assume that people sit down in a fixed order, I guess? I didn't spend so much time on the problem that I'd be able to list a tree of bad decisions.

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

      I agree it was hard to solve, on the other hand it was easy to hack :D. Without hacks on 500 I wouldn't be in the top 40, so I'm glad it was there.

      Btw., a good hack for 500 is

      L = 100
w = {2, 50, 30, 30, 30, 2}
      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think low accept rate is OK, but the problem was just too difficult. Also, I used ad-hoc methods to solve/pass the 1000 pointer, which was also bad for the contest.

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

      I must note here that I liked the problem a lot, despite being still unable to solve it.

      As for this problem appearing at TCO: it sure has depth (and some beauty too), so is a good fit for an important contest. Perhaps it broke some expectations: in rounds 2A and 2B, the advancers were mostly people who solved at least Easy and Medium, while today, a semi-decent time on the Easy sufficed. But I don't think the large amount of wrong submissions was expected by the authors.

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

        I did sort of like it as well, but the depth of a problem has little to do with how well it fits in; how many people can solve it under conditions of this contest vs how it'd be if the conditions were different (say, three more fairly strong systests among the samples?); since just solving the problem gives a large advantage over hackers who didn't solve it, a reasonable number of advancers (10? 20?) really should solve it for the problem difficulty to be properly balanced. This was a competition on one problem and around 60 additional hacks. More on that in a while.

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

Any greedy solutions for 250?

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

    I submitted a greedy solution in the practice room. (But I didn't prove its correctness and I can't come up with a DP solution with time complexity less than O(n^5) >_<)

    Here is my code.

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

      I've submitted dp solution in the practice room with complexity O(V*N^3), V — max card value, N — number of cards. The idea is the following:
      merge 2 arrays to one sorted vector<pair<int,int> > (first element card value, second 0 — petr, 1 — snuke).
      Now we iterate this array from smallest element to greatest.
      At each step we can add current element to the pile or eat it.
      If we add element to the pile and previously added element also from the same person then another person should eat at least one 1 card (because we take cards from the same person twice or more in a row). So, dp array:

      dp[last_taken_value][pos][debt_petr][debt_snuke][last_taken_person];
last_taken_value - obviously last taken value;
pos - current position in a joined array;
debt_petr - how many cards should snuke eat for sure;
debt_snuke - how many cards should petr eat for sure;
last_taken_person - person index (0 or 1) who last put his card in a pile.

      Dp step obvious. I know it is over-killed, but it works and clear for me.

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

        It seems tests are weak, because debt_petr and debt_snuke could be negative and this approach passed all tests. Please, don't read my weird solution. :(

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

          Actually, I just get rid of the negative value problem, by increasing debt_petr and debt_snuke to 101 and adding offset 50 to initialized values. Test passed again.

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

        Actually, you don't need last_taken_value, and without it complexity becomes O(V * N2).

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

          You are right, thank you! Just implemented solution without last_taken_value and got AC with O(V * N^2).
          The trick is that if we put some card into the pile, we have to eat all the rest cards with the same value.

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

Mistake.Sorry.

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

Could anyone explain how to solve 250 please?

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

    We have dp[top][move] which equals to longest possible stack of cards after move moves with top card leq than the number top.

    We begin with dp[i][0] = 0 for i = 0, 1, ..., 100. and when we perform move (check who is "on move", by taking move mod 2, wlog Petr is "on move") we do

    dp[petr[j]][move] = max(dp[petr[j] - 1][move - 1] + 1, dp[petr[j]][move - 1], dp[petr[j]][move])

    for each j. After that we just update dp[j][move] = max(dp[j][move], dp[j - 1][move]). for each j

    The complexity is moves·maxCard.

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

      Thanks a lot!

      The problem looks so easy after someone explain it to you :)

      → Reply