The answer for the problem is calculated with a formula ((a - 1 + b) n + n) n + 1.
Such solution has complexity O(1).
There is also a solution with iterations, modelling every of |b|'s Vasya's moves by one entrance one by one in desired direction, allowed to pass all the tests.
This solution's complexity is O(|b|).
Let's consider the participants from every region separately. So for every region we just need to sort all of its participants by their score in non-increasing order. The answer for a region is inconsistent if and only if the score of the second and the third participant in this order are equal, otherwise the answer is the first and the second participant in this order.
The solution complexity is .
Our task is to take largest amount of toys Tanya doesn't have yet the way the sum of their costs doesn't exceed m. To do that one can perform greedy algorithm: let's buy the cheepest toy Tanya doesn't have at every step, while the amount of money left are sufficient to do that. The boolean array used can be a handle in that, storing true values in indices equal to toy types which Tanya does have at the moment. As soon as 109 money is sufficient to buy no more than 105 toys , used is enough to be sized 2 × 105 (we won't buy the toys with types numbered greater). So we just need to iterate over the number of type we want to buy, and if corresponding value in used is equal to false, we should buy it, otherwise we can't.
The solution complexity is .
One can use the <> data structure (C++ \texttt{std::set}, for example), for storing the types Tanya has at the moment. In this case the complexity is .
From the track description follows that Maria moves the way that the water always located to the right from her, so she could fall into the water only while turning left. To check if the turn is to the left, let's give every Maria's moves directions a number: moving to the north — 0, moving to the west — 1, to the south — 2 and to the east — 3. Then the turn is to the left if and only if the number of direction after performing a turn dir is equal to the number before performing a turn oldDir plus one modulo 4 .
This solution has complexity O(n).
One can solve this problem in alternative way. Let the answer be equal to x (that means that the number of inner corners of 270 degrees equals x, but the number of inner corners of 90 degrees to n - x). As soon as the sum of the inner corners' values of polygon of n vertices is equal to 180 × (n - 2), then x × 270 + (n - x) × 90 equals to 180 × (n - 2). This leads us to , being the answer for the problem calculated in O(1).
One should notice, that for every connected component of the graph the problem could be solved independently, so we just need to solve the problem for any connected graph.
Let this connected graph (of n vertices) contain n - 1 edge (such is called a tree). If one maintain a DFS from any of its vertex, every edge will be oriented, and each of them could given to its ending vertex, this way every vertex (except the one we launched DFS from, that is the root) will be satisfied by an edge. In this case the answer is equal to 1.
Let's then deal with a case when the graph contains more than n - 1 edges. This graph contains at least one cycle. Let's take arbitrary vertex from any of the cycles and launch a DFS (as above) from it. All vertices except chosen will be satisfied, so we are to give an edge to the chosen vertex. As soon as chosen vertex belongs to a cycle, at least one of its edge will not be taken to account in the DFS, so it can be given to a root. This way all the vertices will be satisfied.
Now we are able to solve the task for any connected graph, so we are to divide the graph into a connected components — this can be easily done by DFS or BFS.
The solution complexity is O(n + m).
In this task one should find a connected area, in which the product of the minimum value of the cells and the number of the cells is equal to k. To find such, let's sort all the n × m cells by their values by non-increasing order. Then we will consecutively add them in this order one by one, maintaining a connected components on their neighbouring relations graph. It's enough to use Disjoint Set Union structure to do so, storing additionally size of every component.
Let ai, j be the last added element in some component id, so ai, j has the minimum value among all the cells in component id (according to our ordering). If ai, j does not divide k, then the component id could not consist of desired area. Otherwise (ai, j is divisor of k), let's find need = k / ai, j — desired area size (if it contains ai, j), and if CNTid is not less than need, then the component id contains desired area, which could be easily found by launching a DFS in a neighbouring relation graph from ai, j, visiting only the ap, q ≥ ai, j and exactly need of them.
The solution complexity is .
Let the answer for the problem be the sum
where calc(l, r) is the number of ways to cut the top part of the fence the way its leftmost part is in position l and the rightmost in position r. If l = r, that is the case when the cutted top part consists of part of only one board, then calc(l, r) = hl - 1.
Let r > l, then
In other words, the number of ways to cut the top part of some board is equal to minimum value among heights of it and its neighbours minus one, otherwise the cutted part will be inconsistent. Leftmost board and rightmost board are considered separately, because each of them does have only one neighbouring board. So the answer looks like
The first summand is easy to calculate, so let's take a look at the second. Let us modify it as the following:
Let
Let's take a look how does the S(r) change after increasing r by one:
S(r + 1) = S(r) × min(hr - 1 - 1, hr - 1, hr + 1 - 1) + min(hr - 1, hr + 1 - 1).
This way this sum is easy to maintain if consecutively increase r from 2 to n.
The solution complexity is O(n).
Thanks for nice problems и fast Разбор
Fixed. Thank you)
Thanks for the lightning speed EDITORIAL.
In F problem, I haven't seen the limit that must have an unchanged cell... So I wrote a code in O(sqrt(min(k, 1e15)).. When k > 1e15 print "NO", then enumerate the factor of k, use dsu to solve it, and got WA4. After contest I found the limit and add it then accepted...sad..
The best contest i've seen so far, I really liked the problemset and the fact that is was a 7 problem round instead of the regular one. Great job!
why this 17050130 gets WA in problem E?!!
any one can provide a small case which make it fail ?!
Problem should be solved for every component independently.
I believe this input is a small one where your program fails. There are two connected components: one is a tree and the other is a super well-connected component. The main idea for this test is that the degrees for some vertices are large enough so that when you subtract m edges, then you will not end up with any zeros.
Yea, you don't need to read other comments, better post the same idea that i've already posted but with two times bigger test, good job.
I feel guilty for doing this 17058751 for 659D - Bicycle Race:
I simply used
java.awt.Polygon
class to create the lake polygon.If Maria misses turn
i
, she would proceed bydx = signum(x(i) - x(i+1))
,dy = signum(y(i) - y(i + 1))
Then I simply checked if lake polygon contains
(x(i) + 0.5*dx, y(i) + 0.5*dy)
Well i guess that's still more ethical than "cout<<(n-4)/2";
Can anybody explain why that is correct?
No idea
It's all explained in the editorial, but:
- assume that for all polygons (convex or concave) the sum of internal angles is 180(n - 2)
- for this problem, there are only internal angles of 270º and 90º and we need to count how many (x) of the former ones exist:
I used ray casting with the same approach...
One line code for problem D using
Point2D.relativeCCW()
submission
This one also
Hello everyone , Why testcase 53 is not correct in my answer since my answer totally matched with jury answer here is the link... for problem 2
You have to check if
vec[i].size() > 2
before accessing the third element viavec[i][2]
. Otherwise you may access unallocated memory. I made the same mistake...Why does this only seem to fail on test 53? Even the first test case has a region with 2 people.
Suppose size is 2. Then suppose that vec[i][0] = vec[i][1]. Then you will look for vec[i][2] to compare with vec[i][1], but that element might not exist (causing Runtime Error). In samples vec[i][0] > vec[i][1], so you didn't need the third element.
There is a parsing error in the editorial of F
I solved D by finding point inside a polygon . I had to code almost from the scratch because somehow geeksforgeeks code was not working -_- . And after seeing this O(1) solution.....
Happened with me too !
I found a working code though ( around 7 lines )
Hey,,please give me the link for this code's tutorial
Here You Go :D
Can anybody tell me why i have a WA in test 15 of problem B?
The problem is where you print the answer.
When there are only 2 people in a region the if statement access an irregular position in memory.
I made this check and I got WA in test 15... Can someone tell me why, please?
oh, true! Thank you!
Hello,
sure, it is because you forgot to check size of vector
make the checking line:
if (v[i].size()<3u||v[i][1].p != v[i][2].p)
Thank you!
could you please help me in problem B.I am also facing WA on Testcase 15 . MySubmission 19938161
Here
This modification worked :)
Could anyone help me with that http://codeforces.me/contest/659/submission/17057892 ?
BFS do not check for one cell solution.
My solution for problem D is to count the number of left turn and the number of right turn then take the minimal of them. I have no idea why it works. It was a desperate attempt. Can somebody provide a proof? Thank you!
My submission: http://codeforces.me/contest/659/submission/17055311
My guess is number_of_right_turns = number_of_left_turns + 3
So number_of_right_turns is always greater than number_of_left_turns.
You are actually taking number_of_left_turns.
Just cout << posi << endl; also get AC.
Can someone explain problem F in more detail please? Basically for each cell with value v, you want to know C(v) = how many cells are connected to it that are at least v. When you sort by decreasing value and DSU, won't your calculation of C(v) for cells with the same value be wrong? For example this grid:
2 4 5
6 4 3
I didn't notice that in problem D we may only drop into water on left turn and solved the more generalized version of the problem.
The idea is we can record all the vertical and horizontal segments, and for each turning point we can count how many segments we may intersect if we keep going straight. If the count of segments is odd then this point is dangerous, and not while the count is even.
How does that formula come in problem number A ? Can somebody illustrate please ?
Forget the formula. Basically, all you need to do is to make a loop. When the system has 5 rooms, going 6 rooms front actually means going 1 room front, right? For backward movement, 2 rooms back means 3 rooms front. Just keep adding the number of total rooms until you get a non negative number. So taking mod is enough. Just to avoid 0'th position, as 5%5 or 6%6 makes zero, but you want to print 5 or 6, the mod operation is done in two steps. Eventually the -1 with a and the +1 at the end don't make any difference.
In 2nd Problem, why is the output on terminal and Codeforces Judge different??
I got WA on 1st pretest again and again because of this..
My solution is :- http://codeforces.me/contest/659/submission/17065952
1) You are doing ios_base::sync_with_stdio(0);
2) Then read something C-style: scanf("%d %d",&n,&m);
3) Then read something C++-style: cin>>str>>reg>>score;
Due to 1), 2) and 3) both read same data. I.e. in 3 you read very first input line instead of second.
Hello for problem D, I have a doubt what property does this test case violate:
The first vertex should be the one more in the south and in the west
Thanks!
First of all, thank you for the quick editorial!! I would like to mention 2 points regarding the editorial:
The phrase "as soon as" is used in places where "since" or simply "as" should be used. It is not that important(since the intention is very much clear), but feels odd! :P
For problem E, I did not understand the part "...as chosen vertex belongs to a cycle, at least one of its edge will not be taken to account in the DFS, so it can be given to a root. This way all the vertices will be satisfied." clearly. Can someone explain it in more details?
It is perhaps slightly misworded. The key idea is that for any tree, we can pick any root and direct each of the edges so that only the chosen root of the tree is unaccessible. Therefore, if the program finds a cycle in a connected component, and we assign the root to any node of the cycle then one can perform the same algorithm, except this time there will be one extra edge incident to the picked root (otherwise, the cycle wouldn't exist). This extra edge can, of course, be directed to make the root accessible as well, thereby solving the problem.
So, in short, does this mean the following?
The final answer is the sum of the answers for each individual connected component.
For a connected component, the answer is 1 if the component is a tree, 0 otherwise.
Yes!
can any one tell why am i getting RTE on problem B
this my submission
Good day to you man!
The RTE is because of sort :'( you have to change comparator:
like this :)
+btw I'm convinced the part at the end is also wrong :/
I would change it like:
Thnx !! it worked !! but i can't understand why RTE ?!
Well, sort comparator must be deterministic.
That means it must decide (in finite time) for each pair of elements, whether one of them is bigger (and which one) or whether they are equal.
a: A < B && !(B < A) means A < B
b: !(A < B) && B < A means A > B
c: !(A < B) && !(B < A) means A == B
anyway A<B && B<A (which could have been returned in your program) is "nothing" so the function could not determine, how to sort it :)
Can someone explain solution for F in more details ?
Problem G has a divide and conquer solution too ... :P *I wanst able to arrive at the formula stated in the editorial but divide and conquer was a bit more intuitive to me *
Link to submission- http://codeforces.me/contest/659/submission/17075860
thanks for your share :) it's very helpful.
can anyone explain solution of problem E in detail.
Every connected component of the graph, could be solved independently. Each connected component has at most 1 vertex with ending degree 0 after all (solving optimally) . If the connected component is a simple path or a tree root on a vertex v, we may notice that this component has 1 vertex with ending degree 0. If the connected component is cyclic, starting on any node we can organize the Edges in order to take no edges with ending degree 0. Imagine we have one conected component witch has a cycle and a path or a cycle and a tree or both :) , for example this: 1-2, 2-3, 3-1, 1-5, 5-6; Notice we can turn it into the problema of the cyclic connected componen. For this, we can also pick the vertex with in-out degree=1 and connect it. For example: 1-2 , 2-3 , 3-1, 1-5 5->6; 1-2,2-3,3-1, 1->5, 5->6; In this phase we have the same cycle! Therefore, we can run a dfs for each connect component and verify if it has any cycle. If it has add the answer by 1, if it has not, add the answer by 0.
If it has a cycle, we should not add 1 to the answer right? your last two lines confuse me
Sorry! You are right! if it has a cycle, we should NOT add 1 to the answer :)
Thanks. Some beautiful problems and elegant solutions out there. :)
There is O(1) solution for problem E. http://www.codeforces.com/contest/659/submission/17067296 Can anyone explain me this.
It's not a real solution. It exploits the fact that many tests cases share the same solution and compares number of nodes, edges and first number in second line to identify the test case and print the solution accordingly.
You can easily hack it! ;)
Means it has weak test cases.
Not necessarily, however, if the problem statement asked to print unreachable nodes it would be way more easier to solve it properly
Please it would be really grateful if someone can explain editorial of Problem F.
You just need to launch dfs from all
i
andj
thatk % a[i][j] = 0 and k / a[i][j] <= n * m
. In dfs count values thatv >= a[i][j]
. if value equals to k / a[i][j] you could find answer.Thanks I got your point but if we launch dfs from each i and j for the mentioned condition, won't the complexity be O(n*m*(n*m)) in worst case? How to make it efficient?
You will mark every used points. You can see my solution here
Thanks lord, I didn't realized that the maximum distinct divisors we have to check is really small as n*m<=1e6
Problem G
please explain how S(r + 1) = S(r) × min(hr - 1 - 1, hr - 1, hr + 1 - 1) + min(hr - 1, hr + 1 - 1).
Problem E
why N — BPM getting WA?
Graph :
Edge 1 | Node1
Edge 2 | Node2
Edge 3 | Node3
ACed
Sorry, I am too late but in problem E, what about individual components with no roads why we have to add 1 as I was getting WA earlier but question states a city is separate only when it has no road leading into it and only leading out of it.
My hand at a more "human" explanation for problem G from someone bad at maths:
First, let's solve this task for constant h[i] (assuming each element of h is reduced by 1 from now on).
If we only consider the first plank, we can cut off any part of plank 0 from 1 to h[0]. The total answer for this plank is h[0] — dp[0] = h[0].
If we consider the second plank, we can either only cut off part of plank 1 from 1 to h[1], or do the same in addition to any possible cutoff ending at the previous plank (it's clear that no matter whether we cut off 1 or h[1], we still can cut off any part of h[0]). The answer for this plank is h[1]+h[1]*h[0], and the total answer is h[0]+h[1]+h[1]*h[0].
We can advance infinitely, storing the answer for the previous plank:
Now let's consider the case where h[i] is non-decreasing.
The start is obviously the same, but things change starting from the second plank.
If we want to cut h[1] but leave h[0] (and everything before) as-is, nothing changes for us, so h[i] is still part of dp[i].
But if we want to also cut off part of h[0] and h[0] < h[1], then we can only cut off any part of h[0] if we also cut h[1] to the same height as we will cut h[0]. For example, if h[0] = 3 and h[1] = 10, we can cut h[0] and h[1] to length 0, length 1 or length 2, but cutting h[1] to length 3 makes h[0] impossible to cut.
This means that in this case:
Finally, let's consider the hardest case — non-increasing sequences.
If we want to cut off h[0] alongside h[1] and h[0] > h[1], then we can only cut h[0] to the same or smaller height as h[1]. If h[0] = 10 and h[1] = 2, we can cut h[1] to 0 (in which case h[0] must be cut to 0 as well), or we can cut h[1] to 1 (in which case h[0] can be cut to either 0 or 1). In addition, all options that depend on h[0] being higher than h[1] are unreachable from h[1].
So in this case, only part of dp[i-1] must be used — instead of dp[i-1], use the same formula as before dp[i-1] but with changed height:
Or, to put it in a different way:
Still pretty convoluted, but hopefully a bit easier to understand. See 223426302