### hloya_ygrt's blog

By hloya_ygrt, history, 3 years ago, translation, Hint
Tutorial

811B - Vladik and Complicated Book

Hint
Tutorial

Challenge. Can you solve the problem with n, m ≤ 106?

811C - Vladik and Memorable Trip

Hint 1
Hint 2
Tutorial

Challenge. Can you solve the problem with n, a[i] ≤ 105? Try to use the fact, that .

811D - Vladik and Favorite Game

Hint 1
Hint 2
Tutorial

Challenge. Assume this problem: let's change all dangerous cells on walls, i.e such cells, in which it is just impossible to enter. Now you have to generate such string from moves 'L', 'R', 'U', 'D', that without dependance on possible button breakage of pairs 'L'/'R' and 'U'/'D', as in original problem, will visit finish cell. Of course, it is not necessary to stop at finish cell, you just have to visit it at least once.

811E - Vladik and Entertaining Flags

Hint
Tutorial Tutorial of Codeforces Round #416 (Div. 2) Comments (66)
 » Challenge. In problem A can U solve if a , b <= 10 ^ 18 ? hinttry to use binary search :DD
•  » » Can be done in SpoilerO(1)! It'd be awesome if someone finds out a hack case for this. 27416204
•  » » » The hacking test is443672224612562498 443672223946475251Answer: Vladik (you can easily check this with a slow solution).Doubles often fail by precision, it's not recommended to use this. Casting everything to long double or avoiding doubles would help.
•  » » » » My answer is correct even for that "hacking test", it is below this comment.
•  » » » » » Ok... How about this test?286539999388964720 286539998853670410Answer is also Vladik.You solution prints Valera (I tried custom invocation).By the way, the generator is Generator#include #include #include using namespace std; using namespace chrono; mt19937 rnd(system_clock().now().time_since_epoch().count()); int main() { int64_t x = rnd() % (int)9e8 + 1; int64_t a = (x+1) * (x+1) - 2 + rnd() % 5; int64_t b = x * x + x - 2 + rnd() % 5; cout << a << " " << b << endl; return 0; } Try to stress test your solution with this generator and see your code also fails by precision.
 » Problem A is O(1). Here is my answer.
•  » » 3 years ago, # ^ | ← Rev. 2 →   sqrt function is O(1) ? how is that possible?What is order of sqrt in c++?
 » 3 years ago, # | ← Rev. 2 →   May you please find a mistake behind a logic of my approach for problem C : 27416588
•  » » 3 years ago, # ^ | ← Rev. 2 →   Oh, sorry, there is no question anymore, i found out a mistake, here is AC solution : 27416622
 » In probelm E，the tutorial is too short to understand,could anybody give more details about how it be solved? Thx :)
•  » » 3 years ago, # ^ | ← Rev. 2 →   Let's say we have two segments A and B with endpoints [LA, RA] and [LB, RB] and LB = RA + 1. Let's also suppose we have three informations for each one of these segments: 1) how many connected components are there in it; 2) in which component every one of the n elements of the column Li is; 3) in which component every one of the n elements of the column Ri is.Now, we may want to know these three informations for the segment C, which has endpoints [LC = LA, RC = RB]; i.e., C is the merge of the segments A and B. If we are able to do this merge correctly, then we can build a segment tree such that each node stores the three said informations for its range and thus get the correct information for any given range via the query function.The segment C will have compA + compB - unionsAB connected components, where compi stands for how many components are there in segment i and unionsij for the number of unions made when merging segments i and j. For each line i of the n lines, we gotta union the components of the columns RA and LB if grid[i][RA] = grid[i][LB] and update LC and RC if some change occurred in the components of the elements in these columns.
•  » » » Very nicely explained, thanks! I can see how to implement this solution using Segment Trees. The editorial, however, mentions Interval Trees, which I've never worked with before. Are these interchangeable words for the same data structure?
•  » » » » I don't know what a Interval Tree is, but this page says that it is a data structure similar to Segment Tree, so probably they are not the same.
•  » » » Quite clear,thanks for you help! :)
•  » » » When merging intervals A and B, wouldn't it be necessary to use DSU/union-find data structure? I think you would need a DSU per node in the segment tree. But then you would face the problem of merging DSU's, both for building the segment tree and for answering queries, which will yield TLE considering that there are q = 10^5 queries to answer. How can you solve that?
•  » » » » Take a look at this code. We can just naively merge two nodes in O(n2). Maybe a DSU approach would be even faster. I'm kinda lazy to do the maths right now but it should pass...
 » Explanations in the editorial are shorter than the corresponding problem statements
 » 3 years ago, # | ← Rev. 3 →   Another way to solve A:We know that, Sum of first n odd numbers = n*n and sum of first n even numbers = n*(n+1).Notice that Vladik always gives odd number of candies and Valera always gives odd number of candies.If Vladik can gift n times, then n*n should be at least a, so, n = floor(sqrt(a)) . Notice that Vladik can't give right amount, if Valera can give gift at least same number of times, i.e. n times.Now, to gift n times with even numbers, Valera needs n*(n+1) candies. If Valera has at least n*(n+1) candies, then he can gift n times, and then Vladik is first who can't give right amount of gifts. Code:int a, b, n; cin>>a>>b; n = sqrt(a); if(b>=n*(n+1)) cout << "Vladik\n"; else cout << "Valera\n"; 
 » Problem B for n, m ≤ 106 can be solved with AVL, there are another way for solve it?
