Blog of Xay

Hefei_Site_09总结

Wed, 14 Oct 2009 08:51:44 +0000

今年第一战总算比完了，其实压力蛮大了，不过比赛那几天就不去想了，当时心里面啥都没想了，可以说是轻装上阵吧，心里面很空。
    说说比赛吧，刚开始我把E读了，发现是一道裸体的AC自动机。但是我先放下，看其他题，不一会有队伍过了D题，我一看，应该是数学公式题，于是抛给天王了。天王抛了A题给我。不一会天王推出一个公式，我把它敲上去，AC。我继续看A题，看完过后，天王把B题抛过来，素数测试。我一看范围很大，以为有特殊方法，于是冥思苦想。期间有很多队伍过了此题，又有裁判发clarification，说java加package会RE，于是我想到了java的大整数有一个判素数的函数可以直接用。跟金毅说了说，然后把B秒了。这是大概有A和E可做，但是金毅和天王开出了G题，于是天王去思考G题，A和E都留给我，我先写E。当时还不太在状态，写得慢了点，不过1Y了。接下来天王上去写G，我思考A。G题TLE一次之后在金毅同学的配合下AC了。这是我们4题，排名不是很好看，罚时较多，主要因为B题出的挺慢。然后我上A，思考得比较清楚了，代码不太短，写完直接过样例，稍微看了看提交，WA。打印代码和金毅讨论，天王一直在开新题。金毅看完代码后提出了速度为0的情况，我果然没有考虑啊。于是改代码，小改了一下，过了自己出的样例，提交，WA。和金毅再看代码，果然还有bug，改，提交，WA。其实心里不太急，再看。这回天王来跟我一起看，金毅去机器上出样例。果然，金毅找出了关键的样例！果断改代码过了此样例，提交，AC! rank4.其实我心里还不是很放心，认为还要出一题。然后拿出队伍对照表，发现我位于非旅游队的rank1，于是心里有底了。说实话，瞬间松了一口气，当然也有点泄气了，带着这个rank1进入了封榜最后一小时，果然最后都木有出题。当时我去上厕所的时候就在想，这个比赛是自己在和自己比，自己掌握着自己的成绩，但是最后一小时没题可开的时候，才知道那种由别人来决定自己成绩的感受...
    总得来说，结果还能接受，我校终于实现了连续三年进final的愿望。不过，差距也很明显的，清华大学旅游队7题，再看我们队最后一小时的无能为力，其实我当时心情挺复杂的。总觉得这个final有些运气成分。拿到自己第一个金牌的同时也有些许小小的感触。
    1.我们还不是什么七大强校，差距还很明显
    2.我们的训练效率还不够，有一些经典的东西都还不会
    3.我们队还是比较稳的，在这一点上我很相信队友
    4.我们切题量太少，我觉得这是一个硬伤
    5.对于在训练赛中没有AC的题目，处理得还是不够好，有很多很好的题目被无视掉了

离Shanghai_Site还有不到两周，再接再厉吧

中南赛总结

Mon, 01 Jun 2009 09:19:56 +0000

虽说每次出去比赛总有大量rp事件发生，rp流动异常频繁，就连比赛前也不忘攒一把rp，还是直接说比赛吧

