I_love_tigersugar's blog

TopCoder SRM 631
By I_love_tigersugar, 10 years ago, In English

Tomorrow, the last SRM in August will be held at 12:00 EDT. It's sponsored by HP — as SRM 630. Don't miss it!

Enjoy your SRM, have fun and get high rating!

UPD: Contest ended. Let's discuss problems here!

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

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

And yes, you can try out the new Topcoder Web Arena in this SRM and get a chance to win an all-expenses-covered trip to TCO :)

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

    That sounds great! But there is something wrong with the Web Arena. I can't log in. It's always saying: "Login time out. Please try again at later time."

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

      I used it some time ago, (when everybody was struggling opening the Bayan contest page) and then it worked fine. It is in Beta version and there may be some issues. I am sure they will fix it.

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

        Try logging in to topcoder first, and stay logged in. Then open the topcoder arena.

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

    If we do take part in the round using the Web arena and it crashes during the contest , Would we be at fault or would Topcoder make the round unrated for us if we provide them with a valid proof of the problem with the web Arena ?

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

      You should have the jnlp arena ready to log in, in case that happens. And they mentioned that each one should use the web arena at their own risk since it's in beta phase and flawless performance will not be guaranteed!

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

        I am not sure if they will send us the feedback form in that case. Its mentioned that they will send the feedback form through mail to the contestants. May be, they will send feedback form only to those who have a submission from the web arena. I do not know. In any case, you have two choices:
        - Play the SRM from the applet. Everything goes off normally. At best one will solve more than expected and have a rating increase.
        - Play the SRM from the new web arena. Contribute to its development. Might be not able to submit any solution. Still have some probability to win a chance to witness TCO finals live. At worst, you will stake some ratings.

        My choice would be 2. Looks optimal to me.

        And EDIT : The arena is working for now.

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

          And EDIT : The arena is working for now.

          Talking about the web arena? I am still unable to locate the register tab, the rooms tab etc. Have they really been put up?

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

            There is a register button. But it does not work for now. This is what the admin said when I reported it to him — "There is an issue with registration on the web arena. You should be able to register and compete using the applet arena. If you register through the applet, you should be able to compete in the web arena. "

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

.

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

How did people solve 1000? I guess it is solvable in general case (without using the properties of random), but the solution is pretty insane...

I tried to use the fact that after some modifications queries will be fact due to the randomness, and deal with pieces of the original tree separately. Though I didn't process these pieces optimally, my solution was pretty close (~9 seconds for the most evil test (maxDepth=3) on my computer, which is ~1.5 times faster than topcoder machines). So it might be the case that this approach actually works if implemented properly.

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

    I've just copied the implementation of Linking-Cutting Tree from my template. Seems everyone who solved it except Petr did the same thing.

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

      Ah, I see! I forgot that I also have Link-Cut trees in my template library, and they can be used to solve such problems. I feel stupid :( Anyway, it's not a very nice problem if this is the intended solution.

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

        My solution worked 0.68s on the last test case on the server and I believe it will fit into 1s on all test cases. If it was the intended one, I think the TL would be 2s. That's why I guess the intended solution has complexity .

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

    SQRT-optimization, as usual :) The code turned out to be very simple.

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

What is the idea in Div1.B(500)? I saw a pretty AC solution, but didn't understand it.

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

    I have a dynamic programming solution. Let's sort pairs <coordinate; number of stones>

    Our state consists of position in the sorted array and additional flag, which can be 0 or 1.

    If flag is 0, then we must try to merge current heap and some other consecutive heaps in one big heap.

    If flag is 1, then we must try to split current heap and some other consecutive heaps in many heaps of size 1.

    It's important to do the second operation only in the beginning or after the operation of the first type, because this guarantees, that we have at least T free cells to the left of our current heap.

    Code

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

    There's a greedy solution which results in very simple code (see tourist's for instance).

    First sort the input by its coordinates and process the positions from left to right.

    For each position we may or may not be able to separate all cats. If we are we should put them as far left as we can (to not bother the following positions). If we aren't able to do so, we should put them as far right as we can. Why? Well, we must pay 1 to put a position with >1cat so let's take as much profit as we can; now, it's a bin where we can just throw all cats for free. Therefore, for each position:

    1. Check if the previous position is a free bin (>1 cat there) and we can get there in time. Yes? --> Throw them there :P

    2. Check if we can separate them. Yes? --> Put them as far left as you can without touching the previous position and satisfying the time constraints.

    3. We aren't able to separate them :( --> ++ans and put a free bin as far right as you can

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

Could anyone say how to solve task 3(div 2)?

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

    I've solved it with DP.

    Each state is represented by the current amount and the maximum power of 2 you have available. So you have dp[amount][maxpow].

    At each state you can explore three posibilities:

    • Ignore the coins with value 2maxpow and go to rec(n, maxpow - 1)

    • Take one coin of the kind 2maxpow and go to rec(n - 2maxpow, maxpow - 1)

    • Take both coins of the kind 2maxpow and go to rec(n - 2(2maxpow), maxpow - 1)

    The main problem you can find is that N can be so large, so you need to take into account two things:

    • You cannot use a normal matrix since N can be 1012. I've used a map with pair<long long, int> as key to store the states.

    • If you iterate through all states just doing what I mentioned above you will find that all N numbers will be visited multiple times, so you will have a time and memory problem. The search can be pruned if even with taking all available coins you cannot get the current amount.For that, you need to compare the current amount you have with 2(20) + 2(21) + .. + 2(2maxpow) = 2maxpow + 2 - 2, which can be done quickly.

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

      I did the same thing, but my solution took a lot of amount of time for even input 10^9 :( Can you somehow prove your time complexity or any intuition why it should work in time?

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

        Are you sure you did the very same thing? Take a look at my AC code: Solution

        This code would be very slow and incapable to solve N = 109 if you remove the additional check done at line 12.

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

          it was exactly the same solution, may be then my comparison function could for set could be wrong (First time using Java). I will look into the thing. Thank you !!

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

I have a problem about problem 500 SRM 631 div 2. In the statement: Each element of count will be between 1 and 1000, inclusive. But when I practice by running system test, I got wrong because in test #5: {{27, -79, -93, 0, 37, 42, 1, 26, 41, -34, -53, 22, 62, 52, 72, -83, 25, 18, 44, -87, -21, -4, -20, -74, 60, -88, 83, -71, 53, 32, 47, 48, 85, -39, 33, 13, 93, -94, -70, 87, -61, 39}, {2, 1, 2, 2, 1, 2, 0, 1, 1, 2, 2, 0, 1, 0, 2, 2, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 2, 1, 0, 2, 1, 0, 0, 0, 1, 1, 0, 2, 1, 0, 2, 0}, 24} It exist some elements of count (vector) equal 0. Is it the system input test wrong?

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

Oops ignore this. Thelast4 already reported it.

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

    Yes, there was a problem with the tests. They have already been fixed and, according to this thread everything should be ok now.

    It hasn't affected the round because the checkData (the validator for this problem) and the statement are correct.

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

      If by checkdata you mean testcases used in system testing I don't hink they are correct as my solution also got Failed System Test because of a testcase containing 0 as some elements of the count[] vector ; My Failed Div2 500

      Will there be a rejudge , If yes , Where would the results be uploaded ?

      Edit: System testing has been done and it has changed from failed system test to passed . Thanks topcoder admins

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

        No, by checkData I mean a method that checks whether a test case matches the constraints from the statement (i. e., validates challenges).

        They have already rejudged solutions, but it looks like the statistics are still wrong.

        You can contact admins in the thread on topcoder forums that I mentioned above.

        → Reply