•  » » You can solve it with merge sort tree and binary search too.CodeMerge — sort tree Tutorial
•  » » » Thanks!!!
•  » » » Challenge: Solve each query in O(log n) time complexity. With Merge Sort Tree is it O(log2 n), in strict TL that will Time Out too :P
•  » » » » Like I said, AVL, it solve each query in , so with AVL, insertion time is and total query time is . Do you have in mind another data structure?, I don't know any other.
•  » » » Isn't your code a segment tree that works O(log^2(n)) for a query?
•  » » » » https://discuss.codechef.com/questions/94448/merge-sort-tree-tutorialSegment tre with Vectors AKA Merge Sort Tree has a query with complexity logn * logn (read in link above).
•  » » 3 years ago, # ^ | ← Rev. 2 →   I solved B using, SQRT decomposition.My submission: 27381506Update: Previously, by mistake, I had given my submission link for A. Now fixed it. I didn't notice it earlier. Sorry for that..
•  » » » That's not the answer for problem B, that's the answer for problem A!
•  » » I did it using Segment tree.
 » The time of problem B is O(n·m)???For this problem n, m ≤ 104 so if n = m = 104 then the time would be , that runs on 2 seconds???
•  » » Rule of thumb :- On every major platform O(108) runs in about 1 sec. Except on Codechef, where sometimes it gets TLEd
•  » » » Thanks!!!, I didn't know that. I was thinking that 106 or at most 107 runs in 1 second.
•  » » » How can I know what's the maximum number of operations that runs in 1 second in any platform???
•  » » » » http://codeforces.com/contest/811/customtestJust try code with simple operations with different n
•  » » » so... what about this submission ? 26864037 It is complexity O(10 ^ 9) but get accept in 15 ms !!!
•  » » » » It's about -O2 magic. You can try a code with a 10^18 iterations on your computer and it will run in 0 sec.
•  » » » » » Wow! Why does that happen?
•  » » » » » » The compilers are really clever now.
 » Can someone explain C in more detail, did not understand the dp part
 » 3 years ago, # | ← Rev. 2 →   you can solve problem A in O(1)by using this formula Sn = n/2 *(2*a+(n-1)*d)n number of terms , a = the first element of series "1 for Vladik and 2 for Valera" , d= increment = 2so the formula for count the number of term forVladik = n/2 * (2*1+(n-1)*2) = n(1+n-1) = n^2 = a so na = sqrt(a)Valera = n/2 * (2*2+(n-1)*2) = n(2+n-1) = n^2+n = b so n^2+n -b =0 and solve it by quadratic equation nb = ( -1 + sqrt(1 + b*4) ) / 2if (na <= nb) "Vladik" else "Valera"
