cgy4ever's blog

By cgy4ever, history, 3 days ago, In English,

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/

Read more »

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

By cgy4ever, history, 5 weeks ago, In English,
 
 
 
 
  • Vote: I like it  
  • +21
  • Vote: I do not like it  

By cgy4ever, history, 5 weeks ago, In English,

Topcoder SRM 714

Time: [??:?? EDT Thursday, May 7, 2017]

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

Update: We moved this SRM to May 7 from May 11. Time to be determined.

Read more »

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

By cgy4ever, history, 5 weeks ago, In English,
 
 
 
 
  • Vote: I like it  
  • +25
  • Vote: I do not like it  

By cgy4ever, history, 5 weeks ago, In English,

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

Read more »

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

By cgy4ever, history, 5 weeks ago, In English,

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

Read more »

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

By cgy4ever, history, 5 weeks ago, In English,
 
 
 
 
  • Vote: I like it  
  • +59
  • Vote: I do not like it  

By cgy4ever, history, 2 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +71
  • Vote: I do not like it  

By cgy4ever, history, 2 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +53
  • Vote: I do not like it  

By cgy4ever, history, 3 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +35
  • Vote: I do not like it  

By cgy4ever, history, 4 months ago, In English,

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.

Read more »

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

By cgy4ever, history, 4 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +67
  • Vote: I do not like it  

By cgy4ever, history, 4 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +87
  • Vote: I do not like it  

By cgy4ever, history, 4 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +89
  • Vote: I do not like it  

By cgy4ever, history, 5 months ago, In English,

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.

Read more »

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

By cgy4ever, history, 6 months ago, In English,

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

Read more »

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

By cgy4ever, history, 7 months ago, In English,

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: TooDifficuIt and tourist are top 2 and will advance to onsite finals, congratulations!

Read more »

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

By cgy4ever, history, 17 months ago, In English,

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

Read more »

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

By cgy4ever, history, 21 month(s) ago, In English,

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.

Read more »

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

By cgy4ever, 23 months ago, In English,

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.

Read more »

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

By cgy4ever, 2 years ago, In English,

Hello, I'm the writer of SRM 655 Div1 Easy and Hard.

Div1 — Easy

The key is to thinking from last operation: it will make the final board have a k by k monochrome rectangle.

for example, if we have:

BBBW
BWWW
BWWW
WWWW

Then we know in the last step we may paint the right-down 3 by 3 rectangle. And that means, before this step, these 3*3 cells can be any color. So the board will looks like:

BBBW
B???
B???
W???

And we can see the previous step could be upper-left 3 by 3 rectangle (because we can change '?' to 'B' and that is monochrome), so we get:

???W
????
????
W???

And we are done, because if we change '?' to 'W' that is all-white board.

So the algorithm is: keep finding k by k monochrome rectangles and paint it into '?', until can't do it. And check if the board is all-white. You can proof no matter the order of rectangle we choose to paint, we will get the same result.

Code: http://ideone.com/xM13nh

Fun fact: I come up with this idea when I was playing a mobile game: Strata. Usually puzzle games are NP-Hard, but I find this one is not. :P

Div1- Hard

First let's think about how can I solve it if we change blue points to a circle:

