I participated in the above-mentioned contest by the virtual contest system of CF.

From today, I’m going to participate in virtual contests often.

A. Triangular numbers

Given an integer n, find x such that x(x+1)/2 = n.
If there’s no solution, print “Impossible”.

Just do it.
But I used the binary search method.

B. Coins

Given the relations of weight between three coins A, B, and C, arrange these coins in ascending order.
If that relations are contradictory to each other, print “Impossible”.

Just do it.

C. Crossword

Given six strings, create a crossword puzzle made of those in the form of a rectangular “eight” or infinity sign.
If you can’t, print “Impossible”.

Crap.
Sure, I don’t like constructive algorithms.
But, besides it, this problem disgusts me because it doesn’t define “the lexicographically minimum” strictly.

D. Safe

Given an integer n(<=35) which represents the length of the password, an integer m(<=10) which represents the number of attempts of entering a password, each passwords entered and each system responses(how many positions stand the right numbers), then answer how many possible passwords that don’t contradict the m system responses are left.

Meet-in-the-middle attack!! Just do MITM.
BTW, in Japanese, MITM is called “half of all listing”.

E. Cannon

Given the n angles at which the n cannon balls will be fired, and the m positions of the walls, for every ball, answer the coordinates of its landing point.

Typical Geometry.
I didn’t have enough time to write the code of this problem, but the solution is simple.

1. For each wall, calculate the range of angle at which a ball will hit it.
2. Calculate “which angle at that a ball will hit which wall”.
3. Calculate its landing point for each ball.

CodeForces #114 Div.1 B Wizards abd Huge Prize

• Good DP Problem. It would get buggy easily. Make sure to define the recurrence equation accurately and not to misread the problem sentence.
• solution

CodeForces #121 Div.1 E Thwarting Demonstrations

• Too easy for “E” task.
• solution

POJ 1113 Wall

• Simple.
• solution

POJ 3246 Game

• This problem is bad. It has too weak testcases since my solution should not be passed(O(n^(5/3)logn)). The essence is how to calculate differences smartly.
• solution

CodeForces #109 Div.1 C Double Profiles

• Shit.
• solution

POJ 1759 Garland

• Straightforward. But floating-point is fearful.
• solution

POJ 2100 Graveyard Design

• Just Do It. But since on POJ, you can’t use O(NlogN) methods like binary search. Use Inchworm Method(I don’t how to say in English. Is this correct?).
• solution

CodeForces #119 Div.1 C Weak Memory and Aizu Online Judge 1150 Cliff Climbing

• Easy. Remember Single-Source Shortest Path problem on unweighted graph can be solved by Breadth First Search. In some cases, it could be faster than dijkstra.
• solution
• solution

POJ 3180 The Cow Prom

• READING HARD. Why don’t you describe in simple words, simple sentences?? Just Strongly Connected Component algorithm.
• solution

POJ 1180 Batch Scheduling

• A bit easy. But this is a good example of convex hull tric on DP.
• solution