andreyv's blog

By andreyv, 7 years ago, translation, In English,

Div. 2 A — Dragons

Observe that if Kirito fights a dragon whose strength is less than Kirito's strength, then Kirito does not lose anything — in fact, he even gains a nonnegative strength increase. Taking note of this, let's for each step choose some dragon whose strength is less than Kirito's current strength, and fight it. After performing some amount of these steps we'll eventually end up in one of these two situations: either all dragons are slain (then the answer is "YES"), or only dragons whose strength is not less than Kirito's strength remain (then the answer is "NO"). On each step we can choose a suitable dragon to fight either by searching through all dragons or by sorting the dragons by strength in non-descending order in advance.

The complexity of the solution is O(n2) or . Sample solution: http://pastie.org/4897164  

Div. 2 B — T-primes

It can be shown that only squares of prime numbers are T-primes, and that there are not too many of them — as many as there are prime numbers not greater than . Precompute these numbers (using, for example, the sieve of Eratosthenes) and store them in an array or an std::set, then we can answer each query by simply checking whether the number in question is amongst the precomputed numbers.

The complexity of the solution is linear in relation to n or , where d = 1012 (one can also get a tighter bound). Sample solution: http://pastie.org/4897166

Div. 1 A — Shifts

Let's compute the minimum number of operations needed to get all 1s in each of the m columns. For this, traverse each row twice — one time to the left and one time to the right, recording the index of the nearest cell with 1 (in corresponding direction) for each column in this row. Then the number of operations for any particular column is the sum of the computed values over all rows. In turn, the answer to the problem is the minimal value of these sums.

The complexity of the solution is O(nm). Sample solution: http://pastie.org/4897169

Div. 1 B — Planets

Observe that when we visit some planet, the best strategy is to arrive as early as we can and then wait for the nearest free moment of time to move further. Hence this problem can be solved with the Dijkstra's algorithm by slightly altering the definition of a shortest distance. When we process a planet (meaning that we already know the minimum time needed to reach it), we need to check the array of arrival times for this planet and find the first moment of time in which we can leave this planet — this will be the distance that we will be adding to outgoing paths from this planet. It's clear that we will traverse each array of arrival times no more than once. Additionally, one must pay attention to these cases: when a traveller arrives to planet 1 at time 0 (then Jack has to wait) and when a traveller arrives to planet n at the same time as Jack (then Jack needs not to wait).

The complexity of the solution — . Sample solution: http://pastie.org/4897171

Div. 1 C — Triangles

Let's call Alice's edges simply edges, and Bob's edges the antiedges. For each edge pair of the initial complete graph that pass through the same vertices, assign a weight: for each pair of edges the weight +2, for each pair of edge and antiedge −1 and for each pair of antiedges +2. Now calculate the sum of all the weights. Observe that each Alice's or Bob's triangle adds exactly +6 to the sum, and each combination of three vertices that do not form the triangle in any of the two graphs adds exactly 0 to the sum. The sum itself is calculated by iterating over all vertices and adding the total weight of all the edge pairs that pass through this vertex. If the degree of the vertex is d, then we should add d(d - 1) - d(n - d - 1) + (n - d - 1)(n - d - 2) to the final sum. Since each triangle adds +6 to the sum, then the answer is equal to the sum divided by 6.

The complexity of the solution is O(n + m). Sample solution: http://pastie.org/4897512

Div. 1 D — Towers

Let's calculate the dynamics d[i][k] — the minimal possible height of the last tower that we can obtain by merging the first i left towers into at least k towers. Assume we already have calculated the dynamics' values for the first i towers. Now we iterate over the all possible tower intervals [i + 1;j]; say the sum in the pending interval is equal to s. Now we find the greatest k such that d[i][k] is not greater than s. Then we update the value of d[j][k+1] to the minimum of s and d[j][k+1]. Notice that when k increases the values d[i][k] do not decrease. Because of that we can iterate over intervals in the decreasing value of j, and corresponding k can be found using a single pointer over values of d[i][k].

When we arrive in the position j during the dynamics, some of the d[j][k] values are updated, but some are still not. Using the same observation that along with the increasing of k the values d[j][k] do not decrease as well, we can make a single run over the values of k in the decreasing order and update the dynamics' values as follows: d[j][k] := min(d[j][k], d[j][k+1]). This is done in the beginning of the dynamics' iteration.

In the end we can find the greatest k for which there exists an answer among the values of d[n][k]. The answer to the problem then is n - k.

The complexity of the solution is O(n2). Sample solution: http://pastie.org/4897515

