ir5's blog

By ir5, history, 3 years ago, In English,

Hi,

I would like to invite you to Kyoto University Programming Contest (KUPC), which will be held on 2 Oct. (4:00 — 9:00 GMT). Problem writers consist of several students in Kyoto University. The contest will be held on AtCoder.

Contest Link

The contest duration is 5 hours, and there will be 11 problems. KUPC has been held every year for about 5 years in Japan, but this is the first time to provide English problem statements.

I participated in the test round of this contest. The first a few problems are easy, so I'm sure everyone can enjoy the contest. On the other hand, a few problems from the last are probably interesting and though enough for high rated coders. We hope lots of people will compete in our contest. Good luck and have fun.

Read more »

 
 
 
 
  • Vote: I like it
  • +95
  • Vote: I do not like it

By ir5, 8 years ago, In English,
Statistics
Problem#Submission#Passed Pretest#Passed FinaltestAverage Score
A858767660433.36
B749655600813.28
C4673522291093.07
D281441315.00
E2211620.00


A. Bus Game (writer: rng_58)

Brute force simulation works in this problem. In Ciel's turn, if she has at least 2 100-yen coins and at least 2 10-yen coins, pay those coins. Otherwise, if she has at least 1 100-yen coins and at least 12 10-yen coins, pay those coins. Otherwise, if she has at least 22 10-yen coins, pay those coins. Otherwise, she loses. In Hanako's turn, do similar simulation in reverse order. The complexity of this solution is O(x + y).

B. Colorful Field (writer: ir5)

A solution that uses an array of N × M will absolutely get (Time|Memory)LimitExceeded, so we cannot simulate it naively.
Both the number of queries and the number of waste cells K are not more than 1,000, so it is enough to answer each queries in O(K) runtime.
Let (a, b) be a query cell. Whether (a, b) is waste or not is determined by simple iteration.
So let's consider about the case (a, b) is not waste. Let I be the number of cells including waste ones that will be sweeped before (a, b), and J be the number of waste cells that will be sweeped before (a, b). Then, the answer is classified by the value of (I - J) mod 3 (for example, if the value = 0, the answer = "Carrots", and so on).
By simple calculation, I = (a - 1)M + (b - 1), and J is calculated by O(K) iteration.

Overall, this problem can be solved in O(KT) runtime, where T is the number of queries.

C. Beaver (writer: ir5)

We can regard a substring that is equal to one of boring strings as an interval. The number of such intervals are at most |sn, and the required time to determine whether each of them is a boring string is |bi|, so all intervals can be calculated in O(|sn· |bi|) runtime, by naive way. (Yes, no special string algorithm is required here.)
The original problem can be rewritten as follows: you are given at most 106 intervals on [0, 105], determine the longest interval that does not contain any given interval.

To solve this rewritten problem, define right[i] be the leftest position of an interval whose left-endpoint is equal to i. If there is no interval whose left-endpoint is i, define right[i] is .

Now we will calculate the optimal interval whose left-endpoint is i, in the order of i = |s|, |s| - 1, |s| - 2, ... 0When i = |s|, corresponding right-endpoint is only |s|Let's think the case when corresponding right-endpoint to i + 1 is j. If right[i] > j, then corresponding right-point to i remains j. Otherwise, that right-point is updated to right[i] - 1.
This iteration will be done in O(|s|).

Overall, O(|sn· |bi|) runtime.

D. Password (writer: rng_58)

Define an array b0, b1, ..., bn as follows: If the states of i-th panel and (i + 1)-th panel are same, bi = 0. If the states of i-th panel and (i + 1)-th panel are different, bi = 1. (The states of 0-th panel and (n + 1)-th panel are considered to be OFF.) If Ciel flips panels between x-th and (x + a - 1)-th, inclusive, the values of bx and bx + a are changed and other elements of b aren't changed. We can rewrite the problem:



<Problem D'>
You are given an 0-1 array b0, b1, ..., bn. At most 20 (=2k) of them are 1. In each move, you can change the values of bx and bx + a, where a is an element of the given array and 0 ≤ x ≤ n - a. Determine the minimal number of moves required to change all elements in b to 0.

The order of moves is not important. If there is an index x s.t. bx = 1, you must change bx at least once, so you can assume that the next move is performed on x. Assume that when you change the values of bx and bx + a, at least one of them is 1.