•  » » sqrt function isnt working in O(1)
 » For the challenge of D part . I have an idea with string of size atmost 4*n*m.The idea is first just generate the string from start to final assuming all buttons are correct.Lets call s1.Now assume (L/R) is reversed and simulate s1 from start to see which position it reaches.from that position generate a string which reaches final from it assuming broken (L/R) . Lets call this S.Now concatenate s2=s1+S.Now assume (U/D) is reversed and simulate s2 from start to see which position it reaches.from that position generate a string which reaches final from it assuming broken (U/D) . Lets call this S.Now concatenate s3=s2+S.Now assume (L/R) & (U/D) is reversed and simulate s3 from start to see which position it reaches.from that position generate a string which reaches final from it assuming broken (L/R) && (U/D) . Lets call this S.Now concatenate s4=s3+S.Now it must be visible that s4 passes through final for any possible breakings.Can someone find a flaw in this??
•  » » Yes, my idea was the same :)
 » problem A can be solved in 0(1). http://codeforces.com/contest/811/submission/27385965
 » A better solution for Problem A (Div 2) would be off O(1). Just solve quadratic equations for sum of two different APs. 1) For Vladik, AP would be of type 1, 3, 5, .... 2) For Valera, AP would be of type 2, 4, 6 .....Get the number of elements in each AP which sums upto required number of candies and compare. :)
 » Can someone explain C in more detail?
 » How to solve the challenge problem for problem C
 » Pretest of problem B is weak like a sh**! I want to **** this contest
•  » » @pkien hacked my computer lol
 » 3 years ago, # | ← Rev. 2 →   Is it possible to solve E using SQRT-decomposition? I mean something like this (but I missed that spots can be splitted, so it is wrong anyway).
•  » » I think it's a bit too slow, O(N*M^(1.5)) is about 1e8, while the compiler could barely optimize the complex code.
•  » » » 3*10^8 to be accurate. I think it can suits in 2 seconds.
 » What is the meaning of this line , can anybody explain?Assume, that there was such train carriage, that finished at position i. Then iterate it's start from right to left, also maintaining maximal ls, minimal fr and xor of distinct codes cur. If current range [j, i] is ok for forming the train carriage, update dpi with value dpj - 1 + cur.
 » So how to solve C for n, a[i] ≤ 10^5 ?
 » A lot of people (including myself) found the explanation for problem C hard to understand, so I thought I'd explain my solution. SolutionJust like the official solution, we note down for each number its first and last occurrence. Codefor (int i = 0; i < n; ++i) en[a[i]] = i; for (int i = n-1; i >= 0; --i) start[a[i]] = i; Then we create an array dp, where dp_i will hold the solution to the problem, assuming we were only given i passengers to begin with. This means that dp = 0, and then we iterate over the passenger list, for each passenger checking is this element the last of its kind? if so, we might have a valid segment we should process if not, then we can't add this passenger to any segment so far, so our solution to the problem stays the same. (dp[i] = dp[i-1]) Now, how do we get the new solution if we have a segment to process? We will keep track of two variables: the start of this segment, if it is valid, and its end. we iterate from where we were backwards to the start of the segment, and for each passenger we come across, we check that the last element of its kind is before our end (if not, then we'll check it later, i.e. this segment's end has to be moved), and we check where the first element of its kind is – if needed, we move our predicted start for this segment back even further.If we manage to successfully iterate over the segment, then we need to calculate the needed XOR value for it, and then check if we get a larger final solution by adding dp[start of our segment] + our segment's XOR value, or by simply taking the previous dp value, dp[i-1], whichever gives us a larger result. Confused?In the original solution I couldn't understand what happens if our new segment overlaps some other, smaller segment, but it is important to note that the dp value we add to our newly calculated segment's value, is the dp value for the problem BEFORE the elements of our new segment even began. We don't look at dp[i-1], we look at dp[beginning of our segment].Sometimes it's easier to just go though someone else's code, so here's my final solution to the problem. Code#include using namespace std; const short N = 5001; short a[N], start[N], en[N]; // a is the initial list of numbers, start and en our the first and last occurrences of a certain number. long dp[N]; bool s[N]; int main() { short n; cin >> n; for (short i = 0; i < n; ++i) { cin >> a[i]; en[a[i]] = i; } for (short i = n-1; i >= 0; --i) start[a[i]] = i; dp = 0; for (short i = 0; i < n; ++i) { if (en[a[i]] != i) dp[i+1] = dp[i]; else { // s[N] keeps track of which numbers we have encountered or not for (short k = 0; k < N; ++k) s[k] = false; short mi = start[a[i]]; // predicted start of our segment bool valid = true; for (short j = i; valid and j >= mi; --j) { if (en[a[j]] > en[a[i]]) valid = false; s[a[j]] = true; mi = min(mi, start[a[j]]); } if (valid) { long acc = 0; for (short k = 0; k < N; ++k) if (s[k]) acc ^= k; dp[i+1] = max(dp[i], dp[mi] + acc); } else dp[i+1] = dp[i]; } } cout << dp[n] << endl; } 
