Hello!

Topcoder SRM 728 will be held tomorrow (January 25, 2018).

See what time it starts in your area.

I'm the writer. Everyone is welcome to participate!

# | User | Rating |
---|---|---|

1 | Petr | 3353 |

2 | fateice | 3306 |

3 | Syloviaely | 3274 |

4 | tourist | 3235 |

5 | OO0OOO00O0OOO0O0…O | 3181 |

6 | Um_nik | 3158 |

7 | V--o_o--V | 3148 |

8 | dotorya | 3145 |

9 | LHiC | 3115 |

10 | mnbvmar | 3096 |

# | User | Contrib. |
---|---|---|

1 | tourist | 178 |

2 | rng_58 | 168 |

3 | Petr | 158 |

3 | csacademy | 158 |

5 | lewin | 151 |

6 | Swistakk | 149 |

7 | Errichto | 141 |

8 | matthew99 | 139 |

9 | BledDest | 138 |

9 | adamant | 138 |

9 | ko_osaga | 138 |

Hello!

Topcoder SRM 728 will be held tomorrow (January 25, 2018).

See what time it starts in your area.

I'm the writer. Everyone is welcome to participate!

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/21/2018 21:29:42 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|

Tourist these days be likeReminder: The contest starts in less than 4 hours. Registeration has started.If you are first to compete and don't know how to use applet, I suggest downloading applet from https://www.topcoder.com/community/competitive-programming/ and see https://www.youtube.com/watch?v=A5vnkkFGOo0 (of about first 20 minutes).

Use IcedTea in Linux for running applet.

How to run under proxy server?

arena is not working properly:

screenshot

I didn't experienced. Did you try once more?

yeah, it works fine now

Arena not working for me. The same with web arena

Is it possible to solve d1-500 with factorial polynomials?

????? Am I missing something????

http://apio-olympiad.org/2016/tasks/boat/descriptions/en.pdf

