chrome's blog

Topcoder Open Algorithm Round 1B 2016
By chrome, history, 9 years ago, In English

Hi!

Tomorrow at 18:00 MSK will be held TCO16 Round 1B.

You can read about TCO16 here.

Also this round has limited number of competitors only 2500. And max number of advancers to the next stage is 750.

Let's discuss problems after contest.

GL && HF!!!

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

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

Are people who qualified in round 1A allowed to participate in round 1B?

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

    "All members who have not previously advanced – limited to the first 2,500 Competitors who register in the Arena" — from the rules linked in the post.

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

why no registration open yet?

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

    Its scheduled for tomorrow 12th april, still 26 hrs

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

How to do 1000?

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

    EDIT: My solution is wrong.

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

    My code failed in 1000. My logic is as follows. I find the max protection needed among all the positions not covered by any local shield and set the global shield to that value. After that I assign local shields greedily from left to right. When, at a given position, the current total protection offered is less than that needed, I find the local shield whose ending point is the rightmost among those active currently, and increment its value as needed. Can anyone please tell me whether this logic is wrong (if so, I made an implementation mistake)?

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

    I did ternary search on the amount the special shield is powered, and it looks like everyone did this. After that, you can sweep from left to right and use greedy with the addition of the simple shields, by using the one that extends furthest to the right.

    I unfortunately didn't think much about how it works — it was more based on intuition and the fact that the problem is supposed to be solvable quickly. Can anyone prove why this approach works (or give a counterexample)?

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

      Can you please tell me why we can't assign the value of the global shield greedily as I did (in my approach explained above)?

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

        Perhaps, you want to make the special shield higher than the minimum uncovered one.

        Consider n=3, h=2, t=1, and protection[]={10,1,10} and the two simple shields you have cover [0,0] and [2,2].

        Here, it's optimal to power the special shield with 10, and not use the simple shields, giving 10 cost overall. If I didn't misunderstand, your solution would give 1+9+9=19. Does this make sense?

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

        I had the same approach as yours, but I see our mistake now. If you have n shields next to each other one by one and low cost for supershield power, you'd like to use supershield once for all plants.

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

      I thought about that, but can it be possible, that values will be x, x, ..., x, x+1, x, ..., x, so we can not do ternary search on it?

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

        Maybe it's possible but recall that the parameters are generated by LCG, so are kind of quite random.

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

    I did ternary search on the value of the special shield. But need to set left boundary to the first position where there is a solution.

    First, need to sort intervals and remove redundant ones (e.g. which are fully covered by some other interval).

    When checking given value of the special shield, simply sweep through cells from left to right, checking for each interval start/end. Assume interval starts, then before the next interval you have to cover everything with the previous one. But you need to remember the intervals which were opened previously and how much money you have put in them. I used queue for that.

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

      Can you please tell me how you proved the function is unimodal (before ternary search)? Or was it intuition?

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

        Just intuition..

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

          It is actually not unimodal, simple example is when the cost of supeshield is 1 and we have to cover one plant — we can distribute the power between super- and regular shield in any way. What makes ternary search possible is that only the minimum value can be repeated by this function.

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

            "What makes ternary search possible is that only the minimum value can be repeated by this function" Can you please explain this part in some more detail? I was under the impression that ternary search can only be applied to unimodal functions.

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

              Suppose that the only value that the function can take more than once is the absolute minimum (which you are looking for), i.e. if f(a) = f(b), a ≠ b then f(a) = min f(x). Then you can just run standard ternary search and if the function ever takes the same value in 2 different points, you immediately know the minimum.

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

I think that they could have done a better job in setting point values for the problems. In my opinion it should have been: 300, 350, 1000.

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

Can someone explain me why this solution is incorrect?

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

    EDIT: Rewrote comment.

    The constraint "if len>=n" stop and return -1 applies to the original n, not the last number in the sequence (they never call that n). Not saying it was a misunderstanding; I just know I had a bit of confusion over this and had to reread a couple times.

    Others definitely also made this mistake, and 1e9 catches it as hellman_ said below, but even if you add a catch for "if (n==1) return -1;" you can still fail for example on 1162.

    1162->42->20->4 (now len>=n and you break)->16->17 (answer).

    I think this is where most hacks were from, but also some people in my room just used a bool prime[] array and failed on big primes.

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

      I had another related bug (and I think many others did too). The constraint applies to original n, so we need to check that sequence does not loop. I didn't do it, my thought was that "n will be small after few steps so does not matter". So I was hacked with 1000000000, which looped on 1.

      PS: maybe on C/C++ it would still pass, but I coded on python.

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

        It failed on c++ as well, I tested my own code before submitting on that with removing my check for loops, took 4.5 seconds, and then I hacked a couple of people using c++ or java with the same bug as you using 10^9

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

      It is not misunderstanding

      I think he just forgot to add a new variable for max len of sequence

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

      Oh, stupid bug :( Thank you for your explaining, I was thinking that something wrong with tests.

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

Is it rated?

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

It seems weird to me that Topcoder is always so slow at updating the ratings on the website, I can't really think of any reason why it shouldn't be quite fast to just transfer the data from the applet to the website?? Does anyone know any explanation for why it's so slow??

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

This guy : saisumit has obviously cheated. No actions against him? He got to blue!

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

    leave it to karma

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

    Why downvotes? This guy solved 250 in 21 seconds and 500 in 47 seconds. See here too. Such a gifted coder!

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

    I just saw this post so i need to clear things a bit , First of all apologies , both arrogantidiot and zoomswk are correct but partially , as u can see this was my 3-4 serious contest on topcoder , i was there in my friends room when i saw the questions on his screen and thus coded them there only without knowing the fact( again my ignorance ) that topcoder judges on relative time unlike codeforces ,and that is when things went a bit haywire ,and unknowingly and unintentionally the following scenario happened , I would be more than glad , if u can provide some help on how to unjudge my problems .

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

      I am sorry, but I dont see why we are partially correct! If you dont know the rules, that's YOUR problem. I believe you can own up to the topcoder admins and get yourself off the leaderboard (with / without some penalty).

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

        thanx for the advice, but i have already sent a mail to topcoder before i actually saw your post. but again thanks for the advice and if u want anything else from my side u can message , i will surely ponder upon that

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

          I understand that you did it unintentionally, and it's great that you are trying to be responsible for the consequences. I don't know how TopCoder will react to this situation but you might be removed from the leaderboard, and the problem won't really be a big deal (assuming that you and your friend did not share solution ideas).

          I'm sorry for you and hope you understand my and arrogantIdiot's raising the issue, since it might affect other participants to some degree. :D

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

Seriously, can anyone prove the solution for hard? I made something like ternary search (with parameter -- number of expensive segments) and after walking in both directions as not getting TL. And was really surprised when got AC without any walking. Is that even true that f(i)-f(i+1) is not increasing?

→ Reply