SRM 716 will start in 1 day,

Time: 9:00 pm EDT Monday, June 26, 2017

Calendar: https://www.topcoder.com/community/events/

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:

• First place: $250
• Second place: $150
• Third place: $100

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

Time: 9:00 pm EDT Tuesday, May 30, 2017

Calendar: https://www.topcoder.com/community/events/

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

Time: 9:00 pm EDT Wednesday, April 26, 2017

Calendar: https://www.topcoder.com/community/events/

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:

• 713 Wed April 26, 9pm
• 714 Thursday May 11, 11am
• 715 Tuesday May 30, 9pm

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

Time: 9:00 pm EST Thursday, March 9, 2017

Calendar: https://www.topcoder.com/community/events/

Topcoder SRM 709

Time: 11:00 am EST Tuesday, February 21, 2017

Calendar: https://www.topcoder.com/community/events/

Topcoder SRM 708

Time: 7:00 am EST Thursday, February 9, 2017

Calendar: https://www.topcoder.com/community/events/

Topcoder SRM 707

Time: 9:00 pm EST Monday, January 30, 2017

Calendar: https://www.topcoder.com/community/events/

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

Time: 9:00 pm EST Wednesday, January 11, 2017

Calendar: https://www.topcoder.com/community/events/

Topcoder SRM 704

Time: 7:00 am EST Thursday, December 29, 2016

Calendar: https://www.topcoder.com/community/events/

Topcoder SRM 703

Time: 9:00 pm EST Tuesday, December 13, 2016

Calendar: https://www.topcoder.com/community/events/

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:

• If you got top 10 in one of the 4 onsite regionals (and you haven't advanced to TCO onsite finals yet), then this is your last chance — top 2 will advance to onsite finals!
• For other people, you can participate in the parallel round, it will be rated. This is open for both division, but the difficulty will be at least as hard as Div1 in SRM.

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://mirror.codeforces.com/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:

1. Problem Statements

2. Simple editorial

3. Live update (like: tourist submitted his Hard with 789.01 score / Petr start to write Medium, seems he is on the good track!)

4. 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

Petr and ACRush

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.

1. There is a cycle, its length is not a divisor of 3: For example, if there is a cycle 5->6->5. Then f^6 (5) = 5, but f^3 (5) = 6, they are not equal.
2. There is a node, the distance to cycle is larger than 2 + 1 = 3:

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:

1. Let e[0] = 1, if there is an edge(i->j), then we set e[i] = e[j] — 1. By this we can get e[i] for all nodes in 0's component. We set i*j = f^(e[i]) (j).
2. For all element in other component, we set: i*j = i.

We could verify it is a valid solution.

Short Editorial of SRM 658 Div1

Reference Code:

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

Editorial:

Div1-Easy:

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:

1. x[0][0] should be 'E'.
2. there should be at least one node in both part, i.e. there should exist i such that x[0][i] = 'O'.

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

Div1-Medium:

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:

1. For each i, x9[i] * 9 + x3[i] * 3 + x1[i] * 1 ≥ x[i]: this means the i-th SCV must received enough damage to be destroyed.
2. , and : this means we can't have more then t 'attack as first/second/third target'.
3. For each i, x9[i] + x3[i] + x1[i] ≤ t: this is because one SCV can not be attacked more than t times totally.

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?

Div1-Hard:

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.