题目供应很不赞...3个人一份题目...而且...而且...而且...还是两面打印....B题的背面是A题的样例...C题的背面是B题的样例...连把题目拆开都制造障碍...
比赛过程：不管怎样，还是先拆题。AC题很短，我一下看完了，A题意思很简单，我想了个做法，跟金毅讲讲，我错了...然后想C题，确定是个polya定理。但是刚开场，比较紧张，所以想得不太清楚，于是继续想。我想啊想，期间韩帅过了G题。然后我想出了公式，上去写，写着写着，发现题目中n<=10^9，我的算法还是O(n)的...于是狂汗，然后韩帅和金毅讨论着A题，上机写了个暴力，输出一些结果，发现答案是输入的欧拉函数，于是我上去将其秒了...这时场上有人过了H和I，韩帅把I题交给我，计算几何题。本来这题我不太有信心，害怕被卡精度，不过场上已经有人过了，我就上去写了，1Y秒掉...然后这样就3题了...我写I期间，韩帅和金毅讨论出了H题，我秒掉之后，金毅就来了，我下去想C题办法。我跟韩帅交流了一下做法，以及遇到的问题，然后提供了一些解法方向，在两个人的共同思考中，找到了解决办法，又是欧拉函数，好神奇啊好神奇。金毅不一会就1Y了...换我了，上去将A题代码copy过来，再敲入快速幂以及polya公式计算and dfs枚举约数，样例通过，上交，WA...好吧，我打代码...韩帅就上去敲无敌BFS，我和金毅查查代码，没有数据范围问题，没有int->long long问题...突然被我发现了xx错误，小改一把...AC...我很奇怪这道题过了样例也能WA。。。
3小时30分钟，韩帅继续敲代码BFS，我和金毅观看场上情况，我们队5题，领先第二名，罚时占优7min。然后看一下剩下的题，一道不可做题D，一道B题需要一点技巧...一道E题模拟，一道F题天王正在奋战，一道J题题意不清。然后我们想出了B题的做法，感觉E题比较简单，暂时不太确定F题能不能过，于是犹豫不决开哪题。不过3小时47分钟，天王把F题1Y了！！！于是我们最后同时开了两题。封榜前，我们队6题领先第二名1题，且罚时占优。我先上去敲E题了。怨念一下最后我提交的两个clarification，整整一个小时都没人回答，于是我只好枚举题意流...代码比较好写，上交后WA。。打代码，然后韩帅来敲B，大概20分钟之后交，WA...我们窘迫了...我枚举了一下题意都是WA...B题代码也没看出啥错...最后倒数10秒的时候，我交了一把E...WA了...E总计WA了5次.

总结：
出题6道，其中5道是1Y，另一道2Y，罚时还是比较重要的，虽然不知道最后有几个队过了6题
前期我sb了...抱着C题傻想...还好有韩天王调配，把A题和I题及时给了我
中期我们很猛...切题很迅速，感觉很顺...
后期我们萎了，抱着不超神就超鬼的心态搞了两题，最后超鬼了...
很明显，我们与一流强队还有一定距离，不论是知识点，知识结构，代码能力和现场的心态，我们要有一段长路要走.

[zz from petr]analysis about the world final

Sat, 09 May 2009 13:48:10 +0000

Problem A.
First, we loop over 8! possible orderings for the landing of the planes. Then, we do binary search on the answer. Having fixed the answer, we simply land each plane in the chosen order at the earliest possible time.

Problem B.
This problem requires careful checking of all boundary cases, and doesn't seem to require any particular insight. One just verifies the output of the original scheme on all given inputs, as well as the output of all "wrong" schemes that can be obtained from the given one by introducing one mistake (since there's not more than 19 gates, there's not more than 57 such schemes), and then checks if the output can be uniquely determined. But there surely is some trickiness to implementing that.

Problem C.
This is a very well-known problem if the ant moves along the surface of the cube; the octahedron doesn't change much. We try all possible ways to lay out the octahedron's sides on the plane (first place the first side, then place any of its neighbors next to it, and so on). The number of possible layouts should be on the order of hundreds or thousands. And in at least one layout, the shortest path will be just a straight segment - so we need to check those segments in all layouts, throw away those that go outside the layout, and then find the shortest one of the remaining. This solution should work as long as no shortest path passes through the same side twice; I don't have a proof for that, but intuitively it seems true. The implementation will require a LOT of accuracy, though.

Problem D.
One thing that comes to mind is to draw all possible layouts on paper, and figure out the formulas for the answer in each of them. But that's very error-prone, so I hope there's a more concise solution.

