I_love_Hoang_Yen's blog

By I_love_Hoang_Yen, 9 years ago, In English

Below is very short description of solutions to problem that I can solve. Because it is "short description", for most problems, there is no proof of correctness. Proving the solutions is up to you.

100541A - Stock Market

This is the most simple problem in the set.

Observations:

  • If you buy stock, you're better to buy as much as possible.
  • If you buy stock on the i-th day, then you will always sell every stock on some j-th day, where j > i and the price of the stock on the j-th day is maximal.

Now we have an algorithm that runs in time O(N):

  • Initialize f(i) to be the maximum value of the stock price from i-th day to N-th day.
  • For each value of i from 1 to N, try to buy stock on i-th day, and find the value that you will sell these stocks using f(i+1).

100541B - Sum

Observation:

  • There's only small number of different values of [N/i]. In fact, we can prove that there's only O(sqrt(N)) different values:

Using the above observation, we have a O(sqrt(N)) algorithm:

i = 1
result = 0
while i <= N:
    value = N / i
    last = N / value    // This is the last value such that (N / last) still equals to (N / i)
    result += (last - i + 1) * value
    i = last + 1
print result

100541C - ATM withdrawal

First, there's no solution when N mod 1000 > 0. After dealing with this, we can divide N by 1000.

Obvious (and wrong) greedy solution:

  • Let u = N mod 10. Using notes 1, 2, 3, 5, pay u.
  • Divide N by 10
  • Repeat the above 2 steps for c+1 times.
  • For the remaining values, pay using 5*10^c.

This greedy is wrong with the following test: N = 110 (after dividing by 1000), and c = 1. It calculate the number of ways to pay N value incorrectly. (correct answer is 2: 110 = 50 + 30 + 30 = 50 + 50 + 10, while the greedy will find 1).

But we can fix this greedy solution:

  • Let t = the note with maximum value. Before applying the above greedy, we pay X notes with value t, where X = (N — t) / t.

100541D - Treasure Box

Observation:

  • After at most 100 transformations, X mod 100 will become some value that we already seen.

In other words, the sequences of transformation will look like this:

 + a1 + a2... + ai + b1 + b2... + bk + b1 + b2... + bk + b1 + b2... + bk + ...

So we can group b1, b2, ..., bk together, and calculate the result in O(k).

100541E - ACM

Observation:

  • There is only small number of primes (36 primes) below 150.

Algorithm:

  • Build 36 segment trees. Each node in the k-th segment tree stores the power of the k-th prime in the product of in the corresponding segment.
  • Using the segment trees, we can update / query for each prime in time O(log(N)).

Traps:

  • You must use long long
  • MOD can be equal to 1

100541H - Pencil Game

Let i, j be the first and last column of the result sub-rectangle. Let u, v be the first and last row of the result sub-rectangle.

By using basic algebraic transformations, we have:

2 * L = (j - i + 1) * (v - u + 1) * (N * (u + v) + (i + j))

Let W = j - i + 1 and H = v - u + 1. Note that W * H is our solution.

Because the number of factors of an integer is small, we can loop through all possible values of W and H (first generate all factors of L, then consider only the factors of L). For each pair (W, H), we can uniquely find u and i, and check if it is indeed a valid solution.

100541I - Space Tour

This is a dynamic programming problem. Note that the 4 different paths do not have a common point, so we can consider them separatedly. Use 4 different dp functions to calculate the length of each 4 path.

For example, the path that initially go to left direction can be calculated this way:

for i = 1..M:
    for j = 1..N:
        if a[i][j] == 1:
            f[i][j] = 1
            if a[i-1][j] == 1:
               f[i][j] = f[i-1][j-1] + 2

After calculating the 4 dp functions, we can loop through each starting position (i, j) and calculate the result if we start at this position.

100541J - Math Magic

This is another dynamic programming problem.