<Problem D''>
Let V be the graph with (n + 1) vertices. Vertices are numbered 0 to n. There is an edge between vertex v1 and vertex v2 if and only if |v1 - v2| is an element of array a. Initially at most 20 vertices contain tokens. In each move, you can move a token along an edge. When two tokens meet, they disappear. Determine the minimal number of moves required to erase all tokens.

First, calculate the distances between all pair of tokens by doing bfs 2k times. Next, do DP with bitmasks: Let dp[S] (where S is a set of tokens) be the minimal number of moves required to erase all tokens. If S is empty, dp[S] = 0. If S = {s0, s1, ..., sm - 1} is nonempty, dp[S] = min{dp[S\{s0, si}] + dist(s0, si)} where 1 ≤ i ≤ m - 1.

The complexity of this solution is O(knl + k· 22k).


E. Security System (writer: ir5)

Lemma. The sensors we should consider are only four sensors at the corner.
proof: Let's think about sensors at a fixed row v. As the definition, when Ciel entered to (x, y), a sensor at (u, v) decreases its count by |x - u| + |y - v|. Let this value be fx, y(u). If we fix Ciel's path, the total decrease of each sensor is expressed as the summation of fx, y(u), where x, y is one of the path. Because fx, y(u) is a convex function about variable u and the fact that "the summation of convex functions is also a convex function", we can ignore sensors at center points: i.e. a < u < a + c - 1.
The same thing holds true for vertical direction, so it is enough to consider only four sensors at corner: (a, b), (a + c - 1, b), (a, b + c - 1), (a + c - 1, b + c - 1). ■

Because we need the lexicographically first solution, we want to use 'R' rather than 'U' in each step. Thus, it is enough if we can determine whether a feasible path exists with constraints that Ciel is at (x, y) and the rest counts of four corners are T1, T2, T3, T4.

Lemma. Optimal step is following (except sensors region):

proof: A following figure shows that if a blue path is good a brown path is also good. (Here, the blue path means arbitrary one, and the brown path means optimal one.) ■


The problem is sensors region.  In sensors region, it is possible to assume that the optimal path always passes a right-top sensor.
While Ciel moves in sensors region to right-top sensor, the total decrease of both left-bottom and right-top sensor is constant. So we should think about only two sensors: left-top and right-bottom.
In addition, let the total decrease of left-top and right-bottom be D1 and D2. Then following holds:
D1 + D2 = const.

The smallest value for D1 is the total decrease when Ciel moves upward then moves rightward, and the smallest value for D2 is in the same way (moves rightward  →  upward).
So we can calculate the minimal value and the maximal value of D1. And actually, D1 can be an arbitrary value between them with interval of 2. A following picture shows it.


Complexity at a simulation part is O(1). Overall, the complexity is O(N).

Read more »

 
 
 
 
  • Vote: I like it
  • +33
  • Vote: I do not like it

By ir5, 8 years ago, In English,
Hello.

Today I (ir5) and rng_58 are the authors of Codeforces Beta Round #71. During the contest, you may meet some animals and be asked to solve their tasks.

We sincerely thank for RAD for solving and testing the problems, for Maria Belova for checking the English problem statements, and for MikeMirzayanov for this great system.

Good luck.

UPD:

The round is over. The result was following:

Top 10 participants in the first division:
2. Petr
4. dancho
5. wrong
6. ACRush
7. e-maxx
9. Egor

Top 3 participants in the second division:
3. Tayama

Congratulations!

Editorial (A,B,C,D,E)

Read more »

Announcement of Codeforces Beta Round #71
Announcement of Codeforces Beta Round #71
 
 
 
 
  • Vote: I like it
  • +155
  • Vote: I do not like it

By ir5, 8 years ago, In English,


#Who=*ABCDE
25ir52922--165601:01125200:33101401:57 

Rating: 2150->2205


[A] : I inserted assertion to my code in order to assure that "It is guaranteed that there is exactly one leader in the room", but unfortunately it behaved wrong.

  1. int main() {
  2.     int N;
  3.     while (cin>>N) {
  4.         int mmpts=-1<<29; string res="{";
  5.         REP(j, N) {
  6.             string name;
  7.             int p,m,a,b,c,d,e; cin>>name>>p>>m>>a>>b>>c>>d>>e;
  8.             int pts=p*100-50*m+a+b+c+d+e;
  9.             assert(mmpts != pts); // <- !!!This is wrong!!!: "3 a 0..0 b 0..0 c 999...999" can cause RE.
  10.             if (mmpts < pts) mmpts=pts, res=name;
  11.         }
  12.         cout<<res<<endl;
  13.     }
  14. }

