hmehta's blog

By hmehta, history, 5 years ago, In English

Hey All!

Topcoder SRM 770 is scheduled to start at 12:00 UTC -4, Nov 2, 2019. Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins.

Interested in working at Google? Well as a #TCO19 sponsor, they are looking to hire folks like you! Join us for SRM 770 to opt into their exciting job opportunities!

Thanks to jy_25, lazy_fox, idiot_owl and ashisha690 for writing the problems for the round. Also thanks to KaasanErinn and DuXSerbia for testing the problem set.

This is the third SRM of Stage 1 of TCO20 Algorithm Tournament.

Stage 1 TCO20 Points Leaderboard | Topcoder Java Applet | Next SRM 771 — Nov 27, 11:00 UTC-5

Some Important Links

Match Results (To access match results, rating changes, challenges, failure test cases)
Problem Archive (Top access previous problems with their categories and success rates)
Problem Writing (To access everything related to problem writing at Topcoder)
Algorithm Rankings (To access Algorithm Rankings)
Editorials (To access recent Editorials)

Good luck to everyone!

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

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

off-topic : Algorithm Rankings is broken

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

Gentle Reminder: Round begins in 4 hours :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If problems are hard to come by -- maybe incentivize the problem writing a little bit more. If the budgets are a problem, then maybe introduce a tipping system where after the contest people may tip the writer for a good problem. A lot of us might want to reward good writers to keep the good problems keep coming.

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

    I think it's more on the platform limitation that discourages people to write problems for TC.

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

    Topcoder pays maybe best among all the platforms. But their software is bad :|

»
5 years ago, # |
Rev. 13   Vote: I like it +61 Vote: I do not like it

I was the setter for div1. 450 and 900

450
900
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The 900 explanation is a bit too short for me... Can you elaborate on the part in which a sum turns into an integral?

    Maintain the probability that for all $$$j \geq i, a_j \le A_i$$$

    I noticed this was necessary during the contest but didn't know how to do this, so at least to me it is not obvious. Reading the code makes it much clearer: if you have the probability $$$p_i$$$ that $$$j \geq i, a_j \le A_i$$$, to get $$$p_{i-1}$$$ you have to remove the cases in which $$$j \geq i, A_{i-1} \le a_j \le A_i$$$, so $$$p_{i-1} = p_i \left(1 - \left(\frac{A_i - A_{i+1}}{p}\right)^{n-i+1} \right)$$$.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Assume we had to find the sum over $$$r \geq 0$$$. We can erase the $$$r=0$$$ case later. Let $$$q = \frac{p}{1-p}$$$ $$$\displaystyle \sum_{r >= 0} \binom{k}{r} \left (A_{i} - \dfrac{d}{r+1} \right) p^r (1-p)^{k-r} $$$

      = $$$ \displaystyle A_i - \displaystyle \sum_{r \geq 0} \binom{k}{r} (1-p)^k q^r \dfrac{d}{r + 1}$$$

      = $$$\displaystyle A_i - \displaystyle \dfrac{d(1-p)^k}{q} \displaystyle \sum_{r \geq 0} \binom{k}{r} \dfrac{q^{r+1}}{r + 1}$$$

      Note that the sum can be obtained from the integral $$$\displaystyle \int_{0}^{q} (1 + x) ^ k dx = \displaystyle \sum_{r\geq 0} \binom{k}{r} \displaystyle \int_{0}^{q} x^r dx = \displaystyle \sum_{r \geq 0} \binom{k}{r} \frac{q^{r + 1}}{r + 1}$$$

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

    Solutions like the one you're trying to avoid can pass pretty easily: compute logarithms of summands, ignore those which are too small (they can't be too large) and add/subtract exponentials of the rest. Also, compute all logs as long doubles.

»
5 years ago, # |
Rev. 4   Vote: I like it +12 Vote: I do not like it

The Div1 900 — "seemed" very similar to TCO19 Round 3A 500, however, the difference of asking minimum/maximum made all the difference in some concepts of solutions (at least for me). Great.

»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

My solution to div1. 450 failed system test.
When I submit the same code to the same problem in Practice Rooms, I got accepted (I tried multiple times).
How come?

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

    Did you run the test too, just submitting in practice does not the test on it. You will need to go to practice options and run the tests.

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

      He didn't.

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

      Thx! I didn't know that. Now I can get FST in Practice Rooms.
      BTW, can I get full feedback in web arena like the one in java applet?
      It just tells me that I failed.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do div2 900?

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

