dkjsfkhg's blog

By dkjsfkhg, 4 years ago, In English,

Hello. I found something weird today. Could you please check these two submissions?

Time Limit Exceeded

Accepted

They are both submitted with the same compiler (GNU C++ 14) and they don't differ even in a single character (You can compare them). How can they receive different verdicts? Is it related to how many submissions are being judged at the same time by Codeforces or ...?

Read more »

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

By dkjsfkhg, 4 years ago, In English,

Problem A:

Consider that we have rowi chocolates in the i'th row and coli chocolates in the i'th column.

The answer to the problem would be: . It is obvious that every pair would be calculated exactly once (as we have no more than one chocolate in the same square)

Time Complexity: O(n2)

C++ Solution

Problem B:

Consider that we have boyi males in the i'th day of the year and girli females in the i'th day of the year. These arrays can be filled easily when you are reading the input (See the code). Then for the i'th day of the year, we could have 2 * min(boyi , girli) people which could come to the party. The answer would be maximum of this value between all days i (1 ≤ i ≤ 366)

Time Complexity: O(366*n)

C++ Solution

Bonus: Try to solve this problem with O(n). For each interval given in the input, you don't need to iterate from day ai to day bi. This idea is used to solve problem 276C.

Problem C:

This problem can be solved with dynamic programming:

1. Calculate dpi, j : How many sequences of brackets of length i has balance j and intermediate balance never goes below zero (They form a prefix of a valid sequence of brackets).

2. For the given sequence of length n calculate the resulting balance a and the minimum balance b.

3. Try the length of the sequence added at the beginning c and its balance d. If  - b ≤ d then add dpc, d × dpm - n - c, d + a to the answer.

Time complexity: O((n - m)2)

C++ Solution

Problem D:

First of all, we calculate the volume of each cake: vi = π × hi × ri2.

Now consider the sequence v1, v2, v3, ..., vn : The answer to the problem is the maximum sum of elements between all increasing sub-sequences of this sequence. How do we solve this? First to get rid of the decimals we can define a new sequence a1, a2, a3, ..., an such that

We consider dpi as the maximum sum between all the sequences which end with ai and

dpi =

The answer to the problem is: π × maxi = 1ndp[i]

Now how do we calculate ? We use a max-segment tree which does these two operations: 1. Change the i't member to v. 2. Find the maximum value in the interval 1 to i.

Now we use this segment tree for the array dp and find the answer.

Consider that a1, a2, a3, ..., an is sorted. We define bi as the position of ai. Now to fill dpi we find the maximum in the interval [1, bi) in segment and we call it x and we set the bi th index of the segment as ai + x. The answer to the problem would the maximum in the segment in the interval [1,n]

Time complexity: O(nlgn)

Thanks to AlirezaT who helped a lot for writing the editorial of problem D.

C++ Solution

Problem E:

First of all, we assume that the tree is rooted! For this problem, first we need to compute some values for each vertex u: qdu and quu, cntu , paru, i and hu. qdu equals to the expected value of length of paths which start from vertex u, and ends in u’s subtree and also has length at least 1. quu equals to the expected value of length of paths which start from vertex u, and not ends in u’s subtree and also has length at least 1. to calculate this values we can use one dfs for qd, and one other dfs for qu. \ cntu is the number of vertices in u’s subtree except u, paru, i is the 2i ‘th ancestor of u and finally hu is the height of the vertex u. \ in first dfs (lets call it dfsdown) we can calculate qd, cnt and par array with this formulas:

for ecah $v$ as child of u and paru, i = parparu, i - 1, i - 1

in second dfs (lets call it dfsup) we calculate qu using this formula (for clearer formula, I may define some extra variables):

there are two cases:

u is the only child of its parent: let

then

\

u is not the only child of its parent: let

then

now we should process the queries. For each query u and v, we have to cases: one of the vertices is either one of the ancestors of the other one or not! In the first case, if we define w the vertex before u (u is assumed to be the vertex with lower height). In the path from v to u, the answer is

.

In the second case, if we assume w = LCA(u, v), then answer is

To check if u is one of ancestors of v, you can check if their LCA equals to u or you can use dfs to find out their starting and finishing time. u is an ancestor of v if the interval of starting and finishing time of v is completely inside starting and finishing time of u

The time complexity for the whole solution is O(n + mlgn) (O(n) for dfs and O(lgn) for each query so O(mlgn) for queries!).

C++ Solution

Read more »

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