accidentallygivenfuck's blog

Turkmen National OI
By accidentallygivenfuck, 11 years ago, In English

Day1 Tasks

A. Bet you can't solve it

You need to build a stairway, which has 1.5 unit height and 4.5 unit width. Each step has to have 0.3 unit height and multiple of 0.5 unit width. How many different ways are there to build such a stairway?

Строится лестница из точки А в точку В. Растояние АС = 4.5м; ВС = 1.5м. Высота ступеньки 0.3м, ширина 0.5м или кратное 0.5м. Сколькими способами можно построить лестницу?

Sample stairway. Original images for description.

B. Piece of cake

Given matrix A[1...n][1...m], each element of which is 0, 1, 2 or 3. Find number of 4-ples A[i][j], A[i][j + 1], A[i + 1][j], A[i + 1][j + 1] where these numbers differ from each other.

Данна целочисленная матрица А[1...n][1...m],каждый элемент которой равен 0, 1, 2 или 3.Определить количество четвёрок A[i][j], A[i][j + 1], A[i + 1][j], A[i + 1][j + 1] в котором все элементы различны.

C. Strange Problem

Continue the sequence of 3-digit numbers: 215, 717, 316, 512 ...

Продолжить последовательность трёхзначных чисел: 215, 717, 316, 512 ...

D. Knights' Invasion

Find a way to place 12 knights so that every cell is either attacked or is owned by a knight.

Найти такую расстановку двенадцати коней на шахматной доске, при котором каждое поле будет находиться под ударом одного из них.

Day2 tasks are available here.

Constraints

Participant: What is the limit for N?
Jury Member: N can be anything... The limit for it is infinity...
Participant: But no computer can handle infinity? :D
Jury Member: That is your problem! You should try to solve it for infinity.

But actual tests are the ones that can be calculated by hand.

Time limit

Depends on the patience of the juries. Usually around 10 minutes.

Memory limit

Free memory available in the PC given to you.

Note1 Original blog title was «Turkmenistan National Olympiad in Informatics sucks». And it really does.
Note2 Actually tasks had no names. I gave the names.
Note3 Feel free to give your answers for A,C,D.

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

Comments Comments (24)
| Write comment?
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In A we can assume that width of each rectangle is 0.5 and do DP[width][height].

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. Now write your solution and tell me your answer. I'll tell you if it matches the official answer.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain in more detail? Your solution seems to be incorrect. On the other hand, you can simply run 5 nested loops LOL:

    for a: 0.5 ... 4.5
for b: 0.5 ... 4.5
for c: 0.5 ... 4.5
for d: 0.5 ... 4.5
for e: 0.5 ... 4.5
if a+b+c+d+e == 4.5
  res = res+1
    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it 
      d[0][0] = 1;
for (int i = 1; i < 9; ++i)
{
	d[i][0] = d[i-1][0];
	for (int j = 1; j < 5; ++j)
		d[i][j] = d[i-1][j] + d[i-1][j-1];
}
cout << d[8][4]; // 70 here

      It's OK, but BIEmp's solution is better.

      → Reply
»
11 years ago, # |
← Rev. 15   Vote: I like it +6 Vote: I do not like it

In A: ?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    Your solution (70) doesn't match with official one (252). 0/5 points.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But actually, yes answer is 70. But official answer was 252. When we asked juries that answer was incorrect, they defended themselves by saying that width of the stairway doesn't need to be 4.5 unit. But problem statement that was given to us is exactly same as russian version above. Let me number this as nonsense#1.

      → Reply
»
11 years ago, # |
  Vote: I like it +17 Vote: I do not like it

N->∞ & "Time limit depends on the patience of the juries" lmfao

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint for D
Following is what one jury member told, when one of my friends wrote program for checking every possibility:
— This is not solved using recursion. Recursion is slow. This is solved using DP.

And don't think that he was joking. He seriously said that. Now tell me how this problem can be solved using DP. nonsense#2.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    dp[i][k][mask1][mask2] — true, if we can place k knights on first i rows, such that mask1 is positions of knights in (i-1)th row and mask2 is positions of knights in ith row.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Right. I didn't think about it (ДП по профилю, if I'm not mistaken). But as you can see, A is 5-loop problem, B is brute-force, C is non-IOI-like-at-all. I don't think, that jury had "ДП по профилю" in his mind when he told "... is solved with DP". He may at most mean knapsack when he says DP.

      P.S. What is "ДП по профилю" in English?

      → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

What is the correct answer for problem C?

→ Reply