ir5's blog

By ir5, 13 years ago, In English


It was normal codeforces contest except the IO: input.txt/output.txt. I didn't know the IO change before contest began and I got upset. I used an unaccustomed fstream library in the contest, but I should use freopen as below code. (if C++)

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

A Extra-terrestrial Intelligence

Simple problem, calculate the interval length between first two '1's, then check if all interval lenghs are equal.
I failed to read the statement "It’s guaranteed that the given record sequence contains at least three 1s" at the beginning, then I stopped for a little.

B Fractal

This is also a simple problem, simple iteration is good because the input size is very small.
But I stuck at compilation error of vector<string> substitution, then I lost about 10 mins. This upset me. My C++ compiler MinGW outputs compilation error at below code. I don't know what is wrong yet..

        vector<string> vs1(N,string(N,'^'));
        vector<string> vs2(2*N,string(2*N,'^'));

C Bowls

Difficult geometry. Many branching are required and my submission failed in the contest.
When a bowl A is put on a bowl B, the contact point with A,B will be one of below situations.

So when we simulate putting a bowl A, calculate the height of putting on bowl B foreach 0<=B<=A-1, then take maximum height as a bowl A position.
To find the contact point, I first wrote binary search method instead because branching was laborious. But it was hacked quickly. (perhaps TLE or WA.)

Be aware that input size N is a bit large to run O(N^2) in 2000 msec limit, heavy calculation must be reduced.
Line struct class as below was bad thing because method push_back will consume much time.

    struct Line : public vector<P> {
        Line(const P &a, const P &b) { push_back(a); push_back(b); }

(I think the input size 3000 was a bad thing because the code which is only a little heavy may got TLE.
In Codeforces, TLE may not detect at pretest that contains only easy tests, and we cannot test the worst case in judge server environment, so we can't check if the code will get TLE or not.
If O(N^2) algorithm is simply required, N<=1000 would be good.. wouldn't it?)

D New Game with a Chess Piece

I didn't read in the contest.
This problem looks like Nim, though the rule removing stones is different from Nim. Actually, this problem is not so hard if we experiment with small input size like 1<=N,M<=50.
The answer has a relatively comprehensible rule with N,M,K, so we can construct O(1) algorithm. The solution will be simply an enumeration of mathematical expression.
I thought D is easier than C, though two problems are in different category.

E Two paths

I don't read yet.


ooxxx 1332pts 97th

Bad result. I'm shocked at C because I solved many geometry problems before and had a little self-confidence with geometry.
If a geometry problem is given next time again, I need to solve it.
  • Vote: I like it
  • +5
  • Vote: I do not like it

7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain problem B ?