andreyv's blog

Codeforces Round #142 Problem Analysis
By andreyv, 12 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 (archived copy)  

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 (archived copy)

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 (archived copy)

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 (archived copy)

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 (archived copy)

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 (archived copy)

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 (archived copy)

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

Comments Comments (27)
| Write comment?
»
12 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.

→ Reply
»
12 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).

→ Reply
»
12 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

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

    Can you explain this answer?

    → Reply
    • »
      »
      »
      9 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. ;-)

      → Reply
»
7 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!

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

Hi, I got struck for Div-2B T-Primes. I am getting TLE for TC-63. Can anyone help?

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

    The same thing happened to me :) I fixed it by: Check if the number is 4. If it is, answer is yes. Otherwise, check if it is divisible by 2. If it is, answer is no. Or else do the classic primality test like this: j = 3; j*j <= sqrt(number); j += 2. (So instead of looping through even numbers repeatedly, we are ignoring them and using odd numbers only because all primes other than 2 are odd).

    Accepted code

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

can someone give me a sample solution for Div.2 B problem — T primes. The sample solution link is not working.

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

I have a really simple 1-dimensional DP solution to problem D of Div1, Towers.

Main idea: for the array $$$a_1 a_2 ... a_N$$$, the minimum number of moves to make it non-decreasing corresponds to the smallest height of the last element of the resulting sequence.

For proving this, we can use induction on the index. Let's say it is true for $$$1...j$$$. Then for $$$j+1$$$, we can show that the number of moves to take last $$$m$$$ elements is less than the number of moves to take the last $$$t$$$ elements, where $$$t>m$$$, which results in the $$$m$$$ case to have a smaller value of the last element. We need the inductive hypothesis to classify $$$m$$$ and $$$t$$$ as valid indices.

Feel free to reply if you have any difficulty.

84694143

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

I just want to inform that the sample solution links given in the Editorial are not working anymore.

Thanks

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It Was Very Helpful thank you for this post.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell me what is wrong with my code. it gives error in like 20550th case in 24th test, but i dont understand why...\

include <bits/stdc++.h>

using namespace std; using i64 = long long int; using u64 = unsigned long long int; using u32 = unsigned;

int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; while(n--) {i64 a; cin>>a; float k; bool flag = true; if(a==1) flag = false; int j = a;

k = sqrt(a);
a = sqrt(a);

if(k!=a)
flag = false;
else {
    long long int p;
    p = sqrt(a);
    if(a%2)
    for(int i =2;i*i<=k;i++)
    {
        if(a%i==0)
        flag = false;
    }
    else flag = false;
}
if(j == 4)
flag = true;

if(flag)
cout<<"YES"<<endl;
else cout<<"NO"<<endl;

}

return 0;

}

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

    nevermind, i chose float insted of double which probably gave error though I still dont know the exact reason

    → Reply