Hi!
I'm glad to invite you to Codeforces Round #526, which will be held on Dec/10/2018 19:35 (Moscow time). The round will be rated for both divisions.
Problems were prepared by me, TheWayISteppedOutTheCar, xoxo, Egor.Lifar.
Thanks to ismagilov.code, Kuyan, 300iq, alexey_kuldoshin, Jatana for testing, arsijo and vintage_Vlad_Makeev for helping us and MikeMirzayanov for the great Codeforces and Polygon platforms.
You will be given 6 problems in each division and 2 hours to solve them.
UPD:
The scoring distribution in Div. 1: 500-1000-1500-2000-2000-2500
The scoring distribution in Div. 2: 500-1000-1500-1750-2250-2750
UPD: Congratulations to winners!
Div. 1:
Div. 2:
UPD: Editorial
I think the date is wrong
Fixed
I am confused.
so I decided that I do the contest and I did.
batman taught you a good lesson :P
Aww, new codeforces round, new chance to fall!
Reverse psychology — Activated!
I am very interested in knowing what vintage_Vlad_Makeev is planning to do??XDD
You missed this I guess :)
Heisenberg dude what I meant was that I was curious to know what vintage_Vlad_Makeev was planning to do with his rating! See his graph he is trying something out! Maybe he wants to visit all colors or maybe something else!!XD
He helped in creating the problems so can't participate.
He is trying to look like Bitcoin :)
I asked him. He didn't reply :/
Time is always a severe problem for us Chinese fanatic.
yes!Next regular time is 9:45pm, I think this is ok,but too far.
Sounds like u have long awaited for that aha
oh!There will be no class tomorrow morning，I am ready gang tonight,after i'm ready the first question,the registration channel is closed.
I'm not sure i will join this contest,so I haven't register advance!!! no, the The prophecy is coming true.（唉！真的要等到23号才能打）
“Is this rated?” hURr DuRR
Yes，it is
Nah mate, you’re wrong
f
i hope that problems will be graduated in terms of difficulty ^^
yey i cant wait for all of you to lose rating! :D
2300
:((
Again a new chance to restart coding...
does cf stops producing 5 problem Div2.s ?
Wish for 2400.
how many problems are shared between the divisions ?
3 problems
thkns!
Yes I wont lose rating
Div2A was such broken english that I couldn't comprehend the problem statement. After reading the statement multiple times I reached an understanding which was in conflict with pretest 1 answer. I submitted a question and nobody answered it. So I guess I'm just gonna skip this round then.
Please don't google-translate russian problems into english. If you can't write english problem statements, ask help from someone who speaks english. If you can't explain a simple problem (such as div2A level) in an understandable way, please don't write problem statements at all.
I was confused by Div1A not mentioning that you can choose u,v freely and talking about 'the city u/v' and 'the path' (not a city/path).
So I asked 'what are u,v, they are not in the input' — answer: 'Yes'
Problem statement in russian was very unclear too — I doubt we should blame google-translate here.
How can i register now?
yeah, difficult to understand
RIP problem statements
Lol. C was harder than D and E. How to solve C?
Use a segment tree to quickly calculate, for any segment [l, r], if there is a path that contains all values in [l, r].
Each node should store a pair representing a path, but combining pairs requires a lot of casework and isn't fun :(
Nice.
Actually restrictions were rather kind, so something like checking for all pairs of endpoints of two paths that all other endpoints lie on a path between them still passes. So you could do it without any casework.
What does this comment has to do with problem C?...
The l and r are the interval of node i in the DFS traversal of the tree. So we can store the l[p - 1[i]] in a max segment tree, and the r[p - 1[i]] in a min segment tree, then all values 0, 1, ..., K lie on an ascending path iff ltree.query(0, K) < rtree.query(0, K).
EDIT: I was working on this at the end of the contest but there was too much casework glueing together two paths and my code was a mess so now I only got problem B, RIP :(
How to solve DIV1B?
for each prefix, calculate the maximum string you can make, then add it to the answer.
The characters being 'a', 'b' allows for a pretty easy solution that is barely programming. You can consider s and t as binary strings and iterate through their prefixes. While the prefix difference is less than k, you add it to the sum and when it grows larger you add k instead.
→ Reply
Was the intended solution to E convex hull trick? If so why is it after C and D in the list? :Dd
can someone explain div 2 C problem and its solution?
We have to find the no. of index sequences where in which all the string elements at those indexes are equal to 'a' and between every two adjacent indices there must be atleast one 'b'.
So, we divide the string into pieces, where each piece contains those "a's" which are preceded by same no. of "b's". e.g. : "aabaabbaaabab: is divided into "aab" "aabb" "aaab" "ab".
Now, from each piece, we have the choice of taking either 0, 1, 2... till count of "a's" in that piece. So, total "count of a's in that piece + 1" choices.
Now, to find the total required sequences, we multiply the no. of choices from each piece. But, since we want to choose a non-empty sequence, we subtract 1.
Sorry I'm facing problem yet to understand the problem. Help me please:
For the example you given, "aabaabbaaabab,
[0], [1], [0][1]are also valid sequence. Right? But, how do they satisfy the condition that there must have at least onebbetween two adjacent indices?[0, 1] is not a valid sequence as the first two a's don't have any 'b' in between.
Why [0], [1] are valid?
Yes, 0 and 1 as two different sequences are valid as they contain only one 'a'.
I failed to relate this with given conditions of the problem please help me to do so.
Okay,
The problem statement says to find the no. of strictly increasing sequences p1, p2, ..., pk such that:
This means value of string at all these indices of sequence must be 'a'.
This means, for any two consecutive elements of sequence, there must be a 'b' in between those two indices of the string.
Please let me know if you get it now.
:( not yet.
if the given string be aaa, then second condition can never be met by any sequence. Then?
Yes, but then all the sequences will be of the same size, to meet both the conditions.
So, required sequences are: [0], [1], [2].
But this is not mentioned in no where in the problem :(.
It's called vacuous truth. https://en.m.wikipedia.org/wiki/Vacuous_truth
If the sequence is of length 1, then there's nothing to check regarding the second condition. So you can consider that it meets the requirement.
The two given conditions should be met at a time or else?
Yes, both the condition should be met at the same time.
Problem — Count number of subsequences of the string which consists of only a's and every two a's should have at least one 'b' between them in the original string.
Solution — Pretty standard approach. Iterate over the string. Maintain a counter. When you get an 'a' increment the counter. When you get a 'b' multiply the counter to answer and set counter to 0. Do not forget to multiply the counter again for trailing a's.
It's a classic dynamic programming problem. The first thing is that you should save the position of 'a' beforehand. Okay, so f[i] is the way to choose the array with the positions of all elements are not greater than the position of ith 'a'.
f[i] = f[i-1]; f[i] += 1 (Should take care of the case that the array contains only one 'a'). Now if we choose ith 'a', we should find the previous proper 'a' that has the largest index, which means that between that 'a' and the ith 'a' contains a least on 'b'. This can be done by binary search. The overall complexity of this sol is O(nlogn)
That feeling when you spent nearly 1h to think about 1A but finally realized that the condition that one should have enough gas to pass through a road is useless.
Well, you also may consider it and honestly push maximum possible sums in two dfs, one for pushing them to the root and another one for pushing them from the root.
Lol. I solved it in this way, though couldn't debug it within time.
AC submission
But how to ensure that both the paths do not come from the same child?
You should keep maximum and second maximum pathes.
What? How?
can you please elaborate why that condition is useless?
Because that condition will always get satisfied,when you take two maximum sums among its child.
Because if for any path, at some edge the condition isn't satisfied, then by erasing the path from the starting vertex to that will yield a path with a better result. Thus we only need to find the maximum answer without considering the condition, that is, the optimal answer we find in this way must satisfy the condition.
Here's a little more elaborate proof that I wrote.
how to solve C without seg tree??
https://www.geeksforgeeks.org/sum-products-possible-subsets/
Div2D test 7 anyone please?
Check this case:
The right answer here is 205.
My program got 205, still failing pretest 7?
Me too
early system testing nice ^^
For div1E, is it enough to use long double?
why you used double dude? i am sure there is no fraction needed
I used convex hull. To determine if a point is to be deleted, I needed a check which could go like till 10^27.Well, I used an int128 library for this check.
C and F were very good problems! (Too bad I didn't solve any of them :(.)
Why are constraints so tight in E? My solution worked 1840ms/2000ms on pretests (I don't know if it will pass, although I'm 100% sure idea is fully correct) and it had 64-bit integer overflow issues. So why did you do so? Am I obliged to prepare very fast CHT beforehand to pass on this problem?
Maybe they wanted to block O(nlogn) CHT. But it is poor because there is a sort involved already.
It seems neither possible nor reasonable in such constraints...
This is so sad that someone didn't prove it but got acc and you didn't prove it too but you didn't get acc :(((
Wtf are you talking about?.. I got AC. My complaint is that solution works in 1918ms which is very close to TL and constraints are very tight without any proper reason.
Sorry wrong reply, i wanted to replay another comment.
Maybe they were overly paranoid of n2 dp?
You wrote the blog about li chao tree, so I'm surprised you don't have a fast CHT implementation :O
I used implementation from my article, it didn't turn out to be very fast, haha.
Although I used offline version because thought that Li Chao would use
memory.
it wouldn't
why overflow? isn't the answer always within long long?
Update: sorry my implementation is probably different from yours.
can someone please share their approach to Div2 D ?
DFS, where each node returns the best path in its subtree that ends at this node. Do this while maximizing the answer among the sum of best 2 children of each node with each other, i.e sum the paths returned from the best 2 children and check if they're better than your answer, they resemble the best path passing through this node, also try taking the best path alone, or just the gas of the current node.
dp on tree.
first, make the tree rooted. dp[u] = maximum gasoline that can be starting from u and ending to node that have u as its ancestor
for each node, you can find the maximum of the path passing that node by finding the best two children of that node.
what about the constraint on the minimum amount of gas to cross a path?
nah. doesn't need it. they ask you to maximize the minimum gasoline that can be achieved. not the minimum gasoline spent
Centroid decomposition — force the centroid to have a depth of 0, and find depths of subtree accordingly (add weights, subtract lengths of edges).
Then add in the w[centroid] when considering the answer.
Unfortunately,
I put for (auto e : arr) ARR.insert(e); in the wrong layer of looping causing it to do nothing at all! :(
First notice that an edge and a vertex only comes into the picture along with some other vertex when w(vertex)-w(edge) is positive. In this case it will only increase the gasoline upon reaching some vertex. You need to maximize this.
The way to do it is calculate (in) value for the vertex which denotes answer if you start with this vertex and travel down...Also calculate (out) for each vertex which denotes max answer you can get starting from the node and not traversing the children of it.
As wewark says keep 2 best children for it to do it in linear time.
It is the in-out dp trick. Sad it is for I wasn't able to complete its implementation on time.
Below is the link to its video tutorial. https://www.youtube.com/watch?v=Xng1Od_v6Ug
Last week I was mocking .ckodser. for using "ll" no matter what , even as a loop variable. And today I got two wrong answers in the whole contest , both due to the above issue :|. Guess that's the universe slapping in my face ... :O
Please give proper respect to the power of #define int long long xD
Amen to that. It takes away a layer of worry.
I don't want to make int128 library only for codeforces(why codeforces working on 32bit????)
Can we solve DIV2 D using in-out dp ? for every node , taking max value in inside subtree and max from outside subtree , and now curnodeval+max(inside_value,outside_value) ! we will check this for every node and taking out max of all ! P.S : value in a subtree is sum of values of nodes — sum of values of edges !
Fast judging, pretty good.
And btw, apart from C and F being good problems which I mentioned before, there were a few annoying things. I see that TLE in C was pretty tight (I currently see 1 AC and 2 TLEs on 100/112 tests among my friends) and it seems TL in E pretty strict as well and in E we needed to check whether ab>=cd where these products could be as large as 1027. Why weren't the constraints lower so that it could fit in LL? It took me something like 5-10 minutes to solve this problem and code it apart from doing this check which took me 26 minutes xDDD. CF doesn't have int128 (ノಠ益ಠ)ノ彡┻━┻, long doubles are shaky and all other ways are troublesome and require a lot of care.
Wait where did E require that check? I didn't have it and got AC
Depends on implementation, I guess. Check is needed if you reduce CHT to convex hull of points.
I didn't write this code myself but 46872251 uses the CHT and doesn't seem to produce overflows. Source: kactl
I just copied not mine code for convex hull (which is great btw) and it had such check. Many people here talk about it (yosupo and comfi) and Radewoosh had this problem as well, so this problem definitely exists and I'm not the only one. Maybe you used some other idea.
In my code 46871036 that is line "return (x->b — y->b) * (z->m — y->m) >= (y->b — z->b) * (y->m — x->m);" which is commented and replaced with ugly functions Wrap and Gr
I got AC using long double to do that 10^27 multiplication part (in practice submission). Maybe weak testcases?
I am not surprised by fact that it gets AC, but it may be risky. It may be hard to create testcases against this. You can't be sure.
You can use __float128 instead of __int128, as it has enough bits of mantissa precision to store integer numbers of order ≈ 1033 exactly and exists on the Codeforces.
Also I dont see any point in characters in B being 'a', 'b' instead of 'a' to 'z'.
The characters being 'a', 'b' allows for a pretty easy solution that is barely programming. You can consider s and t as binary strings and iterate through their prefixes. While the prefix difference is less than k, you add it to the sum and when it grows larger you add k instead.
Of course, this solution could be adapted to a larger alphabet, but it only serves to make the implementation difficult.
In my solution it would only the matter of replacing 2 with 26 and b with z...
OMG YOUR CODE IS INGENIOUS
But in your description you missed most important part — why you can don't care about overflows here which is why it is so clean and ingenious.
Thanks :D
Still managed to fakesolve Div2B, though. Yes, to avoid overflows you just notice that k is not large enough to overflow and that you stop updating the difference after a certain point.
I don't understand how does your program survives a possible case where both strings are
bbbbbb...andbbbbb..Your variablesaandbwill for sure overflow because the difference will be 0 at all times. Weird. Maybe weak tests, or maybe I'm missing out on some bit logic.Notice that even if the variables overflow, they will do so to the same value.
Couple this with the fact that the variables will only overflow when they are equal, and notice that this means that even cases such as
bbbbbbb...ba bbbbbbb...bb
will work due to the difference remaining accurate through overflow.
Another curiosity is that dues to multiplying by two being equivalent to a left-shift it "overflows" to - 1 when it multiplies to the sign bit and after that point it will not overflow again if the strings of b-s continues due to 2 * ( - 1) + 1 = - 1.
How about Div 2 C?
it's hard for me to explain but I can give the hint to forget about all characters that are not 'a' and 'b', and count number of adjacent 'a's and store it in vector. Then find formula for it. Check my submission for maybe more info about formula.
I also used the same approach as yours. Some coders used dp. I didn't get that. I also got AC though
It's simple combinatorics.
You need to have atleast a 'b' if you consider more than 1 'a's of the sequence. So, what you can do is count 'a's in each segments seperated by a 'b'. Now, suppose for some segment you have x a's. So, you have x+1 choices(select 0, 1, ...x) to select 'a'. Multiply each segment's (x+1) values. Now, you need to subtract 1 as you need to have a subsequence of length atleast 1.
hey i used a dp approach: consider there are x continuous segments of b's in the string which divide the string in (x+1) parts. Let the no of a's in the (x+1) segments be a1,a2,......a(x+1). Then DP[i]=(a[i]+a[i]*DP[i-1]+DP[i-1])%Mod, DP[i]->no of ways considering first i 'a' segments. Base case: DP[1]=a1 and final answer would be DP[x+1]. Also you would need to check separately when the string would contain no 'a' or no 'b'.
Div1A, statement "Nut can't choose a path, which consists of roads, where he runs out of gasoline" does not affect the answer? Interesting.
That's pretty easy to see since if you would have negative amount of gasoline after some prefix, you can just disregard this prefix and get strictly better answer.
Cheaters 46874750 46876196 ,I suppose that you will not do anything as always MikeMirzayanov ?
KAN MikeMirzayanov cookiedoth
You better have developed plagiarism checker. Check some codes and they are almost the same. No doubts most of them are copied from sites like "ideone". For example, two same submissions:
https://mirror.codeforces.com/contest/1084/submission/46875019
https://mirror.codeforces.com/contest/1084/submission/46876091
Huh, it took me approximately 5 years and 5 months (since the first c++ code), but this moment is worth it, even if it's just a moment :P
Seeing your performance in recent contests I don't think it's going to be just a moment, congratulations!
I sobered up after the holidays XD
But that won't last long. The sober part, not top1.
Yeah I think tourist has a script that registers him automatically to the next contest if he is not in the first place anymore,..
2 sysfails today :( but at least i got a christmas candy cane :)
Congratulations Radewoosh.Number 1 on both rating and contribution.
This Code of Problem B: while (sum < s){ sum += n; num[0]--; } I check is case: 1 999999999 1000000000 It's running for 2000ms on my computer,But gets an Accept in system test....
Can anyone provide a proof why this 2B passes??
Tried around 10-15 tc but It didn't fail.
((i-x)+(i-1)+(x-1))*2. So x cancels out. Similarly when x> i.
For x>i, i cancels out. So this proof is wrong.
P.S. — This soln is correct because x=1 is among optimal solutions.
sorry..my bad.
E was solvable in 10-15lines with just sorting+deque without cht.46878899
Thank you, Good contest, Great problems, Nice pretests.
can anyone explain me div 2 c with example
Ways to choose some subsequence(not necessarily continues) of ‘a’ that between 2 element of this subsequnce there exist a ‘b’
can u explain with an example by telling subsequence ?
aaaaggbbaaadddaa The subsequences of length 1 are every a = 9 The subsequences of length 2 are pair of 4 first ‘a’s and 5 other ‘a’s becuase there has to be a ‘b’ between every two ‘a’s that we choose so = 4 * 5 = 20
Solution: all you have to do is have the number of ways you can do this before the last b then for every a till next b answer is that sum + 1
in aaabbaaaabbbaa the answer should be 9+3*4+3*2+4*2?
Its 9 + 3 * 4 + 4 * 2 + 3 * 2 + 3 * 4 * 2
are u sure ?
Lets count Length of 1 = 9 Length of 2 there could be from first pack of a and second then second and third and first and third Length of 3 is choosing one from each pack
Ps. Its like 12:40 am so Im going to sleep bye
But Pi and Pi+1 are subsequences, so what does Pi < j < Pi+1 means?
No pi isnt the subsequence its index’s pf subsequence
Thank you, but why do you think so? I see this: The Nut is a curious guy, so he wants to find the number of strictly increasing sequences p1,p2,…,pk, such that: 1... 2...
Please, get me right — I'm not trying to be a jerk, and prove that I'm right and you are wrong — I'm just looking for clues, to understand it right next time.
I mean non of n-a-sequences ("aa...aa" n times) is strictly increasing and k is the number of this sequences, not number of "a"s...
K is the length of sequence it can be from 1 to n
Div2E states:
Recently, the Fair Nut has written k strings of length n, consisting of letters "a" and "b". He calculated c — the number of strings that are prefixes of at least one of the written strings.
So he calculates all the possible strings that would be prefixes? Not only those k of length n, that where written?
Can someone give me some links where I can learn about convex hull opt? The old ones that are on codeforces blog's does not work.
Don't know what happened to PEGWIKI, but I recently learned it from it.
You can check this: https://web.archive.org/web/20170609092958/https://wcipeg.com/wiki/Convex_hull_trick/
And for Li Chao Tree (slope/queries are not in monotonic order) refer to: https://cp-algorithms.com/geometry/convex_hull_trick.html
If you want to avoid using std::complex refer to my implementation of Li Chao: https://pastebin.com/fLcs75A9
.
try using long long instead of all ints. it may answer.
Hi I got accepted in problem B(div.2); but there's a test case that is not in your tests, but I will get TLE on it. The test case is this: 1000 10^12-1 10^9 10^9 10^9 .... please add this TC and rejudge
46902714
Guys, what is needed to solve Div2 Problem D? I know DFS but I am not able to understand the approach to be used for this problem. For me, the editorial above is providing no clue/ help. Can someone help me with some explanation on this problem?
Thank you.
Think of it like this : You need to search for a path. So, for each node, you consider its subtree. Now 2 cases : a) You need to find the best one-ending path. That is, find the best path that starts somewhere in the subtree and ends in this particular node. This is the path that can be extended by the ancestor node. So, you need to store it in the DP state. b) You need to find the best possible path in this subtree. Also, it should pass through this particular node. The path in a) is one of them. The others can be found if we combine the best paths from the 2 of the children subtrees. Which we can do by sorting the children DP states.
how is Radewoosh pronounced?
is it like Raydwoosh or Ra-De-woosh?
/ˈraˈdɛ.uʂ/ (the second)
.