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
Rank | Competitor | Total Point |
---|---|---|
1 | yosupo | 1126.37 |
2 | Petr | 743.11 |
3 | tourist | 733.44 |
4 | sky58 | 722.65 |
5 | nika | 710.03 |
2. Division 2
Rank | Competitor | Total Point |
---|---|---|
1 | r3gz3n | 782.27 |
2 | mariandz | 781.66 |
3 | Trias | 757.82 |
4 | geek_geek | 750.79 |
5 | sachintcthope | 739.68 |
Congraturations to winners!
Reminder: 25 minutes to start.
Note that registeration closes 5 minutes before the contest.
How to solve Div1 250? I was trying a solution using DP + Combinatorics. But too much inclusion exclusion. Couldn't able to handle.
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
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
Thanks a lot. I was only fixing d1 during the contest. But fixing both d1 and d2 make it a lot easier to handle!
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.
Here's a nice solution! (scroll down to the bottom)
I hate problems where it is much easier to guess the answer than to prove it. Why not to leave such problems for mathematics olympiads...
But the proof is interesting anyway.
Actually...
Nice Problem. Thanks.
1000: LP Duality. But I use mincostflow with F=V=1000, E=50000, so I don't know why my program is so fast.
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.
Hell, you probably need a psychotherapist.
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.
Everybody Hurts :/
mama's gonna help you build the wall
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) :)
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.
For each edge e, we can write f_e(X) = |X — old_weight[e]|.
Let f_e'(X) = f_e(X) — f_e(X-1) (i.e. the "derivative"). We can notice this function is non-decreasing.
Now, given the number X, let's assign weights to our graph so that the weight of the node corresponding to edge e is f_e'(X).
Let's find the minimum weight closure in this graph (which can be found with max flow). Denote this closure as C.
Now, we claim that that nodes in C have new_weight[e] >= X and all other nodes have new_weight[e] < X.
Let the set of all nodes be V. Suppose in an optimal solution, there are nodes in C which have new_weight[e] < X. Let this set of nodes be D. There can't be any edges from C-D to D (since in the optimal solution, new_weight[i] > new_weight[j]). Thus, we can see that C-D is a closure. Since C is a minimum closure, the weight of C-D is at least the weight of C. In particular, the weights of all the nodes in D must be nonpositive. Since the derivative is non-decreasing and is less than or equal to zero at X, increasing the new_weight of nodes in D to X would not increase the value of our optimal solution and is a valid operation. (this is valid because there are no edges from D to V-C since C is a closure).
Thus, we can conclude all nodes in C have new_weight[e] >= X. Consequently, we can show the opposite directions which is that nodes in V-C have new_weight[e] < X in a similar way.
For a single X, this requires running flow on a graph with O(m) nodes and O(nm) edges. You can see a sample implementation below
This technique can also be used to solve this problem in O(n log 10^9) time. (see code here)
I think you're describing an approach from this paper, while yosupo is describing an approach from this paper :)
The total point distribution graph on this SRM is following:
How to solve div 2 1000?
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.
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
I like this announcement and stats. Keep up good work!
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.
According to this page your rating has already been updated to 2203.
Ohh, yeah you're right. Thanks. I was more than sure that my old rating was 2203 and I saw no change
Can anyone discuss their approach to solve div2 level2 problem? (MinProduct)
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.
Can anyone explain the approach for solving div 2 (1000 point) problem? More on Idea part. Thanks.