Div. 1 E — Gifts

First let's establish some facts that we will use in the solution. With how much probability can the fisherman get a particular set of gifts, among which there are ai gifts of i-th name? In total there are such sets, since there are exactly subsets of gifts with i-th name of size ai, and two different names are independent during the gold fish's choice. Then the described particular set of gifts we can get with the probability of , by asking ai gifts of i-th name.

Now we know the probability p of obtaining one particular gift set A. Now observe that from p we can calculate the probabiltity p' of obtaining the set A along with some one other gift of x-th name in constant time. Say there are already ax elements of x-th name in A. Using the formula from the first paragraph, we can deduce that:

Let's solve the main problem now. We sort all the gifts in descending order of their prices. It is clear that the fisherman will definitely ask the names of all the gifts among the first n ones whose prices are not equal to the price of the n-th gift in the list. Let's say that this set of gifts is the base, and it has b elements. Then there is still n - b unchosen gifts, and we know that all of them will have the price equal to the price of the n-th gift in the list. Say the price of the n-th gift is d, and there are exactly s gifts with the price d (keep in mind that each of them has a different name); also call these gifts dubious. We can also deduce that the fisherman can make different decisions, where l = n - b.

So now we have some s dubious gifts with the price of d; let's enumerate them in any order. We calculate the dynamics f(x, y) — the cumulative probability of obtaining n most valuable gifts, if there are x chosen from the first y in the list. It is clear that f(0, 0) = p, and f(l, s) contains the answer to the problem. Using the coefficients we have deduced earlier, we get two transitions in the dynamics:

  1. , if we add y + 1-th dubious gift to the set of x chosen among the first y dubious gifts;
  2. , otherwise, if do not put the y + 1-th dubious gift. This dynamics can be computed in O(t2) time, where t is the total number of gifts.

The complexity of the solution is . Sample solution: http://pastie.org/4897519

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

»
7 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Div 1 D can be solved in O(n). Very similar problem was at USACO Open 2009: http://tjsct.wikidot.com/usaco-open09-gold problem 3. Unfortunately I can't find any link to the solution. The idea was that making the tower the narrowest is equivalent with making it the tallest, and counting the narrowest tower is somehow easier. I don't remember it very good.

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Div 1 C's formula is wrong, I think. It's d(d — 1) — d(n — d — 1) + (n — d — 1) * (n — d — 2).

»
7 years ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

in Div1 C we can solve it easier:

let t = number of all possible triangles (n(n-1)(n-2)) / (1*2*3);

we restore degree of vertex like when we scan ai and bi -> x[ai]+=1; x[bi]+=1; where 1<= i <=n

let k = sum of all (di * (n-1-di)); where di = degree of i'th vertex;

then k=k/2; because we count each wasted triangle twice ;)

then answer is t-k :D

in here you must use long long or __int64

in this solution I just removed wasted (made with bob's and alice's edges) triangles from all possible triangle

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

    Can you explain this answer?

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

      I think you didn't understand where I'm getting the k value... lemme explain it :)

      I'm counting the wasted triangles.. the wasted triangle forms with connected 3 edges. (1 Bob's edge and 2 Alice's edge.. or otherwise). and it store 2 of vertices which connecting bob's edge with alice's..

      I take one vertex, then I'm counting how many wasted triangles with that vertex can form (triangle's vertex connecting both Alice's and Bob's edges). di contains degree of vertex. number of edges going from that vertex (also choosen that is choosen edge by Alice).. I'm multiplying it with Bob's edges starts with that vertex.. that is (n-1-di) and we get the wasted triangle's vertex number's sum...

      as we said every wasted triangle stores 2 of vertex with that property (connects bob's edge and Alice's), we have to divide k with 2... we get wasted triangle's number... then remove it from all possible triangle's number. ;-)

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

        Thank You, so nice of you!

        I didn't understood why were you dividing it by 2 . Now I do!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B Div2, how can it be shown that the square of a prime number will always have 3 divisors? I am only able to prove that any perfect square will have an odd number of divisors.

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

    T-prime ? div by 3 numbers ... but any prime no is div by itself and 1 .. so T = 3 -2 = 1 .. the remaining case is ? div by its square root

    here may come a question like why the remaining case must be its sqrt no .. : bec. allowance of any number other than its square means what ? reflection of another no that is div by ... ex. : 6/2 so (2 can be counted) and automatically : 6/ (6/2) can be counted also so any no other its square root will give a reflection in greater than square number

    i think andreyv can declare it in the blog in a much better way .

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Once again TLE due to cin and cout without syncing it in div2 B!