Because of the floating-point numbers, the Div. 1 900 was plagued with precision issues -- many of the competitors who failed would pass by replacing double with long double. Other competitors also managed to squeeze quadratic solutions through by quitting out early once the probabilities got low enough. I think the problem would have been better off asking for the expected value mod $$$10^9 + 7$$$.

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

    Yeah, I agree.

    Actually, the intended solution is different than the accepted solutions, and there is no precision issue in the intended solution. Most of the solutions are making the formula that comes from breaking the obvious integral into n intervals pass. I couldn't think a way of calculating it precisely and was therefore under the impression that it can't be made to pass. Thinking that making the answer real would fail these solutions and the problem would actually be hard, I didn't use 10^9 + 7.

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

      I think my solution is quite precise, by correctly joining each subtraction with addition (I mean, at least after you replace ii / (ii + 1) — (ii — 1) / ii with 1 / (ii * (ii + 1)), you only have additions)

»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

My screencast with commentary: https://youtu.be/3oIrxt5Btvc

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

    I respect that you are able to comment in English during the contest. Did you notice to be significantly slower because of that? Would speaking in Russian be easier for you? I'm just curious.

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

      Just tried this today in the AGC, and it didn't seem to matter both objectively — still struggling to come up with correct algorithms — and subjectively — did not feel that different.

      So I guess if I'm significantly slower, it does not depend on the language :)

»
5 years ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

For Div2 Easy, Hard (Also Div1 Easy) — prepared by me and mridul1809 and Div2 Medium — prepared by timmac

Div2 Easy
Div2 Medium
Div2 Hard - Div1 Easy
  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    So it looks like one can pass Div2 Medium by trying the 3 rotations and one type of flip.

    But there are four types of flip (vertical, horizontal, diagonal and antidiagonal) like this:

    https://www.cs.umb.edu/~eb/d4/index.html

    So, it may be nice in the problem statement to describe the "flip" more precisely. I first tried to implement all the four types of flips and then spent a lot of time thinking about whether the order of operations matters (reading the above web page, etc.), but the intended solution was much simpler. (Luckily I was not in the contest, just practice).

    Nice problem otherwise, great for division 2 500. Thanks!

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

      Hey royappa !
      You can perform rotations and flips together as well! So a flip along diagonal is same as horizontal flip along with a rotation!
      Total number of ways of arranging them will be 8 (4 x 2) ( 4 rotations , 2 flips ).
      So the different flips you mentioned are actually being covered in the testcases.
      I would suggest you that you should go over you code once again as your logic seems right!

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

    coud you give some intuition on why using only 2s and 3s is sufficient

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

      You need to maximize the number of moves. So you need to move using small primes. Since 2 covers only even difference between $$$P$$$ and $$$Q$$$, we also use 3 for odd differences.

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

    Hi, In Div2 Hard, how will the cost of removing be a∗x+b∗y+c∗z+sum of all elements in all the arrays. I understand the sum of all elements part, but I have having trouble understanding a∗x+b∗y+c∗z. Could you please explain why that would be true ?

»
5 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Bonus : Solve div1 450 for a general graph :

Given a graph with weights on vertices, find the maximum weight of a subset of vertices that can be covered by $$$k$$$ edges of the graph.

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

    It is obviously not easier than matching in general graph, and reduction to weighted matching in general graph is easy. Doesn't look like a good problem.

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

      I don't think I have an easy reduction. How do you reduce it?

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

        For each vertex $$$v$$$ with non-zero degree let's add dummy vertex connected only to $$$v$$$ with weight 0. Now we can always choose $$$k$$$ edges such that they are a matching.

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I am so tired of writing code to generate large arrays in topcoder. I know their system doesn't allow large inputs but it's still pretty bad.

This one felt especially bad since the B array was generated differently from the other for whatever reason, so you needed to be careful with the copy paste :.

Maybe they should have only one way of generating random arrays (probably the one that the first 1000 elements are given and you generate the rest, so it's easier to hack), and then just have sample code in all the languages.

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

    But for Div1 300 this time, if testcase is not random (like first 500 elements are given), it will be very tricky. Even success rate 25.0% is possible. That's because:

    • The case of which $$$|A| + |B| + |C|$$$ is odd and the minimum element of $$$A, B, C$$$ are same, but $$$x, y, z$$$ are all different
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't quite get the issue. The method they usually do, like they did for 900, let's you generate random tests like A but also manual ones, so you just have more options.

      Also more importantly I am tired of writing the code to generate large arrays. They should either update the platform or make a easier way to generate the large arrays.

      I also remember when the problems had small N, but using the same idea you could solve it will large N, but since the idea was the hard part, they could just keep N small.