SRM 716 will start in 1 day,
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
SRM 716 will start in 1 day,
TCO Round 2A will start at 12:00 noon EDT Saturday, May 20, 2017
Top 40 will advance to Round 3 and will get a T-shirt.
Find more details here: https://tco17.topcoder.com/algorithm/rules/
First regional round of Topcoder Open 2017 will take place this Saturday!
Time: 2:30 pm CDT Saturday, April 29, 2017
As usual, top 10 will advanced to Wildcard round, then top 2 from Wildcard round will advanced to TCO Onsite Finals later this year. And top 3 will win cash prize:
And there are not only algorithm contest, you can find more information about this onsite event here: https://tco17.topcoder.com/regional-events/austin-texas/
If you haven't advance to Round 2 yet — don't miss the last opportunity.
Round 1C will start at 12:00 noon EDT Saturday, May 6, 2017
You need to get top 750 with a positive score to advance. Note that if you have already advanced (in 1A, 1B or received a bye), then you can't participate.
Find rules this year with the schedule here: https://tco17.topcoder.com/algorithm/rules/
Exactly 1 week after Round 1A, we will have our 2nd TCO round.
Time: 12:00 noon EDT Saturday, April 8, 2017
You need to get top 750 with a positive score to advance. Note that if you have already advanced (in 1A or receive a bye), then you can't participate.
Find rules this year with the schedule here: https://tco17.topcoder.com/algorithm/rules/
Topcoder Open is back! The first round will be 1A:
Time: 12:00 noon EDT Saturday, April 1, 2017
As usual top 250 active coder will advance to Round 2 directly. We will announce the list of coder a bit later, at this time you can check this blog: https://www.topcoder.com/blog/next-algorithm-track-automatic-berths/
You can find rules this year with the schedule here: https://tco17.topcoder.com/algorithm/rules/
Update: Byes are announced here (cut-off rating is 1783): https://tco17.topcoder.com/algorithm/byes/
Topcoder SRM 715
Topcoder SRM 714
Time: 2:00 pm MSK Sunday, May 7, 2017
At the same time there will be an onsite contest: https://tco17.topcoder.com/regional-events/st-petersburg-russia/. We will share problems for both SRM and this regional contest.
Calendar: https://www.topcoder.com/community/events/ (Note: Still not updated)
Topcoder SRM 713
Topcoder SRM 712
Time: 7:00 am EDT Tuesday, April 18, 2017
Calendar: https://www.topcoder.com/community/events/
There are 3 more SRMs on schedule:
I will add them tomorrow since 'You can create no more than 3 blog entries per day'.
Topcoder SRM 711
Time: 5:30 am EDT Saturday, March 25, 2017
Calendar: https://www.topcoder.com/community/events/
Update: we moved the SRM 1 week later (and the start time has been changed).
Topcoder SRM 710
Topcoder SRM 709
Topcoder SRM 708
Topcoder SRM 707
Topcoder SRM 706
Time: 11:00 am EST Saturday, January 21, 2017
Calendar: https://www.topcoder.com/community/events/
Update: Sorry but the link to the time was wrong, please click again and see local time in your timezone.
Topcoder SRM 705
Topcoder SRM 704
Topcoder SRM 703
As Errichto suggested here, I will post date/time of upcoming SRMs once I know, and will update it about 24 hours before the contest so it will be in the "Recent Actions" list.
SRM 702 will start on Nov 14 at 9pm EST. Note that Daylight Saving Time will end on Nov 6.
This is the last SRM before Topcoder Open 2016, so please come and compete if you want to practice once more. :)
Update: the contest will start in less than 1.5 hours.
Hi there,
Topcoder SRM 698 will start in about 9 hours (Sept 17, 12:00 noon EDT).
This round is Sponsored by Google, find more details here.
Thanks for participating! The Div1-Medium and Hard were prepared to be used in TCO Round 3B, but shangjingbo told me they are too easy (he got the idea for each of them in 10 minutes). It turns out they are not that easy. :P
Hello there,
TCO2016 Online Wildcard round will start at 12:00 noon on Sept 10 EDT:
Welcome to participate and hope you can enjoy it!
Update: jqdai0815 and tourist are top 2 and will advance to onsite finals, congratulations!
Hello everyone! Tomorrow we will know who is the TCO2015 Algorithm winner!
Do you remember misof did live coverage in previous years like this: http://codeforces.me/blog/entry/14753
This year he is not here at Indy. rng_58 and me (we coordinate TCO algorithm contest together this year) will do live coverage this time!
You will be able to read them here: https://www.facebook.com/TCO2015Algorithm
Today I will post some updates about Marathon contest to make sure I know how to post picture / video quicky, and you can get familiar with that facebook page.
Please let me know what you want to see beside the following:
Problem Statements
Simple editorial
Live update (like: tourist submitted his Hard with 789.01 score / Petr start to write Medium, seems he is on the good track!)
Photo of current scoreboard (is that needed?)
Thanks! See you tomorrow!
Update: We just heard that contestants have internet access during the contest. So we can't publish statements / solutions until the end of challenge phase. We will publish solutions after the end of challenge phase.
Update2: We will publish problem statements once all contestants opened it.
Semifinal:
Statement: https://docs.google.com/document/d/1D0WUDNeWWlpM7ixNMlW7K2FMSk2sXSuOKEyGT-7M3IA/edit?usp=sharing
Editorial: https://docs.google.com/document/d/15zjuih75vzK6VYyi4gSRXdn62lkT8zQiGcJT64qBNp4/edit?usp=sharing
Result (Top 5 advanced to finals):
Final:
Statement: https://docs.google.com/document/d/1putaFIk4OUVlJBzICaA8m7Znd2prVWwQj4P0F6SlsL0/edit
Editorial: https://docs.google.com/document/d/1oJlKlyr3HHKgDEH0sEawXsG31rnOBWaEWHbEq7wFqRk/edit
Winner
Div2-Easy: http://ideone.com/uzGzxa
Div2-Medium: http://ideone.com/EXVZ7f
Div2-Hard: http://ideone.com/04H4H8 (This solution can solve n <= 50 instead of 3)
Div1-Easy: http://ideone.com/HMjObD
Suppose the heights are sorted: h[0] <= h[1] <= h[2] ...
In one hand, we know the answer can't be smaller than max{x[i+2] — x[i]}. We can proof this in the following way: If abs(x[i]-x[j]) >= ans, we add an edge between i and j. We assume there is an i and ans < x[i+2]-x[i]. Then if the graph is connected, edges (i, i+1) and (i+1, i+2) will be bridege (since if x < i and y > i+2 then there is no edge between x and y.) It means this graph don't have a hamiltonian cycle, so we can't arrange these foxes around a round table.
In another hand, we know that we have a solution that ans = max{x[i+2]-x[i]}: x[0]-x[2]-x[4]-x[6]-...-n-...x[5]-x[3]-x[1]-x[0].
So we know this solution is optimal.
Div1-Medium: http://ideone.com/pQhKaG
We can compute S in the following way: For each edge, let s1 be the number of nodes in one side, we know there are s1*(n-s1) paths use this edge. So S = sum{s1 * (n-s1)}.
So we can solve it by dp: let dp[i][j] = minimal number of S such that we have a tree with i nodes and sum{s1 * (n-s1) among all edges it have} % m = j. Each time we pick 2 rooted trees, merge them: root1 becomes a son of root2. We can compute the new sum{s1 * (n-s1)} in O(1). So our algorithm can run in O(n^2 m^2).
Div1-Hard: http://ideone.com/b4v3nY (rng_58's code)
The given input is a mapping from {0,..,n-1} to itself, it is x=>(0*x), we call it f. Suppose 0*0 = 3, then what can we get? We know that 3*x = (0*0)*x = 0*(0*x) = f(f(x)) = f^2 x. So it means x=>(3*x) is f^2. And if we know 0*3 = 5, then we should get x=>(5*x) is f^3..
We construct this graph: for each i, we add directed edge from i to firstRow[i]. Then there must be some connected component, each one is a cycle with some tree towards the cycle. Suppose we have path: 0->1->2->3->4->2. (it means the component of 0 have a cycle length = 3, and the distance from 0 to cycle is 2). Then we have: f^6 = f^3. Then we know in the following cases there is no solution.
For example, if there is a path: 7->8->9->10->11->11, then we have: f^6 (7) = 11 (something on the cycle), but f^3 (7) = 10 (something not on the cycle). Beside these 2 cases, the solution always exist:
We could verify it is a valid solution.
Short Editorial of SRM 658 Div1
Div2-Easy: http://ideone.com/O7yBlI
Div2-Medium: http://ideone.com/cazTBB
Div2-Hard: http://ideone.com/rxEUcR
Div1-Easy: http://ideone.com/JLuDVM
Div1-Medium: http://ideone.com/7FEz1K
Div1-Hard: http://ideone.com/clL4Rk
The key is that: Any tree is a bipartite graph!
That means, if two nodes are in the same part, then the distance between them is an even number, otherwise it is an odd number.
Assume the 0-th node is in first part, then we can know which part each node belong to by looking at x[0][i] : if x[0][i] is 'E' then i-th node should be in the first part, otherwise it should be in the second part.
There are few things to check:
And then we can check if for all i,j: x[i][j] = (i-th node and j-th node in the same part ? 'E' : 'O'), if not, there is no solution.
Otherwise we can build any spaning tree of this complete bipartite graph, for example we can use this:
1 - 1
1 - 2
1 - .
1 - m
2 - 1
3 - 1
. - 1
n - 1
Suppose for the i-th SCV: it received x9[i] times attack as the first target (so damage is 9), x3[i] times attack as second target, and x1[i] times attack as third target.
If we totally attack t times, then these conditions are necessary:
What's amazing is that these 3 conditions are sufficient. I will skill the proof here (In fact I don't have a nice one -- it is ordinary case analysis, if you know a better one then please tell us, thanks!)
Then it becomes easy: First we do the binary search for the answer. Then we can do DP. DP[cur][i][j] := if we use totally i times 'attack as first target' and j times 'attack as second target' to kill all first cur SCV, then what's the minimal number of 'attack as third target' can be?
This task ask the following thing: given a bipartite graph with n nodes in both part, find b: a subset of boys such that: 1. the girl they loves, or say, the neighborhoods of b: |neig(b)| = |b|, that means, any of them don't love girls that is not in this matching. 2. There is a matching of these |b| boys with these |b| girls.
Formula like |neig(b)| = |b| give us a hint for Hall's marriage theorem: Suppose the maximal matching of this bipartite graph is n — d, then we can find b, a subset of boys, such that |b| — |neig(b)| = d. (We can use maxflow algorithm to find such set, by getting the minimal cut)
And then we can do max matching for these |b| boys and |neig(b)| girls, it will give you a valid answer (so we never return {-1}). Why? You can prove the maximal matching of this subgraph is |neig(b)|, once again, by Hall's marriage theorem.
Название |
---|