I think you are not missing anything, and this problem is indeed very similar to today's Div1 Medium. Unfortunately, I haven't been checking APIO problems since I graduated from high school :(

Sorry about that.

Well, individuals can make mistakes, but I don't understand that you didn't had any testers pointing out that.

But whatever, it seems nobody remembered that APIO problem (and I'm really surprised about this. Why guys?????) I'm pretty sad to miss a trivial 497 points.

How to solve Hard? I've seen that the twirl operation actually just allows you to consider basically isomorphism only for even permutations. And it's obvious how to count the number of isomorphism classes if it weren't for this parity stuff. But it just seems impossible to tackle...I'm really curious to see the solution

The usual way to find the number of equivalence classes under a group of actions — Burnside's lemma.

Shit...I need to learn that. I've kept procrastinating it. Do you have any good tutorial?

Here is a short summary of solutions. Have fun!

Halving (div1 250)Generate all stick lengths obtainable from every

a_{i}, along with the number of steps required to obtain it. From all lengths obtainable fromalla_{i}, pick the one obtainable in the smallest total number of steps.The main question is: how many distinct stick lengths are obtainable from a stick of length

L?In fact, this number is . It can be seen as follows. While

Lis even, divide it by 2 until it's odd. When it's odd, we'll have two possible stick lengths on the next step, let's denote them byXandX+ 1.What stick lengths are obtainable on the next step? They are

X/ 2, (X+ 1) / 2 and (X+ 2) / 2 (integer division). Clearly,X/ 2 and (X+ 2) / 2 differ by exactly one, and (X+ 1) / 2 is equal to one of them. Thus, on the next step, we'll still have only two possible stick lengths. Since the number of steps is , the number of obtainable stick lengths is at most .IncreasingSequences (div1 500)This is a DP problem. The only trouble is that

A_{i}can be up to 10^{9}.Divide all integers from

L_{1}toR_{n}into segments such that all integers in this segment belong to the same set of ranges [L_{i};R_{i}]. For example, if the ranges are [1;10], [3;10] and [8;15], then we'll form segments [1;2], [3;7], [8;10] and [11;15]. Clearly, we'll form at most 2nsuch segments.Now, for every

i, instead of deciding the value ofA_{i}, let's only decide which segment it belongs to. SinceA_{i}must be an increasing sequence, corresponding segment IDs must be non-decreasing.For a fixed assignment of

A_{i}to segments, how many ways are there to actually choose allA_{i}so that the conditions are satisfied? Well, it's the product of , wherelen_{j}is the length of thej-th segment, andcnt_{j}is the number ofA_{i}belonging to thej-th segment.This leads to a DP solution. Let

f_{i, k}be the number of ways to assign the firstinumbers to the firstksegments. Transitions are done by looping over how many numbers are assigned to the next segment. The complexity isO(n^{3}) (if you precalculate in advance or quickly calculate them during the process).Trisomorphism (div1 1000)The solution is a somewhat straightforward application of Burnside's lemma.

For every even permutation

p, we count the number of graphs left invariant byp. Then we know the answer.Let's count such graphs for a given

p. Suppose we have edges for alliin our directed graph. Fix somei. We have an edge . Since the graph is left invariant byp, we must have an edge in our graph. Similarly, we must have an edge too, and so on. Suppose thatibelongs to a cycle of lengthk_{i}in p. Then, we must have an edge . Sincep^{ki}_{i}=i, and we only have one edge outgoing from each vertex, we must havep^{ki}_{ai}=a_{i}. Thus,a_{i}must belong to a cycle inpof lengthk_{ai}which is a divisor ofk_{i}.This is a necessary condition. But if on every cycle in

pwe pick oneiand choosea_{i}so that this condition is satisfied, then we can deduce the outgoing edges from all vertices on this cycle, and the condition will be satisfied for these vertices, too. It can be seen that this is also sufficient -- with the condition satisfied, there is a bijection between the original and the permuted vertices and edges, so that's an automorphism.Hence, once we know the lengths of cycles in

p, we can easily count graphs left invariant bypin polynomial time. Every distribution of cycle lengths is a partition ofn, and there are not too many partitions forn≤ 50, so we can try them all.HalvingEasy (div2 250)For every element of

S, apply halving to it while it's larger thanT. If it turns out to be equal toTafter that, add 1 to the answer.IncreasingSequencesEasy (div2 500)This is a DP problem.

Let

f_{i, j}be the number of increasing sequencesA_{1},A_{2}, ...,A_{i}such thatA_{i}=j. Clearly, ifj<L_{i}orj>R_{i}, thenf_{i, j}= 0. Otherwise, .The problem is that this solution is too slow -- it works in

O(n·max(R_{i})^{2}).To fix that, note that . Thus, if both

jandj- 1 belong to [L_{i};R_{i}], thenf_{i, j}=f_{i, j - 1}+f_{i - 1, j - 1}. We can calculatef_{i, Li}first inO(L_{i}) time, and then calculatef_{i, j}forjfromL_{i}+ 1 toR_{i}inO(1) time each.This way, the solution works in

O(n·max(R_{i})), which is just enough to get accepted.TrisomorphismEasy (div2 1000)The key insight is: by applying twirls, we can permute the labels of the graph

almostarbitrarily. In fact, we can apply anyevenpermutation to the labels, since every twirl is equivalent to performing two transpositions.The solution is: loop over all even permutations of length

nand permute vertices of the graph according to them. Count the number of distinct graphs obtained using any equivalent of hashset. The complexity of this solution is aboutO(n!·n).It's also possible to do the Div1 1K in polynomial time (code in the practice room):

SpoilerThat tells you the number of equivalence classes under isomorphisms, but not trisomorphisms (even permutations). Those equivalence classes for which there is an auto-trisomorphism should be counted once, those without an auto-trisomorphism should be counted twice. To count the latter, run through the same DP again, but this time exclude any rooted tree/graph that has an auto-trisomorphism e.g. for a tree, reject it if it has two isomorphic subtrees of odd size.

My implementation is

O(N^{3}), but I wouldn't be surprised if it can be reduced.Sadly this was far to complicated to get right during the contest.

It's also possible to the div1 med by reducing it to this problem: http://codeforces.com/problemset/problem/559/C.

For instance, replace L[i],R[i] with L[i]-i, R[i]-i, respectively so we are looking for non-decreasing sequences. For each interval L[i], R[i], we can add the points (i, R[i]+1) and (i+1, L[i]-1). Then, we just need to find the number of paths from (0,0) to (n, R[n-1]) that go only go down/right and don't touch any of the given points. This is a bijection, since we can take the column where we go from row i -> row i+1 to be the i-th number in our sequence. This can be done in O(n^3) if you don't preprocess factorials, but I'm not sure if you can get to O(n^2) with some smarter pre-processing.

If I understood you correctly, I think there is a bijection iff after doing your changes for L and R arrays, we need to make L non-decreaasing (each L[i] is the maximum of all L[j] for j<=i) and R non-decreasing (each R[i] is the minimum of all i such that j>=i) to make the bijection true, and also making those changes in that way won't change the answer.

Imagine the case where all L[i] are very large except for the last one is very small, there will be a path that go down early at first row (after a few steps), and keep going down, and at row n turn right, and you will avoid all L points since all of them is large except the last one (will be also avoided as L[n-1]-1 is smaller than index current column) , you can also find similar case for R.

But I believe if you made L non-decreaasing and R non-decreasing in the correct way the bijection will hold.

Anyway, I really like your solution a lot ^_^

Thank you :)

This question is not about SRM 728. In topcoder is it possible to see SRM announcement at least 1/2 day(s) before? I used to see about SRM in arena in the day of contest. Due to this I miss SRM frequently.

Pro Tips:

Now you have a schedule on SRM 729 and SRM 730:

SRM 729: February 10th, 12:00-13:35 (UTC -5), writer is Errichto

SRM 730: February 20th, 07:00-08:35 (UTC -5)

I'm grateful to you. I found your tips very useful specially public calendar. Thanks.