Problem E.
Take any vertex in the graph. Let's say it has a "nice left" if any path from the start to that vertex has the same cost. Let's say is has a "nice right" if any path from the end to that vertex has the same cost.
This can be determined by DFSen.
If there's a vertex without both nice left and nice right, then there's no solution: at least one of the roads to the right of it will have to be modified, and at least one of the roads to the left of it will have to be modified - so there will be a path with two modified roads.
Otherwise, the vertices split into 3 sets: A - vertices with nice left but no nice right, B - vertices with nice left and nice right, and C - vertices with nice right but no nice left. If both A and C are empty, the constraints are already satisfied and there's no need to change anything. Othewise, A will always have the start vertex, C will always have the end vertex.
Let's assume for now that B is empty. The above argument about no path with two modified roads tells us that the only way to achieve what's required is to modify the roads that lead from A to C. More specifically: take all pairs of vertices a from A and c from C, where there exists and edge from a to c. The cost of that edge plus the cost of the path from start to a and from c to end is a lower bound for the answer. Take the highest of those lower bounds, say H, and change the cost of each edge between a from A and c from C to H-cost(start,a)-cost(c,end). This will quite obviously be the minimal possible answer, and every path will have the same cost of H since it will pass along exactly one edge from A to C.
Now, how to deal with B? It turns out that we can simply put all vertices from B to C, and the above solution will still work - since it always leaves at least one route from start to end unchanged, it can't make a non-optimal answer; and it will always produce a correct answer since the only thing it requires is for all vertices from A have a "nice left" and all vertices from C have a "nice right".
Does that make sense? :)

Problem F.
First, let's learn how to calculate the length of one fence required to enclose the given set of points. To find that fence, we find the convex hull of that set of points, and then "extend" it to the outside by the given margin. The result may have a complex structure of straight and circular segments, but its total length is easily computed: the total length of straight segments is equal to the perimeter of the convex hull, and the total length of circular segments is equal to one circle, 2*pi*margin (because you have to "rotate" by 2*pi to complete the cycle - when you're moving in straight line, your direction doesn't change).
The rest of the problem is standard: we do a DP that calculates the minimum possible cost for each subset of points, by choosing a subset of that subset to be contained by one fence, and taking the previously-computed DP value for the rest of the points.

Problem G.
I think this problem requires one just to implement the game's rules carefully. The number of possible states in the game is reasonably small: the position is characterized by the number of cards still lying in the row, the cards held by both players, if any, and the layout of the "top line" of the house of cards - which will always include not more than 8 cards. This gives us a rough estimate of C(26,10)*26 states, which is roughly 100 million - but in reality much less of the states will be reachable, since the top line only contains 8 cards in one case, and so on.

Problem H.
If we introduce variables x1,x2,... for the decisions on the bills, then satisfying all ministers can be formulated via statements of form "if x5 is false, then x7 is true" (since if at least one decision contradicts minister's choices, then all his other choices must be respected). That gives us an instance of 2-CNF satisfiability problem, and its solution is well-known. Checking which variables have the same value in any solution is also quite routinely added to that well-known solution (for example, we fix that variable and run the satisfiability checking again).

Problem I.
Another implementation problem here. One should understand the problem statement, and then simulate all resizes going from the outermost window inside.

Problem J.
We can try solving this with a binary search + DP. We binary search over the answer, then do a DP on subtrees. For each subtree, consider all possible roundings that don't contradict the chosen answer (that is, the paths completely inside the subtree don't change by more than that answer), and from each of those roundings, we're interested in the lowest and highest differences for paths from the root of that subtree to its vertices (these two values are the only ones that affect paths that pass through the root of that subtree). So the DP can be: for a subtree T and a lower bound L on the difference on the paths from its root, what is the lowest possible upper bound U on that difference? This should give us only at most of 100*30*100 states, and I think the processing of all states can be done in at most 100*30*100 time (since there're only 100 edges, and "updating" along each edge will take one scan along a 30*100 array that has the U's for each L), thus even a binary search outside still leaves the running time reasonable.
I know this is very unclear, but I think the only way to figure out the details is to actually start coding the solution, and I'm too lazy for that :)
A shot at clarifying: for a subtree, there're 3 parameters:
1) the maixmum modulus of delta for paths inside that subtree
2) the maximum delta for paths from the root of that subtree into the subtree
3) the minimum delta for paths from the root of that subtree into the subtree
Without the binary search, we'd be forced to add the 1st parameter to the DP, and that would make it too slow. That's why we use binary search outside.