(If you can't see the picture, please use this url: http://postimg.org/image/ssvbih7sd/)

For a point P, we say it covers the direction [OA, OB] of that circle.

We can prove: "circle totally in the CH of points" if and only if the union of directions of each point covers is all 360 degree.

The polygon version is same. We can change the vertex to an infinite small arc of circle. Then P will cover the direction [EF, CD]. The condition will remain same.

So the problem becomes: we have lots of interval of directions, each one have a certain probability of occur, you are ask the probability that the union will be [-Pi, Pi]. That could be solved by DP (my solution is N^3).

Code: http://ideone.com/Yq4ReK

Fun fact: there is a simplified version (2 blue points instead of up to 100, but require n^2 solution) used in TCO 2012 round 3B Hard wrote by ivan.metelsky, but today he was solving this harder version during the contest!

And congratulations to tourist! He solved all 3 tasks with highest score with 7 successful challenge!

Read more »

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

By cgy4ever, 2 years ago, In English,

Hello, I'm the writer of SRM 651.

It turns out this round is unrated due to some system failure. Sorry about the inconvenience it caused. I hope Topcoder can improve their infrastructure soon so that can be as good as codeforces.

I will post the problem statement, reference solution and a short editorial here.

Welcome to discuss the tasks, as well as to give feedback about them!

Problem Statement: http://www.speedyshare.com/2kRaC/task.rar

Reference solution:

Div1-Easy: http://ideone.com/a9siv1

Div1-Medium: http://ideone.com/sbEZSH

Div1-Hard: http://ideone.com/9JXoSL

Div1-Easy: RobotOnMoon

Look at this example:

....
.S.#
....

There will be infinite long perfect safe sequence, why? because we have "RRR...". That means if there is one '#' at any of the 4 direction of 'S', then the answer will be -1..

Then look at this example:

#.##
.S..
#.##
#.##

since there is only 1 cell to the left of 'S', there can be at most 1 'L' in any perfect safe sequence, otherwise if all characters other than 'L' are missing, it will lead the robot to die. So we can have a maximal bound of length of any perfect safe sequence: we have at most 1 'L', at most 2 'R', at most 1 'U' and at most 2 'D'. And we could find "LRRUDD" is perfectly safe: we have only 1 'L' so it is impossible to move outside the board from the left edge, etc.

So if the answer is not -1, then it must be n+m-2.

Div1-Medium: FoxConnection3

The key is notice that there can be few "shapes" of the result connected foxes. In fact if n = 6 there can be at most 216 of them: http://oeis.org/A001168

And then we should figure out which fox goes to which position in the final shape. There will be 6! ways.

Then we need to decide the position of our final shape.

After decide the position, we will calculate how many steps do we need to get it. It is simply the sum of length of shortest paths from s[i] to t[i] where s[i] is the start position of fox[i] and t[i] is the end position of fox[i], because we can ignore "there cannot be two foxes in the same cell at the same time." by this way:

Suppose we want to move O to x in this situation:

.O..o...o.x.

There are 2 foxes block our way, but we can do this:

.o..o...o.x. -> .o..o.....o. -> .o......o.o. -> ....o...o.o.

The if we write down the equation, it will be something like abs(offsetX — u[0]) + ... + abs(offsetX — u[n-1]) + abs(offsetY — v[0]) + ... + abs(offsetY — v[n-1]). We can find we should set offsetX = middle number of u[] and offsetY = middle number of v[].

Div1-Hard: FoxAndSouvenir

It will be quite easy to get a solution run in O(n^4) for each query, a classic DP:

dp[i] = how may ways to get exactly i dollar.

initially we have dp[i] = {1, 0, 0, ...}

For each souvenir of price p, we update new_dp[i] = dp[i] + (i-p>=0 ? dp[i-p] : 0).

So how to improve this? One observation is that this kind of dp can be write into convolutions:

for example, new_dp[i] = dp[i] x {1, 0, 0, ..., 1, 0, .., 0}.

Then one possible improvement is FFT with 2D segment tree, but it will need O(n^4 (logn)^4) which is too slow.

Another observation is that, we shouldn't do lots of FFT to merge segments again and again, for example, the answer will be {1, 0, .. , 1, 0, ..} x {1, 0, .. , 1, 0, ..} x {1, 0, .. , 1, 0, ..} ... We should first transform all of them into frequence domain, do the pointwise product of all of them. then transform back the result into time domain.

The last observation is it: we can transform {1, 0, .. , 1, 0, ..} into frequence domain in O(n) by bruteforce instead of O(n logn) by FFT, because we only have 2 non-zero values. And we just need one point value in time domain, so we can get it by brutefoce in O(n) instead of paying O(n logn) to reconver all elements in time domain.

So the solution looks like: preprocoss s[i][j][k] — the pointwise product of index k in frequence domain of the subrectangle [0, 0] — [i, j]. Then for one query we can find the frequence domain value of index k by calculate s[xMax][yMax][k] * s[xMin-1][yMax][k]^(-1) * s[xMax][yMin-1][k]^(-1) * s[xMin-1][yMin-1][k].

We should do the DFT over GF(1000000009). And we can avoid 0s in s[i][j][k] by use a length of an odd number. There are lots of divisors of 1000000008, we can choose 3507, the smallest odd divisor that is no less than 2500.

Read more »

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

By cgy4ever, 2 years ago, In English,

Update 1 : here are the reference solutions for this contest:

  1. Div2-A: http://ideone.com/JP1Ksj
  2. DIv2-B: http://ideone.com/udz3bN
  3. Div2-C / Div1-A: http://ideone.com/KVobNb
  4. Div2-D / Div1-B: http://ideone.com/7MQqOm
  5. Div2-E / Div1-C: http://ideone.com/z3FsU2
  6. Div1-D: http://ideone.com/Y7j21a
  7. Div1-E: http://ideone.com/Orbacp

Note that for Div2-E / Div1-C, it is for the harder version: we need to handle '1' in the cycle.

510A - Fox And Snake

There are 2 different ways to solve this kind of task:

First one is to simulate the movement of the snake head, and you draw '#'s on the board. The code will look like:

head = (1, 1)
repeat:
	repeat m-1 times: head move to right
	repeat 2 times: head move down
	repeat 2 times: head move down
	repeat m-1 times: head move to left
	repeat 2 times: head move down
	repeat 2 times: head move down
until head is out of the board

Another way is to do some observation about the result, you can find this pattern:

(4k+1) / (4k+3) line: "#######"
(4k+2) line: ".......#"
(4k+0) line: "#......."

510B - Fox And Two Dots

This task is essentially ask if there is a cycle in an undirected graph: treat each cell as a node, and add an edge if two cells are neighborhood and have some color.

There are lots of ways to do this, for example:

  1. Run dfs / bfs, if an edge lead you to a visited node, then there must be a cycle.

  2. For each connected component, test if |#edges| = |#nodes| - 1, if not then there must be a cycle.

510C - Fox And Names / 512A - Fox And Names

Let's first think about what S < T can tell us: suppose S = abcxyz and T = abcuv. Then we know that S < T if and only if x < u by the definition.

So we can transform the conditions name1 < name2, name2 < name3 ... into the order of letters.

Then the question become: do we have a permutation that satisfy those conditions. It is actually the classic topological order question.

One trick in this task is that, if we have something like xy < x then there is no solution. This is not covered in pretests. :)