•  » » Hi I've tried solving this problem almost like your method (only little difference like processing dp index as i-1 instead of i+1 ). I am getting WA on 49. The test case is too large for me to comprehend. Could you help me in finding the problem with my code? Thanks. http://codeforces.com/contest/811/submission/27566824
•  » » I tried solving C by making directed graph..but getting WA on test 26 https://codeforces.com/contest/811/submission/90333411 Please help.
 » When n ≤ 104 I always assume that O(n2) shouldn't work. I'm surprised!
 » Why this code is giving me WA in problem 811C - Vladik and Memorable Trip here is my code: 27467986
 » Would someone mind help me look at my code for Problem E? I suppose my code have a time complexity of O(N*(M+Q)*logM) with each merge action as O(N), but I suspect that I messed up part of the implementation thus causing TLE (is the bfs search too expensive for merging?).http://codeforces.com/contest/811/submission/27392571Thanks in advance.
•  » » I see that your solution is extremely non-optimized. Problem is not in bfs, but in vectors inside struct node. You shouldn't store all the edges this way, you can generate them on the run (checking if there is an edge when trying to bfs). For example, your code works 7 seconds in polygon, while this code works in 3 seconds (didn't pass in 2 sec too) (I just made edges in nodes global). This happens because dynamic memory allocation is too slow.
 » 3 years ago, # | ← Rev. 2 →   Challenge Div2CLet dp[i] denote answer when we have created segments till 'i'. We can construct a segment tree which can answer the following for a range [l, r] - 1. Maximum of last occurrences of the elements in the range [l, r] -> Q(l, r).last 2. Minimum of first occurrences of the elements in the range [l, r] -> Q(l, r).first 3. XOR of the elements whose last occurrences lie in [l, r] -> Q(l, r).ans For a valid segment, Q(l, r).first = l & Q(l, r).last = r. So we are checking at those indices only where Q(l, r).last = r. And if Q(l, r).first != l, then we need to change 'l' to atleast Q(l, r).first and then again check the condition. dp[i] = dp[i-1] If Q(l, r).first = l && Q(l, r).last = r dp[i] = max(dp[i], dp[l-1] + Q(l, r).ans) If Q(l, r).first < l && Q(l, r).last = r While l < Q(l, r).first && Q(l, r).last = r l = Q(l, r).first If QUERY(l, r).first = l && QUERY(l, r).last = r dp[i] = dp[l-1] + Q(l, r).ans We can save the optimal index for 'l', which will bring the overall complexity to O(nlogn).Solution
 » Problem B: can be Easily solved in O(q*logn) without AVL,Merge Sort,SQRT Decomposition. Concept : Simply use BIT Reference : First go Through KQUERY (SPOJ) using BIT: MY code :http://codeforces.com/contest/811/submission/27556192
 » Problem C dfs solutionhttp://codeforces.com/contest/811/submission/27572002Description: Put all LR segments in a tree where each segment's parent is either whole list with root = MAXN or smallest segment that fully contains it. Mark all segments that contain some other elements other than their children with w[i] = 1, their value cannot be xor, only sum of its children Run dfs from root, and based on value of w[u] return either sum of all children segments results or if w[u] == 0 maximum between sum and xor.
 » My O(n) solution for problem C... Since I'm a beginner in dp (and English So I just implement my own thoughts.. and then I get the code blow.. http://codeforces.com/contest/811/submission/29330084
 » 14 months ago, # | ← Rev. 2 →   Can we solve C by doing DP on all subsegments of the input? Like DP[segment(l,r)]= max(xor(segment(l,r)), DP[segment(l,i)], DP[segment(i+1,r)] for all l<=i<=r where both segment(l,i) and segment(i+1,r) satisfy the condition)
 » Problem D is so bad.