[B] : The statement was very long, so I skipped and went to C.

[C] : The statement was short in contrast to B, so I read it.
Considering the top row of the board is OK, so the problem is just counting the number of the connected components. (Assume two cells (1, i) and (1, j) are connected if (1, i) can beat (1, j).)
...But the mathematical part was a bit hard to me, so it took a bit long time.

It is surprising that this problem can be solved by only gcd.

[B(again)] : The statement looked very long at first, but it was actually not so long.
This problem was a kind of simulation (a bit hard!), and I made 2WAs. I felt C was easier than B, but it is perhaps because of individual difference.

[D]: Inserting points to a line is done by simulation with a few data structures (I used <set> and <map>). Answering queries in online looked to me very hard, but after thinking for a while, I found that it can be done by coordinate compression + BIT.

[E]: I did not have time to read E at all during the contest, so I solved this after the contest.
In this problem, finding the way to swap two adjacent cells is enough. Really constructive problem.

Read more »

 
 
 
 
  • Vote: I like it
  • +34
  • Vote: I do not like it

By ir5, 9 years ago, In English,

General


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,'^'));
        vs1=vs2;


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.


Result

ooxxx 1332pts 97th
1885->1814

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By ir5, 9 years ago, In English,
I would like to write participation commentaries of Beta Round #33. I'm sorry my English may be poor.

A What is for dinner?

The problem is quite easy, but the problem statement is a little hard so I got as many as 2WAs. This made me upset a little.


B String Problem

This problem is also easy if we know warshll-floyd algorithm. But I confused the specification. I translated the statement "According to the game rules, with each move Valera can change one arbitrary character Ai in one of the strings into arbitrary character Bi..." as "each string can be moved at most one time" by mistake, and I spend much time in wrong and heavy coding, then I got 1WA.


C Wonderful Randomized Sum

Simple DP Problem. Let dp[n]:=(maximum sum using only "prefix multiplication" operation if an input sequence is a[1],a[2],...,a[n]). Each dp[n] can be calculated by as follow.

    dp[0]=0;
    ll mm=-1LL<<50;
    FOREQ(j,1,N) {
        mm=max(mm,-2*sum[j]);  //sum[j] is a sum of a[1],...,a[j]
        dp[j]=sum[j]+mm;
    }

And let dp2[n]:=(maximum sum using only "suffix multiplication" operation if an input is a[n],a[n+1],...,a[N]). This is also calculated as same as dp[n].
Then the final answer is max_{n} (dp[n]+dp2[n]).


D Knights

Interesting problem about geometry and graph. Query number k is large, so a program must calculate each query as fast as possible. Or, it is also good to calculate all possible M^2 queries in advance.
A way I tried was the latter tactics. First of all, I constructed a graph with M vertices. In the graph, there would exist an edge between node i and node j, if a fence i contains a fence j strictly. "a fence i contains a fence j strictly" means that there is no fence between the fence i and the fence j.
Construcing such a graph in O(M^2) is not so plain, but it can be done as follow: 1. sort all fences by their radius 2. see each fence from smaller one, then check if the fence contains the other fence strictly. Because it can be said that every fence will be contained by at most one the other fence, we need to check only fences that is not contained by any fence.
It would help implementation to add an "outer envelope" fence as a sentinel value like R=1e14, P=(0,0) , because: 1. adding it will not change any result 2. by adding it any control point will be contained in exactly one fence strictly.


After constructing the graph, we will calculate distance[i][j] for each pair (i,j). This can be done by some depth-first-search approach, starting from top node(outer envelope).


Implementation of above algorithm was laboring and I took much time. I finally got AC with 1 resubmission.


After contest I read some solution of other people, and following method looked quite good.
For each query, we can also calculate the answer by counting the number of fences that enclose only i or j. (i,j is an index of a control point)
If we use this method, the time complexity will be O(10^5*10^3)=O(10^9) and we would got TLE.
But if we calculate this not by bool[] one by one, but each bit of unsigned long long, it will be O(10^9/64) ~ O(1,562,500), then the method will be good for the time limit. I think this method is comprehensible and clever.


E Helper

I didn't read the statement yet.


Result

oooox +3442pts 62nd place

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it