510D - Fox And Jumping / 512B - Fox And Jumping

This task equals to: what is the minimal sum of costs that we can select k cards, so their GCD is 1.

First observation is that: GCD(x1, x2, ..., xk) = 1 means that for any prime p, there exist i such that xi is not dividable by p. So we only care about what prime factors a number contain. (So for example, 12 -> {2, 3}, 6 -> {2, 3}, 9 -> {3]})

The second observation is: If x ≤ 109 then it has at most 9 prime factors.

So after we select one number, we only care about these 9 or less primes. Then this problem equals to set covering problem (SCP), it can be done by mask DP. It can run in about O(2^9 * n^2).

510E - Fox And Dinner / 512C - Fox And Dinner

First finding is: if a + b is a prime, then one of them is an odd number, another is an even number. (that's why we set 2 ≤ xi)

Then we could find: every odd number have exactly 2 even number as neighborhood, and every even number have exactly 2 odd number as neighborhood. And that means we need |#even| = |#odd| to have a solution.

So it looks like bipartite graph matching, but every element matched 2 elements. And in fact it can be handled by maxflow: For each odd number, we add a node on the left side and link it from source with capacity equals to 2, and for each even number, we add a node on the right side and link it to sink with capacity equals to 2. And if sum of two numbers is a prime number, we link them with capacity equals to 1.

Then we solve the max flow, it have solution if and only if maxflow = 2 * |#even|.

We can construct the answer(cycles) from the matches.

Note: Actually this task is still solvable if we allow ai = 1. But you need some clever way to deal with it. We think it is too hard so we removed this case. What do you think about this decision?

512D - Fox And Travelling

We could find that some nodes cannot be visited. And more specific, if one node is in a cycle then it cannot be visited. So what about the structure of nodes that we can visit?

Let's first find a way to get all nodes that could be visited. We can deal with this by something like biconnected decomposition, but that is not easy to implement. In fact we can use this simple method: each time we pick one node that have at most 1 neighborhood and delete it. Repeat this process until we can't do it anymore.

We could find these nodes are actually belonging to these 2 kinds: 1. A tree. 2. Rooted tree. (that means, the root is attached to a cycle)

The rooted tree case is simple: we can solve it by tree DP. The state will be dp[i][j] = the way to remove j nodes in the subtree rooted at i.

Then how to solve the unrooted tree case? The way to deal with that is to transform it into rooted case. We have 2 solution:

  1. We select one unvisited node as the root by some rules: for example, we select one with minimal index. Then we just need to modify the DP a bit to adjust this additional condition.

  2. We could find if the tree has n nodes and we visit k nodes in the end, then there will be max(1, n-k) ways to choose the root. That means if we choose every node as the root and sum up them, we will count this case exactly max(1, n-k) times. So we just do the rooted DP for from node n times, and divide max(1, n-k) for ans[k].

The overall complicity is O(n4), and it can be optimize into O(n3) if you like.

512E - Fox And Polygon

Triangulation of polygon is something hard to think about. So the first key observation is that, we can transform this task into operations on rooted trees!

One Triangulation of polygon can be mapping to one rooted tree. And the flip operation can be mapping to the rotation of trees. (It is the operation we used to balance our BST) You can find the mapping from above picture. The red lines indicate the edge that will be flipped and the nodes we rotated.

Then we should find a standard shape of the tree, and solve this task: how to rotate any tree into this standard shape?

My solution is to choose the balanced tree as standard shape. The way to do that is this: find the node that the index is the middle number, rotate it to the top(that what we did for splay tree), and do the same thing for each subtree.

It is easy to see it could work in O(nlogn) steps.

Read more »

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

By cgy4ever, 2 years ago, In English,

Fox Ciel is back!

I invite you to participate in Codeforces Round #290, which will start at the standard time on next Monday:

This is my 4th round on Codeforces, my previous rounds: #190, #228, #270.

Last Div1 Round (#286) is so hard, so after notice that, we decide to reduce the difficulty of this round. (For example, current Div1-E was used as Div1-D) I hope more people can enjoy all tasks in this round: this time no task requires advanced knowledge like linear space or Fourier Transform.

The background story will be Fox Ciel's life: learning programming, play games, traveling, have dinner and so on.

Like Round #228, top-20 contestants that are currently at Petrozavodsk training camp will be rewarded with nice Codefores T-Shirts. Contestant may be a team member, jury, coach, organizer, or whoever else involved in camp, no matter of status.

As usual, thanks to Zlobober for giving great suggestions and test my round, and MikeMirzayanov for the platform (Codeforces and Polygon).

Good luck and have fun!

Update1: Score Distribution is ... Div2: Standard (500 — 1000 — 1500 — 2000 — 2500), Div1: a bit unusual ... (500 — 1000 — 1500 — 22502250)

Update2: Editorial: http://codeforces.com/blog/entry/16173

Update3: Congratulation to our winners:

Div1:

  1. Petr

  2. Endagorion

  3. mmaxio

  4. TooSimple

  5. tourist

They are all people who solved 5 tasks!

Div2:

  1. SkullSkin

  2. joshkirstein

  3. gabrielinelus

  4. Noobgam

  5. Andrey_WK

Read more »

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

By cgy4ever, 2 years ago, In English,

472A - Design Tutorial: Learn from Math

One way to solve this is by bruteforce: there are O(n) different ways to decomose n as sum of two number. If we can check if a number is a prime in O(1) then the whole algorithm can run in O(n). You can use Sieve of Eratosthenes to do the pre-calculation.

And another way is try to prove this theorem. The prove is simple: if n is odd number, then 9 and (n-9) is an answer (n-9 is an even number at least 4, so a composite number), and if n is even number, then 8 and (n-8) is an answer (n-8 is an even number at least 4, also must be a composite number).

472B - Design Tutorial: Learn from Life

This task can be solve by greedy: the k people with highest floor goes together, and next k people with highest floor goes together and so on. So the answer is 2 * ((f[n]-1) + (f[n-k]-1) + (f[n-2k]-1) + ...) .

It is a bit tricky to prove the correctness of greedy, since people can get off the elevator and take it again. We can give a lower bound of the answer by flow analysis: between floor i and floor i+1, there must be no more than (# of f[i] >= i+1) / k times the elevator goes up between these 2 floors, and then there be same number of times goes down. We can find this lower bound matches the answer by above greedy algorithm, so it means the greedy algorithm gives an optimal answer.

472C - Design Tutorial: Make It Nondeterministic

This one laso can be solved by greedy, let's think in this way: let pick one with smallest handle, then we let him/her use min(firstName, secondName) as handle. And go for the next one (2nd mallest handle), now he/she must choose a handle greater than handle of previous person, and if both meet this requirement, he/she can pick a small one.

This time the correctness of this greedy solution can be proved by exchange argument.

Note that if we change the goal of this problem: ask number of different permutations they can get, then it will be very hard. (I tried it for hours but can't solve.)

472D - Design Tutorial: Inverse the Problem

Let's think it in the following way: for the minimal length edge, it must belong the the tree, ..., for the k-th minimal length edge(a, b), if there is already an path between a-b, then it can not be an edge of tree anymore, otherwise it must be edge of tree, why? Because otherwise there must be a path from a to b in the tree, that means a and b can be connected by edges with less length, but a and b is not connected.

So this Kruskal style analysis gives us this theorem: if there is an answer, then the answer must be the MST of that graph. (You can also guess this theorem and try to prove it.)

You can solve MST in O(n^2 log n), and then there are many way to check distance between notes on tree: you can just simply do dfs or bfs from each node, it can run in O(n^2). Or if you have pre-coded LCA algorithm, it can run in O(n^2 log n).

472E - Design Tutorial: Learn from a Game

First let's solve some special cases:

If the initial board and the target board contains different orbs, then there can't be a solution.

If n = 1 (or m = 1), then we can try all O(m^2) (or O(n^2)) possible moves.

And for the other cases, there always have solution. We first hold the orb with number target[1][1] in initial board. Then we want to move other orbs to their position.

So let's come up with a process to move orb from (a, b) to (c, d): it must be some continue path from (a, b) to (c, d), so we want to build a single move: it will move an orb from (a, b) to an adjacent cell (c, d). How to do that? We can move our touching orb to (c, d) first, and then move to (a, b). But there are some concerns: in this move, the touching orb shouldn't pass any already-done cells, and it shouldn't pass (a, b) when we get to (c, d).

That means we need a good order to move orbs. We can do it in this way: first, as long as there are more than 2 rows, we move the orbs to last row (from left to right or right to left). And then it must be 2xm boards: we do it column by column from right to left. We can find that in this order, there always exist paths for our touching orb to get (c, d).

472F - Design Tutorial: Change the Goal

You need to know some knowledge about linear algebra and notice the operation of xor on 32 bit integers equals to + operation in a 32 dimension linear space. If you don't know, you should learn it from the editorial of similar tasks, for example, Topcoder SRM 557 Div1-Hard.

We need to know some basic properties of our operation:

  1. we can swap two number a and b by: a^=b, b^=a, a^=b.

  2. This operation is inversible, the inverse is itself.

By property 1 we can do the Gaussian elimination of each set of vectors.

By property 2 we can use this way to build an answer: use some operation to make A[] into a base (linear independent vectors that the span will be A[]), then transfer it into a base of B[], then use the inverse of Gaussian elimination to recover B[].

So now we have two bases: {a1, a2, ..., ax} and {b1, b2, ..., by}. If there exists some bi such that it can't be expressed as a linear combination of {a1, a2, ..., ax}, the solution can't exists.

Otherwise there always exists a solution: first we build b1 and put it in the first position. Suppose b1 = a2 ^ a3 ^ a8, then we swap any of them, say, a2 into position one, and then xor it with a3 and a8, then we get b1. Note that after this operation {a1, a2, ..., ax} will remain a base. And we need to ensure we don't erase already-done numbers in a.

472G - Design Tutorial: Increase the Constraints

Let's start with a simpler task: we have string A and B (|A|, |B| <= n), we have q queries and each query we ask the Hamming distance between A and a substring of B with length equals to |A|.

How to solve this? We need to notice compute A with different offset of B is similar to the computation of convolution, so it can be done by FFT.

We use +1 to replace '1' and we use -1 to replace '0', and then we do the convolution of A and reverse B. We can extract the answer of all possible query of "the Hamming distance between A and a substring of B with length equals to |A|."!

Then let's come back to our problem, how to use this way to make a faster solution? We can use a way like sqrt decompose: we divide A into L blocks, for each block, we compute the convolution of this part with B, it will takes O(n*L*logn). And for each query, we can use the pre-calculated results to speedup (if a whole block contains in the query, we can compute it in O(1)). So each query needs no more than O(L) operation.

If n = q then this solution can run in O((n*logn) ^ 1.5). But in practice it has some issues: for example, we can use bit operation to speedup like __builtin_popcount(). I tried to set constraints to fail solution with only bit optimization, but seems I failed: I apologies to allow this kind of solutions passed. (I used __builtin_popcount() to test such solution, but in fact cnt[x<<16] + cnt[x>>16] is much faster than the builtin fucnion)

(Also, you can use your knowledge about real world computers to solve this task: http://codeforces.com/contest/472/submission/8014415)

Read more »

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