E869120's blog

TopCoder SRM 720 Announcement
By E869120, 7 years ago, In English

TopCoder SRM 720 will starts in ~8 hours.

Time: 8/24 07:00 EDT, 8/24 11:00 UTC, 8/24 14:00 MSK
Duration: 75 minutes coding phase + 5 minutes intermission + 15 minutes challenge phase

You can check the future contests from calendar.

Let's discuss after the contest.

Final Results

1. Division 1

RankCompetitorTotal Point
1yosupo1126.37
2Petr743.11
3tourist733.44
4sky58722.65
5nika710.03

2. Division 2
RankCompetitorTotal Point
1r3gz3n782.27
2mariandz781.66
3Trias757.82
4geek_geek750.79
5sachintcthope739.68

Congraturations to winners!

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

»
7 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Reminder: 25 minutes to start.
Note that registeration closes 5 minutes before the contest.

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

How to solve Div1 250? I was trying a solution using DP + Combinatorics. But too much inclusion exclusion. Couldn't able to handle.

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

    Find all possible pairs of numbers and put them in all possible positions then multiply with how many way we can find a number A with length blank1 — 1 and number B with length blank2 — 1 by using remaining numbers

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

    Let's denote the two numbers as A and B. Let's fix any two digits d1, d2, such that d1 occurs in A at index x1 from the right (beginning with 0). Similarly define x2. Note that you can expand both A and B in base-10 representation.

    So you have d1 * 10x1 in A and d2 * 10x2 in B. How many times does their product appear in the final sum? Well, note that all the remaining blanks are distinct, and you have amount quantities of each digit. The number of ways in which you can fill B blanks with digits 0 to 9 each with available quantity ti for each digit i is the coefficient of xB in:

    Edit 1: Code

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

      Thanks a lot. I was only fixing d1 during the contest. But fixing both d1 and d2 make it a lot easier to handle!

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

How to Solve 1000?

And how to prove the most distinct numbers is n × (k - 1) + 1 in 450? I just solve 450 by guessing.

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

1000: LP Duality. But I use mincostflow with F=V=1000, E=50000, so I don't know why my program is so fast.

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

I opened 450 at first and didn't believe the solution to be so simple and spent 10min on finding counter examples to it. Then I spend some time on 250 and found that I misunderstood the statement. Then I opened 1,000 and found that it is similar to the problem in this article. Thus, I spent much time doing duality. Near the end of the contest, I tried to write simplex but soon realized that there wasn't much time left. I didn't manage to solve 250 for the rest of the time.

Then for the challenge phase. I blindly challenged a late submission of 250 and found that it passed the last two examples. Then I did another unsuccessful challenge and lost 75 during challenge phase(but it meant nothing since I would lose many ratings anyway).

Now I am silver in IOI, no longer LGM in Codeforces nor a target on Topcoder. To add insult to injury I didn't make it to the final round of any contest, including RCC on which I made it last year. Congrats matthew99, you lost everything now.

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

    Hell, you probably need a psychotherapist.

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

      Sorry, btw. It wasn't making fun of you in any means. But if you wrote this seriously: "Congrats matthew99, you lost everything now", then you probably really have some problems. It is not OK to feel something like this toward the olimpiads and rating.

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

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

    Everybody Hurts :/

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

    mama's gonna help you build the wall

    → Reply
»
7 years ago, # |
← Rev. 7   Vote: I like it +49 Vote: I do not like it

My feedback of this Div1 round:

- Easy(250): Interesting DP and mathematics problem. Topcoder has many interesting problem in Div1 Easy. But I think this problem is difficult for Div1 Easy.
- Medium(500): I solved, but I couldn't prove it. I don't like "difficult to prove it, but you can see the solution from small-case experiment" problem. I think Topcoder can publish interesting and non-small-case-experimentable problem (I wrote this issue in a thread in topcoder forum).
- Hard(1000): It's too difficult and only yosupo solved it. But I believe it's a good problem.

Anyway, I want writer's commentary (I guess the writer is Lewin) :)

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

    Yes, I was the writer. I'm on vacation right now, so I'm not able to provide detailed comments.

    I agree that div1 easy is harder than usual. Also, the med was only placed at that level because it is hard to prove, but perhaps it is not that great of a problem in the first place. The med is too much of a math problem, and not really a programming problem (the tester bought this up, but I thought it was ok to experiment as is).

    For the hard, I have a different intended solution from the one from yosupo. Let's solve a more general problem, where we have an arbitrary directed graph with m nodes (for each edge in the original graph), and we have a directed edge from node i to node j if new_weight[i] <= new_weight[j].

    Given a number X, we can determine which nodes will have new_weight[i] <= X in an optimal solution. The rest of the solution is in the spoiler below.

    solution

    This technique can also be used to solve this problem in O(n log 10^9) time. (see code here)

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

The total point distribution graph on this SRM is following:

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

How to solve div 2 1000?

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

    Its probably bitmask dp. Divide the nodes into buckets of different colors. There are 10 such buckets. Now, in each bucket, do a bitmask dp to check whether a path can end on a node which visits all the nodes in that bucket exactly once. Now, again do a bitmask dp over all the buckets to find the number of ways. State should be something like dp[mask][last bucket used][last node used from the used last bucket]. Didn't code it but I guess it should work.

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

    My AC solution was like this:
    1. Calculate dp1[c][mask][first][last] — the number of paths of color c with mask of used nodes and fixed first and last nodes.
    2. Calculate ans[mask][last] — the number of paths with mask of used colors and a fixed last node. It can be calculated as a sum of ans[mask^(1<<color[last])][prev_last] * dp[color[last]][mask_with_all_bits_set][first][last] over all possible first nodes with color[first] = color[last] and prev_last nodes, which color is in mask^(1<<color[last]) and which have an edge to the first node.
    3. Answer is a sum of ans[mask_with_all_bits_set][v], where v is every node of the graph.
    code: https://ideone.com/y6RhFZ

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

I like this announcement and stats. Keep up good work!

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

Am I the only one whose rating wasn't updated yet? I mean it's already one day since the contest and the ratings were updated usually in less than an hours after the ending of the competition.

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

    According to this page your rating has already been updated to 2203.

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

      Ohh, yeah you're right. Thanks. I was more than sure that my old rating was 2203 and I saw no change

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

Can anyone discuss their approach to solve div2 level2 problem? (MinProduct)

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

    My solution was brute-force exponential.
    Let A have "n" digits and B have "m" digits.
    We assign n+m of the smallest digits from "amounts" to generate all possible A, B.

    To generate all possibilities you can use bitmasks or recursive backtracking. With bitmasks:
    - Iterate over all bitmasks from 0 to 2^(n+m)-1
    - Skip any mask which does not have exactly "n" 1-bits (and so, "m" 0-bits).
    - Loop through each bit of the mask. If bit=1, then give A the next smallest free digit from "amounts" array.
    - Otherwise bit=0, so append the next free digit into B instead.

    At the end of this process you have assigned digits to A and B in increasing order. Just compute A*B and track minimum.

    The match winner has a non-exponential solution but I haven't fully understood its logic, there's a lot of repeated code. I would love for someone to explain the greedy approach.

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

Can anyone explain the approach for solving div 2 (1000 point) problem? More on Idea part. Thanks.

→ Reply