Блог пользователя natsukagami

Автор natsukagami, история, 9 лет назад, По-английски

VOI (Vietnam National Olympiad in Informatics) 2016 has just ended a few hours ago. You are given 6 problems (3 each day) to solve in the time of 180 minutes per day. As a contestant, I must say for such a small window of time I just couldn't do them all. Anyways here are the (of course, shortened version of) statements of the problems.

The problems have a total score of 40, which divides to 6 / 7 / 7 per day.

Day 1

Problem 1 (6 pts)

You are given a sequence of numbers A[1..n] (1 ≤ Ai ≤ 109). You have to erase the least amount of numbers in the sequence such that for every i < j in the new sequence the following condition holds: .

50% of the tests have n ≤ 20. The remaining have n ≤ 2000.

Problem 2 (7 pts)

There is a road which has a length of L. You have a truck with the fuel tank capacity of K, and start off with Q litres of fuel at one side (point 0) which you will have to deliver to the other side (point L) of the road. Your truck consumes 1 litre of fuel per unit of length it travels. In order to help you, starting from point 0 there is a fuel tank with unlimited capacity every D units of length (so there are tanks on point D, 2D, ... and they are empty at start). You are allowed to transfer the fuel in and out of any tank. Maximize the amount of fuel you can deliver to point L.

Given L, K, Q, D, calculate the maximum amount of fuel you can deliver to point L.

Constraints: 1 ≤ L, K, D ≤ 109, 1 ≤ Q ≤ 1012. On the first 50% of the tests .

Problem 3 (7 pts)

You are given an undirected connected graph G(V, E) of n vertices and m edges (with no self edges and multi-edges) and the following algorithm to construct K:

  • First, initialize K[1..n] as an array of empty vectors of integers. Let K[1] = {0}.

  • Let f[1..n] be an array of booleans, all being false at start. Let Q be a set of indices i such that f[i] = false and |K[i]| > 0

  • While |Q| > 0:

    • Let u be the smallest number in Q. Set f[u] = true
    • For each edge (u, v) in G such that f[v] = false we append u into back of K[v].

Please renumber all the vertices in the graph so that for the resulting array K of the algorithm the following condition holds: For every u < v we have K[u] ≤ K[v] alphabetically.

Constraints: 40% of the tests have n ≤ 10. 80% of the tests have n ≤ 103, m ≤ 104. All tests have n ≤ 2 × 104, m ≤ 106.

Day 2

Problem 1 (6 pts)

You are given a grid of n × m cells, each containing a zero or one. Find the diamond-shaped area (which has to be fully inside the grid) containing the most ones such that no two one cells inside the area share the same edge.

A diamond-shaped area with center (x0, y0) and radius r is a set of cells (x, y) which satisfies |x - x0| + |y - y0| ≤ r.

Constraints: 40% of the tests have n ≤ 100. 80% of the tests have n ≤ 500. All tests have n ≤ 1000.

Problem 2 (7 pts)

You are given a set of n operations containing at most 4 numbers within [0..106] and operators +, -, *. You have add brackets to some of the equations such that each of them has an unique value.

Constraints: 50% of the tests have n ≤ 20 and operations having at most 3 numbers. All tests have n ≤ 2000.

Problem 3 (7 pts)

You are given n trees (real world trees) with the i-th tree having height hi and stands at position i and you have to fall down all of them. Falling the tree i to the left causes all trees j with i - hi < j < i to fall to the left, and falling tree i to the right causes all trees j with i < j < i + hi to fall to the right (and they to make chains like dominoes). Find a way of cutting the trees such that the number of trees manually fell at minimized.

All trees have height not exceeding 4 × 106

Constraints: 40% of the tests have n ≤ 104, 80% of the tests have n ≤ 105, all tests have n ≤ 4 × 106

  • Проголосовать: нравится
  • +64
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Anyone know how to solve the second subtask of the first problem — Day 1?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Here's a hint:

    Let's use dp. Looking at the statements, we can easily find out that: if we sort all numbers from smallest to largest and then check all of them from left to right, when we consider Ai, any number smaller than Ai - 10 can be ignored.

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Is there anyway to solve problem 2 (day 2) without using big integer ? As 1000000*1000000*1000000*1000000 may result in a 24-digits number.

Ans how is your team's performance ? Did they do well ?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    I really ignored the bigint thing and let it overflow — consider it as a 2^64 hash. It will cause some trouble, hopefully not too huge.

    Well actually you can perform multiple base hash and it should be as good as implementing bigint.

    About my team's performance, I must say... not so well. None of us expected this difficulty on the first day (compared to last year's problems, even the 6-pts problem was as hard as last year's 7-pointers. VOI rounds aren't usually that difficult, it was meant to be quite easy somehow), and the expected implementing skill on the second day.

    Mostly depend on luck now :)

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Can you please write short-editorial? :)

My sketches about the problems (day 2):

  1. We can rotate a table by 45 degrees. Now our task is to find a square, which can be solved in N^2logN (fix one corner and do binary search).

  2. We have small amount of bracket-arrangements, so we can construct a bipartite graph and do a max-matching algorithm.

  3. Seems like a simple DP problem.

Did I miss something and my solutions are wrong?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I can write a short editorial, when I have all complete solutions :) Your solutions are correct (though I have an O(n2) for the first problem)

    But try implementing all of them (all with traceback included, not funny) within 3 hours, you shall find out how difficult it is :)

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Could you please explain day1 problem 2 statements? Because I'm reading it like this:

You have to deliver Q litres of fuel from one to the other

And then I'm reading this and feel frustrated

Maximize the amount of fuel you can deliver to point L

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    It means that you have Q litres of fuel in a tank at point 0, and you have to maximize the amount of fuel you can deliver to point L.

    I hope it sound more clear now :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

where can I submit my solutions?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Since the contest is offline I'm afraid you cannot submit (for now) unless you actually compete.

    • For now, because the unofficial testdata is being uploaded to our SPOJ site soon.
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

On Day 1, problem 2, you mention we want to deliver Q units of fuel. At the end, the statement says we want to maximize the amount of fuel delivered to point L. Could you clarify the exact goal?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by natsukagami (previous revision, new revision, compare).