Let f(i, x, y, z, t) be the maximum score you can get if you used some tiles 1..i, and the colors at the four directions are x, y, z, t.

From f(i, x, y, z, t), you can calculate all values of f(i + 1, x', y', z', t') by trying all possibilities of adding the (i + 1) - th tile to one of the four directions.

This solution is a bit slow to get accepted. You can try following optimizations:

  • Only consider reachable states (i, x, y, z, t).
  • Only consider states where x <= y <= z <= t.

Traps:

  • Result can be negative
  • Vote: I like it
  • +17
  • Vote: I do not like it

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

I remember that Problem E has 35 primes.(Maybe that's not important><)

And I have many feelings when I was working for problem E.

(><My English isn't so great.I hope you can understand it><)

First I always got TLE on test 2.

I started to look over my program carefully,but I didn't get any information.

After my teammate's reminder,I found out that I hadn't used LONG LONG type!

Then I submitted happily but soon I got WA on test 2!

In about nearly two hours after that,I looked over my programs one after another,

But I didn't get any information too and still got WA.

Finally I noticed that maybe the P is equal to 1 and the numbers of 35 primes are all equal to 0.In this state,my program doesn't do anything and print initial value of answer——1.

Now I'm a bit upset but I'm also happy to get this valuable experience!

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The experience is interesting! I'm wonder that how can you find that bug.

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think that complexity of problem E is too big. It's about T*(m*35*log(n)*log(X)), with log(X) is time to calculate a^X (X is a long long number). I still get TLE on test 2.

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

    Yes.

    To pass time limit, for queries 1 and 2, you must loop through only the prime factors.

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

My algorithm worked O(35 * m * log(n)) with segment_tree, but I get WA #2. Can you help me!!!

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

    Ooooo sorry, I have found my mistake, I haven't seen L > R

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

I think the solution of problem B missing something, i is not change.

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

can someone provide a more detailed solution of problem I ?

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

http://paste.ubuntu.com/10600334/

Any ideas why this is giving WA? Thanks in advance.

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

Can you help me with problem E ?

I solve this problem as tutorial :

  • I use 35-segment_tree . Each node in the k-th segment_tree stores the power of the k-th prime in the product of in the corresponding segment.

  • I also pre-calculate the prime factors of the integer from 1 to 150, to pass time limit for queries 1 and 2 (as I_love_Hoang_Yen said)

But I still get TLE on test 2.

This is my code.

Explanation :


vector<int> p : contain the primes from 1..150 vector<ii> fact[x] : contain the prime factors and the power of x : i = 0..fact[x].size()-1 fact[x][i].X = the prime factor that fact[x][i].X | x fact[x][i].Y = the power of fact[x][i].X in x ll t[idx][k], lazy[idx][k] : idx-segment_tree with node k and idx-lazy with node k (base-0) int pos[0..34] : the index of the (i+1)-prime
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You calculate power inside your get method. So the complexity is log(N)2 for each call to get.

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

Hello)) Can I see 2th test in task C or where I can find it? My solution: http://pastebin.com/RsGnM6M7

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

Can someone please explain H a little deeper (**Pencil Game**). I found the factors of L in O(sqrt(L)) and then iterated over them as:

bool ans = 0;
for(int i = 0; i < factors.size(); i++)
{
    w = factors[i];
    if(w>n)continue;
    for(int j = 0; j < factors.size(); j++)
    {
        h = factors[j];
        if(h>m)break;
        if(((2*l) % (w*h) != 0)) continue;
        k = (2*l)/(w*h) &mdash; (h-1)*n &mdash; (w-1);
        if(k&1)continue;
        k = k/2;
        u = k/n;
        x = k%n;
        if(u + h <= m && x + w <= n)
        {
            area = min(area, w*h);
            ans = 1;
        }
    }
}

After this, I check if ans = 1, then I print area, otherwise I print -1. I am getting TLE on test 2. Please guide me.