Problem K.
Consider the chain of transformation in the optimal answer. Consider the change(s) that affect the leftmost character of the string. Between those changes, the transformation is split into independent parts. That gives us the possibility of the following DP: consider the set of all suffixes of length L of all given strings (S,T, and all transformation strings). There're at most 202 of those for each L. Now, let's calculate the best way to transform each of those strings to each other, given that we know such answers for smaller values of L. First, we account for the transformations that don't involve the whole L characters - we can just take the value from the L-1 step. And then, there are transformations with the whole L characters - they are given by rules of length exactly L. And then, we need to combine those two kinds with a shortest-paths algorithm, like the Floyd-Warshall. That gives us 202^3 running time for each L, so about 160 million very simple operation for each testcase - that should be enough.

终于解决了关于a／b％m的问题

Thu, 30 Apr 2009 04:31:16 +0000

central europe 08 I题的一点经验...
背景：a是b的倍数
1.如果m是质数，很简单，直接用扩展的欧几里德求b关于m的逆元

2.如果m不是质数，把m质数分解成质数p1,p2,……,pk的积
  然后把a分解成a1*a2，其中a1的质因数只能在p[]中，a2与p[]中的所有质数都互质，即a2与m互质
  同理把b分解成b1*b2，其中b1的质因数只能在p[]中，b2与p[]中的所有质数都互质，即b2与m互质

3.现在问题变成了(a1*a2)/(b1*b2)%m，即(a1/b1)%m*(a2/b2)%m。
  问题分解成了两个问题:
   对于a1/b1%m，可以化为(p1^m1*p2^m2*……*pk^mk)/(p1^n1*p2^n2*……*pk^nk)%m，即p1^(m1-n1)*p2^(m2-n2)*……*pk^(mk-nk)%m
   对于a2/b2%m，b2与m互质，则可以直接求出b2关于m的逆元化为a2*b2^(-1)%m.

4.于是，问题解决，时间复杂度约为O(sqrt(m) + log(m))

宁波邀请赛总结

Tue, 28 Apr 2009 14:29:21 +0000

话说YY刚才stockholm回来就直奔宁波，还是传说中的硬座流...很坚持，不过他的身体还不够坚持.比赛前一天病号了...亏得有人照顾啊～MS很幸福的样子...
第二天的比赛，应该是我们组队的第一场正式比赛吧.开场FJ发现了C题简单题，YY就让她上去敲了，期间我发现了I题简单题，比C更容易敲，于是我上去把I秒了，FJ继续上来敲C。A题很熟的样子，但是又想不出来，于是我就看题，看了很多题。这期间YY发现E题可做，我发现J题可能可做，但是FJ在写C题的时候还是出了点小问题，主要还是经验不足，所以我们C题出得稍慢。然后YY上去敲E题，FJ下来了解了J题题意，不一会我和她讨论出了J题的做法，我上去敲了一会，WA一次之后过了。期间，YY发现E题看错题意，原来的题意更简单，导致他很郁闷，不一会他干掉了E。后来的题，我们开了B和H，我敲B，YY搞H。不一会封榜了。
我用暴搜+O(15)的判断，TLE了，然后改成O（1）的判断，WA了，知道比赛结束。
YY用自动机YY了H题，TLE了，RE了，又TLE了，比赛结束了。

总结：1.我们状态不好，有个病号，加上一晚上硬座，比较需要睡眠
      2.我们控场还有问题
      3.我们还需要磨合
      4.我居然没想到卡特兰数...

校赛总结

Sun, 29 Mar 2009 08:44:08 +0000

校赛终于结束了~

1.预赛
   预赛10个题目，我们队做了6个，也就是6个简单题被我们切了。不强调了，也就是6个简单题。
   ps.有一队全切
2.练习赛
   练习赛2个题目：1.a+b 2.一道np问题。第一题用来练习和测试，第二题挺好玩的，很有竞技性，很有rp性~最后我们队没用rp，贪心了一个解...虽然很挫
