chrome's blog

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

Hello Codeforces!

Tomorrow at 14:00 MSK will be held Topcoder SRM 665.

Let's discuss problems here after contest.

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

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

It will be my first topcoder round from a long time. I wish all good luck tomorrow.

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

Div1 300 was repulsive and made this round a little boring.

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

    Div1 300 was an okay DP. I didn't think it needed 300 points instead of 250, even.

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

      Your reply does not make sense . I am not talking about the difficulty of the problem but that this problem did not have any 'nice idea' that topcoder problems usually have to make the coding part less painful.

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

        The coding part wasn't painful, at least for me. And DP is a good enough idea for the easiest problem.

        If you think having different experience and opinions is not making sense... oh well.

        Btw, my idea was that we try all lengths of the first, second lucky number, and if we know the lengths, then DP = min. number achievable if we've filled in the last i digits of both lucky numbers and the i + 1-th digit of the sum from those digits is j (0 or 1). The limits are small, so a lot of things can be bruteforced.

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

        Actually, you could speed up obvious 414 ( {4, 4}, {4, 7}, {7, 4}, {7, 7} for every position) bruteforce to 314 with observation that you don't need to check (7, 4) after you tried (4, 7), since it leads you to the same state of the backtracking. So we have a little observation/proof + easy code, which is quite TC style.

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

          I actually coded this initially because the code was relatively short, but because I also had to brute force over the lengths of the two numbers it ended up running slightly too slowly, at least in Java.

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

            My solution in Java has passed the test data. Actually, we have only two options for the bigger number's length. So it's runtime is roughly 14 * 28 * 314 = 1.8 * 109. Seems like it runs faster because of "if currentSum >= ans return" condition and trying to put lesser digits first.

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

          I tried to generate all possible numbers as you said, This is my code.

          some time's it gives TLE on some cases, and some times it returns wrong answer for other cases.

          What is still missing ??

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

Can anyone (well, I guess there are 4 candidates) describe their solution to div1 hard?

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

    There is a wrong solution, suggesting that the answer could not be more than 625. Egor convinced jury that it's possible to get more. Now there is no proof you can't get more than 861. And still a problem with 500. I got hacked on the test "5,5,5", "5,5,10", and my hack "1", "1" wasn't successful. :)

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

    I can make anything up to 861, but cannot prove more is impossible

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

For Div2 900, I tried to find greedy solution as this:

1- generate all possible lucky numbers up to 1^15, which results in almost 65600 numbers.

2- for each number generated, try subtract it from the note digit by digit.

3- if some digit in note is not a question mark then check if it is a possible summation of the corresponding digit with a '4' or a '7', if not then ignore this number and proceed to the next one

4- if the digit is a question, I try to take the summation of the corresponding digit with 4 or 7 and replace the question mark with the first digit of the sum, and this way I am sure the resulted number is a summation of two lucky numbers.

of course I will minimize the resulted numbers each time.

is this approach correct ?

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

Yet another fail

At least this time I had same bugs as jury :)

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

    Just wanted to say I am so excited that you are back to uploading screencasts! Now finally have a few more of yours and Petr's to watch!

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

"As it seems the D1 hard may not actually have a solution, D1 will be unrated (at least for now). Division 2 will still be rated, however."

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

    Well, that's one more unrated match for me...

    oh well, not much of a loss considering how little I solved.

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

    is it settled that the round won't be rated ?

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

      There are no results yet even for the medium problem. And no solution for hard.

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

    I don't understand this decision to be honest. I'm looking if TopCoder has some official policy concerning unrating matches.

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

What's wrong in this solution for Div1 300?

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

I am surprised when i open the division summary and see tourist hasn't solved Div. 1 Hard. And a few minutes later comes an announcement: "It seems the D1 hard may not actually have a solution".

Tourist doesn't solve a problem -> Problem is unsolvable :P

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

I was thinking about Div1 Hard and assuming that favorite number is smaller or equal than 625 (exactly how it was supposed to be during the match; for values bigger than 625 the author expected to return an empty vector) is the following solution working? (I've implemented a tester and it seems so, but I'm still not sure) (SPOILERS):

  • find the biggest number P that P^2 <= favorite. Construct a chain with 2*P+1 nodes (and 2*P edges), alternating with type 4 and type 7 edges, like: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6, where the edge between nodes 0 and 1 is of type 4, between 1 and 2 is of type 7, between 2 and 3 is of type 4 and so on.
  • subtract from favorite P^2 (because we already have P^2 balanced paths obtained from the chain), what it remains should be <= 2*P.
  • Now, in the worst case we have only 2 more nodes available to add (to don't go over the limit of 51 nodes). If we append this node to node 1, with type 4, then we'll get exactly P more balanced paths. If we add it to node 3 (again with type 4) we'll get exactly P-1 balanced paths, and so on. We can cover in this way the remaining number of required balanced paths using exactly 2 more edges.

Isn't this solution obvious and pretty simple, assuming it is correct? It seems actually too simple for a Div1 Hard :-D. What do you think? Thank you!

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

    A construction similar to this was actually the intended solution and will always construct numbers 625 or less. The implementation is quite simple but the idea seemed hard to think about or not super obvious to try. I actually proposed the problem as a d1medium but we decided it worked better as d1hard.

    To make the problem work I had a bounding proof to show that you cannot form a construction with over 625 paths. (Most of the difficulty of the problem was proving/convincing yourself more was not possible) Unfortunately, proofs can have bugs. :( My proof had a subtle error in it and as we see with Egor's solution, trees with larger number of paths can be constructed.

    The proof is not a total wash though; you can fix my proof to bound the number of balanced paths that start with weight 4 and end with weight 7. If I had noticed the mistake earlier, this would have been an easy fix to save the problem. (Add the additional requirement that such paths must start with 4 and end with 7)

    If anyone is interested in the details of my bounding proof, I'd be happy to spend some time posting on my bounding method and the stupid mistake I made in the original proof.

    I tried to form a new upper bound for the stated version of the problem but haven't found any bounding that result's in an upper bound close to Egor's construction. :( I also don't have a construction that forms more paths.

    Many things went wrong during the preparations of this round. (Resulting in the errors for the d1medium and the removal of the original d1easy and replacing it with the d2hard) The result of the SRM was very sad to me because I liked the ideas for the d1 problems but everything seemed to fall apart during testing. :( The thing that seemed the most stable after testing was the d1hard because we had a straightforward bounding proof and the solution was simple. Sadly, even that problem had an issue.

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

Why TC doesn't want to post correct results for Div1 on the website?

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

Are the tests for Div1 Medium correct in practice room?

→ Reply