|
1320 - Ural Championship 2004 Round 2 - D You’re asked to judge whether the given graph (of coz the edges in it) can be split into some chains with two connected edges. Such as the sample input: 1 2 2 3 3 1 1 10 We can split it into two chains: 1-2-3 3-1-10 My algorithm is a little tricky, just check every connected component. If the number of edges in that component is even, then this component is “splitable”, or else, it is not. How to prove that? Mathematical induction is okay.
1321 - Ural Championship 2004 Round 2 - E The lowest digits can be got 0~9 easily, so we want to check the highest digit first: if the highest digit is 1: We must check 0~1 2~3: We must check 0~2 4~9: We must check 0~4 For the last two conditions, others digits will be checked wholly from 0 to 9, so the main difficulty remains on the first condition. For it, we should check the second highest digit. (I’ll give you a hint, the two sub conditions depend on whether the second highest digit is larger than 1). Enjoy it.
1322 - Ural Championship 2004 Round 2 - F The expanding version of IOI2001 binary code (spare problem). The algorithm is exactly simple, but you'll make mistake easily. Now I’ll write the algorithm again: For the example, we know that the last column is “rdarcaaaabb”. We can simply sort them to “aaaaabbcdrr”, this is the first column. Then we got some connection between them: r->a, d->a, a->a, r->a… But how about the order? “a” denotes the first “a” or the second “a”? In fact we can write them as: a1 a2 a3 a4 a5 b1 b2 c1 d1 r1 r2 r1 d1 a1 r2 c1 a2 a3 a4 a5 b1 b2 Then we got it: a3 -> b2 -> r2 -> a4 -> c1 -> a5 -> d1 -> a2 -> b1 -> r1 -> a1. How to prove it? It cannot be said clearly, but you should know that the order of the same letter in two sequences are strictly the same. Why? You can see it from this example: abort < address < animal and we also have: borta < ddressa < nimala
1323 - Ural Championship 2004 Round 2 - G Enumerate all the possible order of N people, forming a sequence (of course the first one is monitor). Then just like Bellman-ford, for every minute, from the last person, set the one he/she calls, to be the first person after him/her in the sequence (who hasn’t received the message). Find the best one among all of the possibilities.
1324 - Ural Championship 2004 Round 2 - H If we’re asked to generate a solution for solving given L, without getting the largest K, we can simply use greedy. Each time, we process “x spaces to 1” operation. How large this x is? I make it near sqrt(L), and choose the one with smallest remaining spaces. This is NOT the answer for this problem, it just gives the correct solution for solving given L, but we can run this program many times, and got some bend point, such as: 718052410 cost us 7 operations, 718052411 cost us 8 operations. Then any one correct solution for 718052410 can be used as the answer for all of the input data, using “const” is fine! Don’t believe me? You’d better run your program to have a look :D
1325 - Ural Championship 2004 Round 2 - I An easy BFS problem, but you don’t need to use priority queue. The easiest way is, for each time, generate from “i-times-changing-boots” states to “i+1-times-changing-boots” states. Then the complexity is low enough.
1326 - Ural Championship 2004 Round 2 - J It is easy to say the algorithm must have something to do with “hash dp”, that means the status of dynamic programming should contain a 0~2N-1 state, to denote the set of bought things. At first, I didn’t find out the dynamic phase, but later I know: X or Y >= X in pascal, (X|Y) >= X in c/c++ We can use f[i](i in 0~2N-1) to denote, if we buy the things in set “i”, the lowest price we should pay. Then from f[0] to f[2N-1], expand them one by one.
1327 - USU Junior Contest October'2004 - A - Fuses (program experimentation by a275417 from Vietnam) Discuss solely for each condition…
1328 - USU Junior Contest October'2004 - B - Fireball WARNING: During the first N collisions, if the fireball has already touched point B, that touch is NOT considered as a “collision”, so the fireball just fly through the ball smoothly. I’m tested case 16 out, that’s: 10 10 6 5 5 5 5 The correct answer is 45.00. Now let’s enumerate the number of collisions in horizon and vertical. (The sum of them is N), and investigate the segment between them.
1329 - USU Junior Contest October'2004 - C - The galactic story That’s a problem of LCA (least common ancestor), you could use the easiest LCA algorithm: O(n*log(n)) in both time and space. Just maintain an array p[i][j] to denote the node i’s ancestor in level 2j. The main difficult of this problem is to avoid MLE. So you should pay attention while you’re counting array p. (use as less unwanted memory as possible) Another solution from a275417 (Vietnamese) First label all the nodes with post-order traversal. You can then give the label interval of each sub-tree. After that, giving the label of any two nodes, you can check whether one’s label is inside the other’s interval. All the algorithm is O(N) in both time and space.
1330 - USU Junior Contest October'2004 - D - Intervals (program experimentation by a275417 from Vietnam) Pre-calculate the sum of A1..Ai.
1331 - USU Junior Contest October'2004 - E - Vladislava My idea is not so good. And I could even give some data to make it TLE (but of coz I have other precaution to avoid it, but no need for URAL testdata. If you have better solution, please contact me) I search the closing launching points for each artifact one by one. But I sort all of the points by latitude first. So I could cut a large number of branches down while searching. Neal Zane’s another solution (Chinese): closest <== least angle (0 <= angle <= 180) <== max. cosine value <== max. dot product (x1*x2+y1*y2+z1*z2) so just convert all coordinates into 3-D x-y-z coordinates and for each artifact location, find the max. cosine value among the landing locations (M <= 5000). say the value is 'a', then the output should be: r * acos(a). even enumeration can do it not too slowly because sine/cosine operations are eliminated.
1332 - USU Junior Contest October'2004 - F - Genie bomber Enumerate two points on the circle, and calculate the center with the fixed radius. Check all of the circles calculated, and find the best one.
1333 - USU Junior Contest October'2004 - G - Genie bomber 2 (program experimentation by a275417 from Vietnam) It doesn’t need a high precision calculation, so we can split the plane into small “pixels”, and do it one by one :).
1334 - USU Junior Contest October'2004 - H - Checkers Be careful: the new checker might attack others and be attacked by others.
1335 - USU Junior Contest October'2004 - I - White Thesis (program experimentation by a275417 from Vietnam) n*n+n n*n+n+2 n*n+1
1336 - USU Junior Contest October'2004 - J - Problem of Ben Betsalel (program experimentation by Thanh Vy from Vietnam) (n2)2 / n3 = n, with big number.
1337 - USU Junior Contest October'2004 - K - Bureaucracy Be careful: there’s at most one bureaucrat on work each day! So simulate day by day.
|