3.现场赛
   重点。
   失误。拿到第一题，有其他队很快就出了，看题之后也发现很水的样子，结果trick一大堆。所有的trick全被我忽略了一遍...怨念，于是第一个小时没出题 -_____- AC了A题之前，fj过了E题；AC了A题之后，J题被shz秒了...zan！这样我们三题了。
   这时，场上有B，I题出得比较多，于是乎我去瞅瞅瞅I题，瞬间想出算法了！！！O（n^2），被shz泼了冷水...于是乎，再接再厉，我想啊想，好像半平面交...我绞尽脑汁-----------栈！神一样的数据结构，我使用它，干掉了I题，嗯。正在这时，神一样的shz过来了，他上去了，他去敲C题了，传说中的集合DP……Orz，1A。。。
   于是，我们5题了...于是...我们mega kill了...于是有人holyshit了...于是board被封了...
   好，继续~D题最小堆，我看一看题，嗯？做过...嗯？好像是DP...嗯？很简单的样子...嗯？我秒了它~
   与此同时，fj小盆友的B题敲啊敲~~WA啊WA，这时！！！！！！！！就在那一刹那~~~~神一样的shz又出现了！
   Orz...他发现了问题~oh，wicked sick。。
   还有20分钟...FGH，我后悔啊后悔，俺应该去搞搞H的，最后20分钟浪费掉了...

   最后，狂赞一把神一样的shz~
以下……

Hefei B题解题报告

Mon, 02 Mar 2009 05:27:45 +0000

r^2 mod n = x (0<=r给定x和n(2<=n<10^9),求所有r
其中r的一个解r0已经给出

由题意知：r^2 = x + n*k (1)
又可得 r0^2=x + n*k0 (2)
(1)(2)式相减得(r+r0)*(r-r0) = n * (k - k0)，即(r+r0)*(r-r0) = n * p (p != 0)

现在将n分解为两个数x1*x2的积
(x1，x2由O(n^(1/2))的枚举得到)
则可得到方程组 r + r0 = x1 * s1
r - r0 = x2 * s2
将两式相减得：x1 * s1 - x2 * s2 = 2 * r0
其中r0, x1, x2已知，于是问题转化为一元二次不定方程
用扩展的欧几里德解出该方程，将s1,s2带回方程组中求得r，再用r^2 mod n = x检验正误
最后有序输出结果即可

zoj月赛

Sun, 15 Feb 2009 10:12:08 +0000

刚一开始我看了几道题，发现I题比较水，于是直接敲I题。期间有人过了A和C题，25分钟，我全场第一个过了I。紧接着我去做A题，也是简单题，枚举就ok，理解错误，WA了2次之后AC。然后我跟风做C题，很经典的DP，我把它想简单了，于是用了个n^2(n<300)的办法，果然WA了，不过后来我找到了错误数据，改成n^3的dp就过了。接着就是本场最让我纠结的一题，使用了错误的解法，使用了枚举法，使用了打表法，大概用了2个半小时，最后用组合法才算勉强过了这题。然后F题是找到结果就行了。

总得来说，题目难度不大。我的水平还有待提高，难题不会做，简单题又做得慢，很囧很无奈。

于是我去吃饭了。

sgu128

Tue, 10 Feb 2009 16:18:29 +0000

根据题目意思，如果多边形存在，那么只有唯一解。

首先把点连起来，按照y主x次排序，第2k-1个点一定与第2k个点相连；同理，按照x主y次排序，第2k-1个点一定与第2k个点相连。这样就把所有的点连起来了，至于这个连接方法是否合法，需要确定两点：1.所有的点是否连通，2.线段之间是否有交叉。

1.很简单，用并查集。

2.用线段树解决。先以y轴建树，每个节点记录该线段上的水平线段的条数。把所有线段的端点按照x主y次排序，相同的点按照水平线段的右端点<竖直线段的端点<水平线段的左端点的顺序。排好序后，逐个扫描，遇到水平线段的右端点把该线段插入线段树，遇到水平线段的右端点就把该线段从线段树中删除，遇到竖直线段就判断当前该线段所在区域是否有水平线段，如果有就有交叉。

Tags - sgu , 128 , acm