Ripatti's blog

Solutions for Codeforces Beta Round #70 (Div. 2)
By Ripatti, 14 years ago, translation, In English

A. You should count a number of vowels for every of three phrases. Next, you should compare this numbers with numbers 5, 7 and 5. If all is matched, answer is YES, otherwise answer is NO.

Author of problem is Ripatti.


B. At first, you can [n / 7] times output string "ROYGBIV" ([] is a rounding down). After than you can output "", "G", "GB", "YGB", "YGBI", "OYGBI" or "OYGBIV" according to remainder of division n by 7. A resulting string will satisfy problem's requirements.

You can also build answer in other way.

Author of problem is Ripatti.


C. If n is even, Marsel wins - he just symmetrically repeats moves of Timur.

Now consider a case of odd n. If Timur cannot move - he is losing automatically. If he can do a move, he always can split one log into few parts that this parts cannot be splitted again. It can be done if we have find minimal t that k ≤ t < m and t|m. Next we split log into parts with length t. Thereafter Timur symmetrically repeats moves of Marsel and wins.

For checking that Timur could move or not, you can iterate over all divisors of m. If there is exists some divisor t that k ≤ t < m, Timar can do a move. Chech of all divisors can be done in time.

Author of problem is Lepetrandr.


D. It should be solved like a classical problem "count the  number of square cells 1x1 lying inside the circle". Firstly, lets find the highest hexagon that lies inside the circle. Then we move to the right and up from this hexagon, and then go down until we find hexagon lying inside the circle. Repeat this process until you reach the rightmost part of the circle.

Thus we can count number of hexagons in each column, answer is sum of this numbers. Total number of operations is O(n).

Few words about implementation. Coordinates of every considered point looks like . That's why distance between this points and (0,0) should be calculated using integers only. For example, criteria "point lies inside circle of radius R" looks like x2 + 3y2 ≤ 4R2.

Also you can solve this problem in . For every column of hexagons you can find number of hexagons inside circle by using binary search.

Author of problem is Ripatti.


E. Firstly, let's calculate the following value:
dp[t][x0][y0][x][y] == true iff scientist from block (x0,y0) can reach block (x,y) in time t, considering toxic coolant.

Secondly, let's consider a graph consisting of 4 parts:
1 - source (one vertex)
2 - first fraction (nxn vertices)
3 - second fraction (nxn vertices)
4 - sink (one vertex)
Each vertex of each fraction is for one block. Build edge from source to each vertex of the first fraction with capability as number of scientists in corresponding block. Build edge from each vertex of the second fraction to sink with capability as number of rescue capsules in corresponding block. Build edge from vertex (x0,y0) of the first fraction  to vertex (x,y) of the second fraction iff dp[T][x0][y0][x][y]==true for at least one T. Capability of this edges is infinity.

As one can see, value of maxflow in this graph is answer for the problem.

Complexity of this solution is O(tn4 + kn6), where k is maximum possible number of scientists in each block(in this problem k = 9).

Author of problem is Ripatti.

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

Comments Comments (15)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
where is the english version?
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it
For problem B it is also possible to use a randomiszed algorithm

do
{
    randomsolution=randomCalc();

}while(!isValid(randomsolution));
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Please fix typing e
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Please elaborate on problem D, i found that counting hexagons easy initially, but as N gets bigger, my answer fails. I think I misunderstood the question even after reading it several times... For example, I don't completely understand this clarification:  Then we move to the right and up from this hexagon, and then go down until we find hexagon lying inside the circle. Repeat this process until you reach the rightmost part of the circle.
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      I have TLE on Java with this solution. Does it actually fits to time?

      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it
        I think you didn't get the main idea. I've updated my picture, hope it's more clear now. We do not need to check white hexagons, only red and green ones. So, total number of hexagons we need to check is O(R). This solution easily fits to time even on Python, and on C++ it works 60ms.
        → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks for editing. But what next? We got some hexagons, but still can not say how many hexagons inside this quarter of circle. Just border hexagons. What I missunderstood?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        We  choose highest hexagon in every column.
        So, we can calculate it's count
        (all from highest downto - highest)in every column
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    try to check precision.
    You can write smthng like 
    double d1 =  Math.sqrt(x1 * x1 + y1 * y1);
    if (d1 > R &&  d1 - R > 1e-6) return false;
    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For task B

res[0] = 'R';
res[1] = 'O';
res[2] = 'Y';
res[3] = 'G';
res[4] = 'B';
res[5] = 'I';
res[6] = 'V';
int n;
cin >> n;
for (int i = 7; i < n; ++i) {
    res[i] = res[i - 4];
}

works as well.

→ Reply