Note, that if the array has two intersecting continuous non-decreasing subsequence, they can be combined into one. Therefore, you can just pass the array from left to right. If the current subsequence can be continued using the i-th element, then we do it, otherwise we start a new one. The answer is the maximum subsequence of all the found ones.
Asymptotics — O(n).
At first we sort all friends in money ascending order. Now the answer is some array subsegment. Next, we use the method of two pointers for finding the required subsegment.
Asymptotics — O(n log n).
Let's go down the tree from the root, supporting additional parameter k — the number of vertices in a row met with cats. If k exceeds m, then leave. Then the answer is the number of leaves, which we were able to reach.
Asymptotics — O(n).
A two-dimensional DP will be used to solve the problem. The first dimention is the mask of already taken dishes, and the second — the number of the last taken dish. We will go through all the zero bits of the current mask for the transitions. We will try to put the one in them, and then update the answer for a new mask. The answer will consist of the answer of the old mask, a dish value, which conforms to the added bit and the rule, that can be used. The final answer is the maximum of all the values of DP, where mask contains exactly m ones.
Asymptotics — O(2n * n2).
At first, we calculate the hash for all line elements depending on their positions. That is, the hash of the number k, standing on the i-th position will be equal to gi * k, where g is the base of the hash. We construct the segment tree of sums, which support a group modification, for all hashes. Thus, we can perform queries for modification in O(log n). It remains to deal with the queries of the second type. Let us assume, that we want to process the query 2 l r d. Obviously, the substring from l to r have a d-period, if a substring from l + d to r is equal to substring from l to r - d. We can find out the sum of hashes at the subsegment with the help of the sums tree, so we can compare the two strings in O(log n).
Asymptotics — O(m log n).
Use __builtin_popcount(int) in C++ for counting non-zero bits instead of new function
I think you wanted to say l+d r and l r-d.But you forgot a case.
For example 12312312,123123 can be solved using that method because is periodic,but the part that remains (12 in our example) has to be compared to the prefix of the same length.
12312312 is periodic, because two bold parts are equal: 12312312 and 123 12312. Everything is OK.
Sorry, we had mistake. Thanks for your attentiveness! =)
In Problem B:
How the inner loop (inside the outer one which iterates from 0 to n) of the two pointers method affects the complexity.
Here's my solution :
http://codeforces.com/contest/580/submission/13175844
I thought it would give me TLE.
can anyone explain the complexity ?
In your loop, you don't reset st, so, st and i would be incremented at max. the size of array.
(None of them are re-initialized to zero)
Got it, thank you :)
m.Elbarbary Can you please explain it?
What is this "method of two pointers" ???
I think this link can help
Yes, I saw that. But, that link describes on 2 arrays. Here we have 1 array only...
The same concept :)
check this link
In E, isn't it possible that hashing will create collisions and hence give an incorrect result? If yes then hacking solutions in E will produce incorrect results for hacks that should be succesful.
Fortunately, nobody knew which mods and bases were used in authors solution :)
I know that the probability of error is small if we choose a good base and a good prime but that doesn't mean that we can ignore the probability that there were collisions in the authors solution as well right?
Actually it does. Lets do a little math. Assume that N = 105. There are (105)2 substrings of the input. Authors are probably using 32-bit integer to store the modulo, to make calculations easier assume that mod = 109, It means with a uniformly random distribution, for each 0 ≤ x < 109 there are 10 substrings where each of them has a hash value equal to x. For each query probability of collision is equal to
, because there are 109.102 ways to choose collision pair and (1010)2 ways to choose any two substring. It means for each query probability of having a correct answer is 1 - 10 - 9, which means probability of having correct answer for all test cases is (1 - 10 - 9)105.80 = 0.992.
It's up to you to worry about %0.7 probability of fail.
Thanks for the probabilistic insight, is really helpful :)
What about two primes? Like two bases and two mods.
My solution to problem B is giving TLE. SOLUTION
Here I have an index j which is run from the end and if the difference is within d then I do not check further for the subsegments of this segment.I do this for every i from 0 to n-1.I am not able to figure out why the TLE.
Your solution goes to O(n^2) because of the for loop in line no. 29.
Consider the following example: d = 5 5 15 25 35 45 55 65 75 This is the array of money values (values of n[i].m in your case). For i = 0, j starts at 7 and reduces till 0. For i = 1, j again starts at 7 and reduces till 1. And this continues for all the values of i.
For a general n, the complexity of this loop would be n + (n — 1) + (n -2) + .... This is O(n^2)
Can someone explain E in a little more details please? I've never used hashes before and I don't know how to pick the base — why does this work? I mean, there are 10^100000 possible serial numbers, and that's a lot more than possible values of hashes. So why don't we worry about that? How to estimate how good is our picked base?
Also I don't quite understand this segment tree. Seems pretty tough to implement. Is this some kind of modificated segment tree for updating range and querying sum on range? I never really knew how to implement it (only segment-point and point-segment variations), let alone modifications. How can we support this group modification for all hashes — just a little sketch, please? :)
For question D can some one explain how the answer is coming 37 for this test case?
5 5 5
3 3 3 3 3
3 4 6
4 1 2
1 5 7
5 2 4
2 3 5
Thanks!
1 5 2 3 4
Yeah i got it . Thanks by the way!
Can someone please explain the time complexity in question 580D? How is the time complexity O(2^n * n^2)? We are taking dp[(1<<18)][18], should it not be O(2^n * n) ?
inside the recursive function we do an O(n) loop over all dishes. so we have a table of size (1 << 18) * 18 with O(n) to fill each cell so overall the complexity is O(2^n * n^2)
Oh! I get it! Thank you.
Please, can someone help me understand what's the problem with my submission for 580A? =/
http://codeforces.com/contest/580/submission/13188909
That's convert your code.
as this question is very old(5 years) and i am not able to solve this question please can you help me with solving it just mention the states of dp and transitions...please
Which question are you talking about ?
if atual < ant but seq < longest, you should let seq equals 1. because it's a new sequence
Thank you! :D
Well, I believe that the std of problem E can be hacked.
Solutions are completely unreadable. Specially for the first two questions!
why im getting runntime error
include
include
include
using namespace std;
define f(i,n) for(i=0;i<n;i++)
typedef long long int ll; typedef vector v; typedef vector< vector > vv; typedef pair<int,int> p; typedef unsigned long long int ull; int main() { ll n;//number of friends ll d,i,j;//scale for poor ll m,s;//money and friendship of the each friend cin>>n; cin>>d;//friendship factor ull friend_temp=0,friends=0; vector < p > mp(n); for(i=0;i<n;i++) { cin>>m>>s; mp[i].first=m; mp[i].second=s; } sort(mp.begin(),mp.end()); for(i=0;i<n;i++) { friend_temp=0; for(j=i;mp[j].first<mp[i].first+d;j++) { friend_temp+=mp[j].second;
}
Put your code here or here and post only the link here
I am not able to understand logic for D. can anyone plz help me. thnx
Why memset and memcmp work in problem E? :s
because the final order is o(n * q / 32)
and it seems that (1e10 / 32) isn't big enough for cf servers ...
why WA in test 20 ?
http://ideone.com/76fCx6
This is your corrected code=)
Thanks a lot igdor99 :) i missed this case
Sorry Guys,
I would't have asked if I could have figured it out myself.
For question C I implemented a simple dfs algo but get WA for test case 26.
Any Ideas?
http://codeforces.com/contest/580/submission/13208683
Edit:ignore my previous comment
13212382
d[y] must be 1 before you do this d[y] + = d[child];
Can someone explain the solution for B in a little more details please?
After you sort them by money ascending order, if M[i]+d <= Mj, then M[i]+d <= M[j+1]. If person j has at least d units of money more than person i, then person j+1 too, so the answer will lie in a contiguous subsequence.
So you can use two pointers pi and pj. pi will point to the left-most person and pj to the right-most (starting both in 0 and incrementing pj). If at some moment M[pi]+d<=M[pj] (Person pj has at least d units of money more than person pi) then you will have to increment pi until M[pi]+d>M[pj]. The answer will be the segment with largest sum of friendship factor.
In this question, can we have multiple segments where the conditions given in the question are satisfied and then we have to choose the segment which has the largest sum of friendship factor???? I am not sure about the above statement, can you help??
chotto_matte_kudasai 's solution for E is very nice :)
I'm trying to solve problem E using Segment tree and String hash. My code gets WA29, outputs "NO" instead of "YES", and I fail to find what's wrong in it. Here is the code I submitted Elise-580E.
Could you help me?
Did You get it? I am also facing the same problem.
can someone pls explain me the logic of question no 580D.
UPD modulo and randomization helped.
Can anyone tell me what is wrong with test # 75 http://codeforces.com/contest/580/submission/13208727 http://codeforces.com/contest/580/submission/13229611 I even checked hashes bf http://codeforces.com/contest/580/submission/13229546 They are equal with all keys I tried. Thank you
Hi Infoshoc how did you resolve that problem? I have the same problem with that case 24274322
OK guys, I have been wondering for like 5 days now about problem D since I absolutely cannot grasp the idea of the solution the author implemented I will now explain my own idea :
Since it's a dp problem i first look for a subproblems ( optimal substructure )
The question I ask myself is which item is the next item I must pick for the current set and if I pick it should i include it as an item from the bonus satifisfaction collection or not thus I have 3 recursive calls -> 1 for the set without the item,1 if the item is included, and 1 if there's a bonus which I can get for the current item with combination with another item then I pick it for the second recursive call.
Thus it should be something like this :
answer = max(recursive(totalSum,nextIndex),recursive(totalSum + value[currentIndex],nextIndex),foreach i recursive(totalSum + in dp[currentIndex][i]) then mark the visited items by passing an array of visited items to recursive calls.
Does this algorithm seem correct to you as it seems to me? If yes how do you do it bottom up? I have trouble transforming this to two dimensional bottom up approach.
I haven't read your solution but let me explain you in simple language what the author's solution is.
So he iterates over all the 2^n possibilities (using i=1 to 2^n). Out of them he chooses only those i which have exactly m bits on. Each bit represents the index of the element of the original array. Now that you have the 'i' that have exactly m bits on, you get to the algorithm.
/// algorithm lets say m=3 so you might have a 'i' as '1101' (0th index as the rightmost). Now lets say I pick the 0th index as my last dish and I add it's taste index to my answer. Now the remaining set of dishes remains as 1100,
NOTE: the 0th index has turned to 0 from 1.
Now to my function I will pass the new mask(1100) and the last dish index (0). So while following the same procedure for the rest of the dishes it will add the relation value ( tab[mask][last] ) to the answer. Hope it helps. For better understanding, refer my code
Could someone give me some links about hash functions? I've studied it in class but superficially. We talked about hash functions in an abstract mode (i.e. we suppose that f is a good hash function without specifying the body, we only saw the basic hash functions such as f(x)=x%m) without seeing nothing about base of the hash or how to merge two hashes into another (in order to make the sum tree). So in contests i don't know how to approach it in order to make a good hash function or how to manipulate it. Thanks in advance!
http://codeforces.com/contest/580/submission/13820453 I keep getting TLE at test 10 for A. What's wrong?
http://codeforces.com/contest/580/submission/13820822 Shortened the code, only one loop but still TLE at test 10, this is mad.
Change array size to 100000 from 10000. AC :)
Oh wow, thanks a lot. Can't believe it was this.
Hi.. In problem C, if the question was to get number of distinct WAYS to get to restaurants in the leaf nodes while crossing at most m cats, what would be the approach to solve that?
Thanks
why it is giving wrong answer in kefa and company problem i can not understand
include <bits/stdc++.h>
using namespace std; struct data{ long long int m; long long int n; }; bool comp(data A,data B){ return A.m<B.m; } int main() {
long long int i,j=0,a,b,sum=0,maxi=0; struct data hotel[100000];
}
What is the dp solution of 580A?
it couldn't be solve with recursive method use only one loop and check at the end for the maximum value here is my solution http://codeforces.com/contest/580/submission/22301569
I am getting WA for C, but cannot figure out what's wrong. Can anyone give me a test case to check my solution
I know I am late, but this is a serious issue. Here is my code for 580A:
http://codeforces.com/contest/580/submission/22831784
The solution gives correct output on ideone (https://ideone.com/UVSpRe), but here the output is not same. Even in Custom Test the output showing is wrong. Please help!
I know this is an old post but you should never do this
Arrays must have fixed size. Or else different compilers will react differently.
Hi Can anyone help me with D.Kefa and Dishes. I have used top-down dp but my solution is giving TLE. I think I have followed the same process as in the editorial with same time complexity. Thanks in advance. My solution:
Please help how you can visit only 6-7 resturant's on the leafs only and the answer is 3 for the problem "Kefa and the Park" don't get it really
Sorry i mean the answer is 2 but there is only 1 leave and its not red...
consecutive
Why there is runtime error on test 27 of 580C using python? http://codeforces.com/problemset/submission/580/54878038
In solution of problem A, We have never assigned any value to and in for loop we are writting o=max(o,k). How can we do that please help.
Kefa and Park
For the above question, when I am trying to submit my code using JAVA . I am encountering TLE.
I wanted to know if all the languages have same timeout set? or is there any multiplier that is being used specific to high level languages?
Cause Java I/O processing is relatively slower than c, c++. I tried using Scanner as well as BufferedReader but encountered same issue!
Hi, I think this is a late reply, but why don't you check how other Java submissions are?
BFS solution for C (Kefa and Park): https://codeforces.com/contest/580/submission/77761479
DFS solution for C(Kefa and Park): https://codeforces.com/contest/580/submission/88595959
can you ples check why it is showing WA . I am not able to find my mistake https://codeforces.com/contest/580/submission/103030572 103030572 i would be very thankful to you
I think, I didn't understand 580B - Kefa and Company . I thought the answer is the sum of friend factors for those who have less money than d, but I got wrong answer by 83266145. Can someone help me explaining what the problem is saying or what the answer should be?
How to solve B using binary search? why it is in binary search tag. I've solved it using two pointers method but dunno how to solve it using binary search.
Update: Finally i got the idea. here is my solution. I have a spaghetti template you will find the solution in the Solution function. Here is my code — 89585819
Complexity — $$$O(nlogn)$$$
Why does my recursion solution for 580A always fail at test#20? https://codeforces.com/contest/580/submission/121256298
[Update] solved: https://codeforces.com/contest/580/submission/121262296
In problem C, test case #3 is >
so m = 2, n = 3 and each node has a cat.
each node has a cat so the ans should be 2 and not 0, because if we go from 1 -> 2 or 1 -> 3 then the number of consecutive cats encountered = 2 which is not more than m = 2.
Why is this wrong?
I think tree looks like this: 1 -> 2 -> 3