I would like to write participation commentaries of Beta Round #33. I'm sorry my English may be poor.
And let dp2[n]:=(maximum sum using only "suffix multiplication" operation if an input is a[n],a[n+1],...,a[N]). This is also calculated as same as dp[n].
Then the final answer is max_{n} (dp[n]+dp2[n]).
A way I tried was the latter tactics. First of all, I constructed a graph with M vertices. In the graph, there would exist an edge between node i and node j, if a fence i contains a fence j strictly. "a fence i contains a fence j strictly" means that there is no fence between the fence i and the fence j.
Construcing such a graph in O(M^2) is not so plain, but it can be done as follow: 1. sort all fences by their radius 2. see each fence from smaller one, then check if the fence contains the other fence strictly. Because it can be said that every fence will be contained by at most one the other fence, we need to check only fences that is not contained by any fence.
It would help implementation to add an "outer envelope" fence as a sentinel value like R=1e14, P=(0,0) , because: 1. adding it will not change any result 2. by adding it any control point will be contained in exactly one fence strictly.
After constructing the graph, we will calculate distance[i][j] for each pair (i,j). This can be done by some depth-first-search approach, starting from top node(outer envelope).
Implementation of above algorithm was laboring and I took much time. I finally got AC with 1 resubmission.
After contest I read some solution of other people, and following method looked quite good.
For each query, we can also calculate the answer by counting the number of fences that enclose only i or j. (i,j is an index of a control point)
If we use this method, the time complexity will be O(10^5*10^3)=O(10^9) and we would got TLE.
But if we calculate this not by bool[] one by one, but each bit of unsigned long long, it will be O(10^9/64) ~ O(1,562,500), then the method will be good for the time limit. I think this method is comprehensible and clever.
A What is for dinner?
The problem is quite easy, but the problem statement is a little hard so I got as many as 2WAs. This made me upset a little.B String Problem
This problem is also easy if we know warshll-floyd algorithm. But I confused the specification. I translated the statement "According to the game rules, with each move Valera can change one arbitrary character Ai in one of the strings into arbitrary character Bi..." as "each string can be moved at most one time" by mistake, and I spend much time in wrong and heavy coding, then I got 1WA.C Wonderful Randomized Sum
Simple DP Problem. Let dp[n]:=(maximum sum using only "prefix multiplication" operation if an input sequence is a[1],a[2],...,a[n]). Each dp[n] can be calculated by as follow.dp[0]=0;
ll mm=-1LL<<50;
FOREQ(j,1,N) {
mm=max(mm,-2*sum[j]); //sum[j] is a sum of a[1],...,a[j]
dp[j]=sum[j]+mm;
}
And let dp2[n]:=(maximum sum using only "suffix multiplication" operation if an input is a[n],a[n+1],...,a[N]). This is also calculated as same as dp[n].
Then the final answer is max_{n} (dp[n]+dp2[n]).
D Knights
Interesting problem about geometry and graph. Query number k is large, so a program must calculate each query as fast as possible. Or, it is also good to calculate all possible M^2 queries in advance.A way I tried was the latter tactics. First of all, I constructed a graph with M vertices. In the graph, there would exist an edge between node i and node j, if a fence i contains a fence j strictly. "a fence i contains a fence j strictly" means that there is no fence between the fence i and the fence j.
Construcing such a graph in O(M^2) is not so plain, but it can be done as follow: 1. sort all fences by their radius 2. see each fence from smaller one, then check if the fence contains the other fence strictly. Because it can be said that every fence will be contained by at most one the other fence, we need to check only fences that is not contained by any fence.
It would help implementation to add an "outer envelope" fence as a sentinel value like R=1e14, P=(0,0) , because: 1. adding it will not change any result 2. by adding it any control point will be contained in exactly one fence strictly.
After constructing the graph, we will calculate distance[i][j] for each pair (i,j). This can be done by some depth-first-search approach, starting from top node(outer envelope).
Implementation of above algorithm was laboring and I took much time. I finally got AC with 1 resubmission.
After contest I read some solution of other people, and following method looked quite good.
For each query, we can also calculate the answer by counting the number of fences that enclose only i or j. (i,j is an index of a control point)
If we use this method, the time complexity will be O(10^5*10^3)=O(10^9) and we would got TLE.
But if we calculate this not by bool[] one by one, but each bit of unsigned long long, it will be O(10^9/64) ~ O(1,562,500), then the method will be good for the time limit. I think this method is comprehensible and clever.
Comments (0)
