### majk's blog

By majk, history, 5 years ago,
Code
Code
Code
Code
Code
Code
Code
Code
Code
• +151

| Write comment?
 » 5 years ago, # |   +67 the fastest editorial in the west
 » 5 years ago, # |   +404
•  » » 5 years ago, # ^ |   +88 You just want contribution, go away!
•  » » 5 years ago, # ^ |   +15
•  » » 5 years ago, # ^ |   +19 Actually this is the Commentin the screen posted in the blog it taken 11 months since the comment of Swistakk and now it has been 22 months it seems that the REDs never forget :'D
 » 5 years ago, # |   +14 Fortunately for us, for each n≥3 there is a prime number in interval [n,3n/2], simply the smallest of them will do. Ok I need a demonstration for this one
•  » » 5 years ago, # ^ |   +49 Though I am interested in seeing some mathematical proof, I brute-forced in the interval [3, 1000] and it indeed holds true in that interval. And since 3 <= n <= 1000, we are set to get AC.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +2 .
•  » » 5 years ago, # ^ |   +11 You can read about Prime Gap
•  » » 5 years ago, # ^ |   +30 Look at some of the results here:https://en.wikipedia.org/wiki/Bertrand%27s_postulate#Better_results
•  » » 5 years ago, # ^ |   0 I tested it by running through all n <= 1000 in ~ 500 squared operations, took me 2 min to implement because you needed a sieve anyway
•  » » 5 years ago, # ^ |   -11 I just queried Wolfram Alpha for all primes less than 1000.
•  » » 9 days ago, # ^ |   0 The degree of every node can be either 2 or 3.By Chicken McNugget Theorem, we get to know that the smallest number that we can't make with 2,3 is 1. And we won't get one degree. So suppose we have X number of 2-degree nodes and Y number of 3-degree nodes, so $X +Y = n$, and $2X + 3Y = 2e$ Why ? Solving these equation we will get $X = 3n - 2e$ and $Y = 2(e - n)$, and also $X >= 0$ and $Y >= 0$, upon solving this you will get $e >= n && e <= 3n/2$
 » 5 years ago, # |   0 Shouldn't there be a proof or at least a link to an article for 1178D, about finding a prime number between n and 3n/2? Cause a lot of the constructive algorithms used in it rely on this fact
•  » » 5 years ago, # ^ |   0
 » 5 years ago, # |   +34 "To optimise it to O(n^3) just note that the selection of a and b is independent."
•  » » 5 years ago, # ^ |   0 Did you realize this statement?
 » 5 years ago, # | ← Rev. 2 →   0 Hi, can someone tell me how is my code for E (very brute, I printed palindrome with 2 characters) getting AC?Is there any proof or countertest?https://codeforces.com/contest/1178/submission/57407689
•  » » 5 years ago, # ^ |   +11 Oof it's been hacked. apparently it altered my placement. good to know ig
 » 5 years ago, # | ← Rev. 3 →   0 Why my solution is giving wrong answer in problem B? linkI am using simple permutation and combination.EDIT. this one got accepted. I guess macros doesn't work the way I thought they work :(
•  » » 5 years ago, # ^ |   0 Take long long int instead of int. (to stop overflow)
•  » » » 5 years ago, # ^ |   0 I am still getting wrong ans after using long long. I have a macro #define int llilink
•  » » » » 5 years ago, # ^ |   +1 Take your variable 'a' as long long. It is the one that is overflowing
•  » » 5 years ago, # ^ |   0 Your macro #define int long long is lower than type typedef vi vector. That's why your values in your vi arr remain int
•  » » » 5 years ago, # ^ |   0 Thanks for clarification :)
 » 5 years ago, # |   0 For Problem G, is a lazy segment tree possible instead of sqrt decomp? Is sqrt just to make implementation easier?
•  » » 5 years ago, # ^ |   0 Since you need to rebuild some part of the convex hull trick, using any type of segment tree just doesn't help it. Sqrt decomposition is used to balance out between the rebuilding complexity.
•  » » » 5 years ago, # ^ |   0 Thank you, I finally understand now.
 » 5 years ago, # |   -8 In problem D, how can we say that there is always a prime in the interval [n,3n/2] ?
•  » » 5 years ago, # ^ |   0 Just list all primes less than 1000 by writing a simple program or querying Wolfram Alpha.
•  » » 5 years ago, # ^ |   0 The density of prime numbers around n is approximately 1/ln(n) which means 1 out of every ln(n) numbers is prime, so between n and n+ln(n) roughly there must be a prime hence between n and 3n/2 also for large n, there will be a prime
 » 5 years ago, # |   +10 Learnt a very important lesson from Problem B.Always use long long int if you're not 100% sure that int will not overflow.
•  » » 5 years ago, # ^ |   +7 I have now made a habit to use long long int instead of int. It really was frustrating back then.
•  » » » 5 years ago, # ^ |   +102 well, once you will notice replacing back to ints gives you AC instead of TL and your life won't be the same
•  » » » » 5 years ago, # ^ |   -91 Once you will notice replacing ints to long longs will give you AC instead of WA and your life won't be the same
•  » » » » » 5 years ago, # ^ |   +97 Once you'll be able to read whole discussion and not only last message of it. Not sure it'll change your life
•  » » » » » » 5 years ago, # ^ |   -59 Where did you get the information that I read the only last message xD? Of course I read "whole discussion" consisting of your message and a few above. I will say more, my post fits much better to the discussion taking preceding posts into account.
•  » » » » » » » 5 years ago, # ^ |   +153 You had polish contest today or something?
•  » » » » » » » » 5 years ago, # ^ |   -52 What were you trying to say through your last two posts other than just throwing wannabe cool random insults unrelated to the actual topic?
•  » » » 5 years ago, # ^ |   -25 Let's downvote Swistakk to make his contribution out of top 15.
•  » » 5 years ago, # ^ |   +65 Or, you know, calculate which one u need.
•  » » » 5 years ago, # ^ |   +10 Thinking a little bit, it becomes understandable that in the worst case scenario each product may produce 10^(10).So, the decision to choose long long should have been clear to me if I paid enough attention.Thanks.
•  » » 5 years ago, # ^ |   +5 using long long instead of int is for the weak
 » 5 years ago, # | ← Rev. 2 →   +110 I was able to solve G with a modified kinetic tournament: 57423487 (AC in 530ms)Can anyone bound the time complexity?Edit: I think I have a proof that it is $O((n+q\log{n})\log^2{n})$.
•  » » 5 years ago, # ^ |   +57 Modified kinetic tournament? What are these mysterious words xd?
•  » » 5 years ago, # ^ |   -12 Could u please give some good tutorial links for the data structure.
•  » » » 5 years ago, # ^ |   +5 I don't know of a good tutorial for this data structure. I learned about the kinetic tournament itself from Wikipedia and realized the priority queue can be embedded into the segment tree by having each subtree store the time until its first certificate failure. This problem also required lazy propagation of time advancement updates.I would recommend reading jiry_2's tutorial on "segment tree beats" as it uses many of the same ideas. Once you understand the ideas behind it you may be able to understand the code.
•  » » 5 years ago, # ^ |   +24
•  » » 5 years ago, # ^ |   +5 Can you share your proof?
•  » » » 5 years ago, # ^ |   +15 The data structure is basically an amortized segment tree that supports the following operations on two arrays $a_i$, and $b_i$: For $l\le i \le r$, set $a_i$ to $a_i+b_ix$, where $x>0$ ($x$ may be different between updates). Find $\max_{l\le i \le r} a_i$. Queries are obviously $O(\log{n})$. Updates are trickier.First, suppose all updates are over the entire range. For each leaf, consider the set of segment tree nodes where it is maximum in. The size of this set can increase and decrease, but once it decreases it will never increase again.More formally, let's call a leaf shrinking if it will never become greater than the sibling of the topmost node in the segment tree it is maximum in (i.e. $a_{node}\le a_{sibling}$ and $b_{node}\le b_{sibling}$), and growing otherwise. Once a leaf becomes shrinking, it will stay shrinking forever. If a leaf is shrinking, the set of nodes it is maximum in will never increase again.Define the potential for a growing leaf to be the depth of the topmost node it is maximum in. The total potential is the sum of potentials of all growing leaves. Each unit of potential will pay for $O(\log{n})$ units of time. The initial potential is $O(n\log{n})$.An update will basically locate each node whose maximum leaf changes and fix it in $O(\log{n})$ each. This is paid for by the potential decrease of the growing leaf involved. Some leaves will change from growing to shrinking, but this only decreases the potential.Now consider updates that do not cover the entire range. For most nodes, everything above remains true. The exception is the $O(\log{n})$ nodes whose parent are partially covered by the range. The leaves maximum in these nodes may change from shrinking back to growing, which could increase the potential by $O(\log^2{n})$.Thus, the total time complexity is $O((n+q\log{n})\log^2{n})$.
 » 5 years ago, # |   +65 Why are all the editorial solutions playing code golf? I can understand doing it in a contest, but for a solution that you intend people to read and try to understand? The variable names are all just one letter and there are no comments or anything anywhere. Please never do this again. (I realize that this happens in other editorials too, which makes it even worse — how is THIS the standard??)
•  » » 5 years ago, # ^ |   +5 Same goes for explanations, actually. Sometimes all they say is How to solve the problem, not why it works (see current D for example). The code itself starts with double tabs for some reason. If they put so much effort in problems and testing, the code should be better than the ones posted. Accepted or not, there is a difference between right answer and solution.
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 It's actually kinda funny though; I think this is a perennial problem for anyone with backgrounds in both mathematics and computer science. Programmers may wish that mathematicians stop using single-letter variables and funny symbols, but when you're up to your neck twisting numbers in algebraic and calculus knots, treating them as means to an end rather than an end to themselves... sometimes there is just no concise way to describe the intermediate variables. Just imagine if π was "circumferenceToDiameterRatio" everywhere, even in seemingly far-removed contexts like the "infinite lighthouse-lake" problem: https://www.youtube.com/watch?v=d-o3eB9sflsThough I do agree that more step-by-step explanations as well as some comments would be nice.Additional sources of great "fun": confusion between 0-indexing, 1-indexing, and sometimes even Python-indexing...
•  » » 5 years ago, # ^ |   0 I get whatchu mean. In CEOI testing, I was surprised that I'm the one with readable codes.
 » 5 years ago, # |   +13 majk For 1178E another Exercise could be as follows:If There are many letters like complete set of alphabet (Not just 'a' ,'b', 'c'). Also If consecutive elements can be same.In above case, "IMPOSSIBLE" can be one of the answers. SolutionKeep a deque of index of occurence of each letter or alphabetNow, Keep a sorted array of each deque index with comparator as difference between the front and back element index.From all other deque remove front elements until, they are strictly greater than the index of current deque front element and do so similarly for back elements.Now add front and back element of this deque to an answer vector and pop them from deque.at the end sort answer vector and print all the characters of string whose index occur in the answer vector.
•  » » 5 years ago, # ^ |   0 Can you prove that works? It looks like it doesn't (but I may have misunderstood something).
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Have a look at thisThis is solution for 1178E. Instead of having 3 deque (for 'a','b','c') we can have a deque for each alphabet.Now we can take a deque whose back()-front() is maximum. maintaining order of deque would be very easy as we have to sort an array (array size would be number of disitnct letters so may be 26 for if we have all lower case letters.).In above solution I have checked which among the those deque (out of a,b,c) has maximum difference (back()-front()). so instaed of three we need to check for all the distinct alphabets.
•  » » 5 years ago, # ^ |   0 I think you are trying to apply greedy solution. It clearly doesn't work... This was solvable due to such constraints...
•  » » » 5 years ago, # ^ |   0 The proof of correctness goes this way.Let's say we have 2 pointers. l pointing to index 0 and r pointing to index n-1.By comparing the difference, the approach is to converge these pointers and bring them close to each other at the slowest pace.let's say currently l points to index i1 and r points to index i2.let there been any index j1,j2 such that j1r then those would have already been covered (as we are moving at slowest pace). another case could be we have more than one choice of moving pointers and include letters in palindrome. here, we can take any one and move ahead (since our focus is to decide for current position if they can be included in formation of palindromic string.
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 What's your answer for s = "AbccbAWpqrstW"? Important characters I have written in uppercase...
•  » » » » » 5 years ago, # ^ |   0 IMPOSSIBLE
•  » » » » » » 5 years ago, # ^ |   0 I have changed the TC... What's your answer then?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 That's no proof of correctness. It works for the "no adjacent pairs is equal" due to luck, if you understand the proof that there's always a solution you'll understand why.amnocabplpb — your algorithm finds "ama" even though "bplpb" is the best answeramncabplpb — depending on ties, your algorithm finds "ama" or "bplpb" (it'd find "ama" if you tie like in your submission), in this case "bplpb" is the only answeramncbpalpb — your algorithm finds "ama" even though "bpapb" or "bplpb" are the only answers. (5 spaces for a and 4 spaces for b)I could create some more cases but I think this is enough
•  » » » » » 5 years ago, # ^ |   0 yeah. got it. Thanks for help.
 » 5 years ago, # | ← Rev. 2 →   0 Can anyone please explain what S[2 : -2] means in problem editorial E?
•  » » 5 years ago, # ^ |   0 S[2:-2] is S except for the first 2 and last 2 elements.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +13 I'm using the Python notation for subscripts. It means starting from the $2$nd character ($0$-indexed) until the $2$ character from the end ($-2$) exclusive. So the string $S$ without the first and last two characters.
•  » » » 5 years ago, # ^ |   0 Got it! thanks! :)
 » 5 years ago, # |   +3 Explain please: Problem F1: To optimize it to O(n^3) just note that the selection of a and b is independent
•  » » 5 years ago, # ^ |   +26 ax + ay + bx + by == (a + b)(x + y)
•  » » 5 years ago, # ^ |   +22 $DP[l][r] \\= \sum_a \sum_b DP[l][a-1] * DP[a][I[c]-1] * DP[I[c]+1][b] * DP[b+1][r] \\ = \left( \sum_a DP[l][a-1] * DP[a][I[c]-1] \right) \cdot \left( \sum_b DP[I[c]+1][b] * DP[b+1][r] \right)$So you can just calculate $\sum_a DP[l][a-1] * DP[a][I[c]-1$and $\sum_b DP[I[c]+1][b] * DP[b+1][r]$each in $\mathcal O(n)$.
•  » » » 5 years ago, # ^ |   0 Now I got it, thank you so much)
•  » » » 5 years ago, # ^ |   0 It may seem silly but can you please tell me how the complexity of ∑aDP[l][a−1]∗DP[a][I[c]−1 is O(n) . I am really not able to prove/logically explain it .
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 For selected l and r you need 1 for loop to calculate all a's.
 » 5 years ago, # |   0 Can G be solved using lazy propagation on segment tree? I was thinking, if we transform given tree in an array, then the problem is finding the maximum answer in some interval.That sounds like it can be done with segment tree in which for each vertex we store a pair of values, (sum of (values of array A) of parents of the best vertex in that interval) and (sum of (values of array B) of its parents). Update for some vertex is just updating the interval by some value. When we are searching for maximum, we take in consideration only absolute values. If its not correct, please, I would like to know where it fails, or if I misunderstood something. Hope brackets help. Thanks in advance.P.S. sorry if my english is bad :)
•  » » 5 years ago, # ^ |   0 The problem is, we have to increment each element on the interval by a multiple of the sum of b_i across all ancestors, not a single value across all elements, so lazy propagation doesn't work.
 » 5 years ago, # | ← Rev. 2 →   0 Fortunately for us, for each n≥3 there is a prime number in interval [n,3n2], simply the smallest of them will do.This was the only link I found after the contest ended. Salute to the authors for assuming this was trivial. :|
•  » » 5 years ago, # ^ |   0 Link does not work
•  » » » 5 years ago, # ^ |   0 Updated.
 » 5 years ago, # |   0 In question E could someone explains to me why the answer would never be Impossible?
•  » » 5 years ago, # ^ |   +4 Because you can cut pieces of size 2 from both ends of the string and always get two characters for palindrome from there. That is already almost half the string size. You can add any character from remaining string of length 3 or less in the end.
 » 5 years ago, # | ← Rev. 2 →   0 For C, may someone please explain how 2^(w+h) was derived? Thanks.
•  » » 5 years ago, # ^ |   0 Work for 1-D array then add another 1-d layer to it u will see
 » 5 years ago, # |   -8 Can anybody help me out with this wrong solution (probably integer overflow). Please explain when to use a certain data type according to constraints, what could go wrong if I use long long int everywhere, Thanks.
•  » » 5 years ago, # ^ |   0 Yes. The problem in your code is indeed that of overflow in the power function. Convert all of the ints to long long ints in the function and it will work.Actually there is no harm if you use long long int everywhere but I once heard that memory limit exceeded can be encountered in some case. (btw I have never encountered it personally due to the use of long long int). You use int when you are certain that none of your value stored in your variables exceeds 10^9 (approx.).
•  » » » 5 years ago, # ^ |   +3 You can also get TLE with long long when used with slow Data structure like GNU-PBDS Ordered set, it happened with me in one of the CodeChef long rounds. But for most cases, using long long is good idea.
•  » » » » 5 years ago, # ^ |   0 Noted. Thanks man.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Yes. When you multiply two ints, integer overflow happends.Use (or convert int to) long long int when multiplying. For example, x = ((long long int)x*x) % p;.
 » 5 years ago, # | ← Rev. 3 →   +2 An one-line solution of C using python: print(pow(2,sum(map(int,input().split())),998244353)) 57432100
•  » » 5 years ago, # ^ |   +90 A nice one-line solution of E: print(input()) Unfortunately, doesn't work after the checker update :(
 » 5 years ago, # |   0 Can anybody please share his code for the problem f1,as i was not able to grasp the code shared in editorial. It would be good for me if someone would share the code in which segment trees are used for min query and a memoization approach rather than iterative dp as i have used them in my code and would be easier to see where i am wrong.... But every help is welcome.. Thanks in advance.
•  » » 5 years ago, # ^ |   0 if anyone can find the mistake , here is the code i used... http://www.ideone.com/ocV6az
 » 5 years ago, # |   0 Those Bonuses are really interesting!Could you give some details of Bonus of F2? Does the faster alogorithm reduce O(n^3) part to sth smaller such as O(n^2logn) ? It's so hard.BTW, time limit of F2 is so loose that My O(n^4+m) and O(n^3logn+m) can pass it. The runnning time are 5366ms and 3400ms. My O(n^3+m) runs 717ms, and most ACs pass within 1s. I guess those runs more than 3s are all of bad complexity, maybe 3s is a better time limit.
•  » » 5 years ago, # ^ |   +10 My solution works in $O(n^{2}+m)$.
•  » » » 5 years ago, # ^ |   0 Thank you, got it.
•  » » » 4 years ago, # ^ |   0 What's the solution? Any hints?
 » 5 years ago, # |   0 Why memory limit exceeded in my solution to problem B? Code
•  » » 5 years ago, # ^ |   0 Pay attention to this line: for(int i=str.size()-2;i>=0;i--)When str.size()=1, str.size()-2 does not equal to -1 as str.size() is a variable of type unsigned intOn my ubuntu 19.04 x64 with g++ 8.3, that equal to 18446744073709551614.
•  » » » 5 years ago, # ^ |   0 Thanks for the reply. But why does this code work then? The array declared now is of type int instead of long long.
•  » » » » 5 years ago, # ^ |   0 This can explain everything: #include using namespace std; int main(){ string s = "s"; int x = s.size()-2; cout << x << endl; long long y = s.size()-2; cout << y << endl; return 0; } Notice: Use cf's 'custom test' to run this, please.
 » 5 years ago, # |   0 When solving problem G, I noticed that only changing my block size sometimes changes AC to WA. I am wondering, where is the error in my implementation? Is it likely to be in my SQRT decomposition or in my convex hull code?AC submission: 57441583WA submission: 57441814
 » 5 years ago, # |   +3 1178E-ArchaeologyIn the editorial :"Bonus: Find a subpalindrome of length at least ceil(|s|/2)."s=abababcbcbc|s|=11 bbbbb is a subpalindrome of maximum length and |bbbbb|=5. In this case there is no pallindrome of length 6.
•  » » 5 years ago, # ^ |   0 Yes, for the bonus there are some cases in which no solution exists.
•  » » » 5 years ago, # ^ |   0 Hi, Could please explain the solution of Bonus problem, present in E's editorial.
•  » » » » 5 years ago, # ^ |   0 Cases of length of 4k,4k+1,4k+2 are trivial, and we try to transform the case of 4k+3 into them if possible. You will find that the only cases that can’t be converted easily are like abab...ab abc bc...bcbc where the number of left ‘ab’s is equal to that of right ‘bc’s. It’s easy to prove there is no solution for these cases.
 » 5 years ago, # |   +51 majk Thanks for the tasks!There's a problem in task G, though. Your main solution uses doubles in some point to compute the convex hull. However, the point coordinates are as large as 1e18, and double has only 52 bits of precision (so something like 15-16 significant digits). Therefore, it's possible to craft a test against it: gen. it took way too much of my life(When using doubles, your main solution decides that some three input points are collinear when they're not; then it removes a point that actually is the only optimal point for some query.)I have some intuition that long doubles might be just enough for this task (by a few of bits of precision), but doubles are hackable. :
•  » » 5 years ago, # ^ |   +11 It would be great to have the Polish mafia for testers!I also have a solution with big integers marked as the master solution. In editorial I used the double solution for brevity.I didn't find such case and somehow convinced myself that doubles are sufficient (my notes are long gone as this task was prepared a year ago). So, congrats on finding the hacking case.It seems to have hacked only our Java solution, while the C++ one still stands. I'll see what I can do about it when I get back to a computer.
•  » » » 5 years ago, # ^ |   0 return a/b >= c/d;Comparing without eps sounds dangerous af.Is it even guaranteed that e.g. $3/7 = 9/21$ on doubles or long doubles?
•  » » » 5 years ago, # ^ |   +18 Oh damn, these 32-bit cf judges. It seems that 32-bit C++ executable decides to use x87 instruction set to do the floating-point computations, which apparently has larger precision than double. The solution in editorial fails only when compiled in 64-bit mode. :/It then makes sense that Java solution fails as Java VM doesn't know anything about 80-bit floating-point numbers, and simply won't be able do any operations with higher-than-double precision.
•  » » » 5 years ago, # ^ |   0 My solutions fails on the 3 test if I use 57508921 a/c >= b/d like in the editorial and gets AC, if I use a * d — b * c >= 0. 57510232The problem is in floating point calculation?.P.S. this computation I made in long doubles.
 » 5 years ago, # | ← Rev. 2 →   -8 What does s[2 : -2] in the problem E actually mean? Edit : i found the explanation, doesn't matter anymore.
 » 5 years ago, # |   +3 Another possible way to solve problem F is to note that there is one-to-one correspondence between such coloring and rooted tree obtained in such a way that for each color $v$ its ancestor is the color $p_v$ which was there before color $v$ was applied. And thus DP may be to calculate number of rooted trees which may be built on some particular segment. This one seems quite standard...
•  » » 5 years ago, # ^ |   0 I was trying to work out this idea myself, but I'm having trouble with figuring out where the current segment starts and ends. Basically, I start with the finished segment that is inputted. Starting from the highest color id, change its color to either the color of its left or right neighbor (this simulates the reverse of one painting step). Then, continue solving with that modified state (until we return to the blank segment), but the problem is I don't have a fast way of finding the current left bound and right bound of the highest color id segment. I think that this should work though by memoizing the states.
 » 5 years ago, # |   0 in problem E 1st test case why cabac is not a valid solution ??
•  » » 5 years ago, # ^ |   0 It is.
 » 5 years ago, # |   +16 I have a faster solution which works in $O($$N^2 * log_2$$(N))$ for F2.Lets count the number of way to create 2 arrays $a_i$ and $b_i$ (the segment that we are going to paint the $i$-th color) in reversed order (From $N$ to $1$). Denote that $L_i = p$ be the leftmost position that $c_p = i$, same thing with $R_i$ for the rightmost position.Say we are solving for the $i$-th color. We can easily write out some condition for this color as below: We should not paint more than enough. This means that we should only paint the $i$-th color for the segment from $L_i$ to $R_i$, and some positions to its left and right if these positions have already been painted. If our current $a_i$ and $b_i$ for the $i$-th color conflicts with some $a_j$ and $b_j$ $(j > i)$ that has already been painted. $[a_i, b_i]$ should strictly cover $[a_j, b_j]$. And once the $i$-th color covers the $j$-th color in our progress, we should also replace $j$-th color with $i$-th one by changing $[a_i, b_i]$. With these two properties, our problem changes to choosing how many $j$-th color to cover from the left and from the right instead of choosing some specific $[a_i, b_i]$.Let's denote $dp(i, j)$ as the number of way to paint our array until we reach the color $i$ and the consecutive segment of painted positions around $i$ formed with $j$ different colors. To be easier to see, let's try solving with F1 first. If we are solving for the $i$-th color, we should look to its left and right, let's say that these positions have already been painted and have the represented color (the smallest color in that consecutive segment) $left$ and $right$. Now, if the $i$-th color is going to cover $x$ out of $X$ colors from its left and $y$ out of $Y$ colors from its right. We will have the transition formula below:$dp(i, X + Y - x - y + 1)$ $=$ $dp(left, X)$ $*$ $dp(right, Y)$.Luckily, the $i$-th color will cover only a suffix or a prefix of $dp(left)$ and $dp(right)$, thats why we can calculate the suffix sum of $dp(left)$ and $dp(right)$. The idea behind this is that if we want to keep $k$ colors from $dp(left, X)$, we can simply use $i$ to cover $X-k$ colors from its suffix.Now our problem becomes$dp(i, x + y + 1) = dp(left, x) * dp(right, y)$.Which one can easily see the FFT/NTT application here. In total, this solution will run the FFT/NTT for $N$ times and the time complexity is $O($$N^2 * log_2$$(N))$. The same can also apply for F2. But its a little bit more tricky if theres some painted color between $L_i$ and $R_i$. This part can be easily solved, but too hard for me to implement during the contest lol.
•  » » 5 years ago, # ^ |   +1 Good solution! It seems that the $O(n^2)$ solution has also emerged if just replace the FFT/NTT by brute force since the contribution of every pair would be counted only once in all multiplication!
•  » » » 5 years ago, # ^ |   0 Didn't realize this until now. Big thanks!!!
 » 5 years ago, # |   0 cann't visualize the tutorial of Problem F1. Can anyone please describe the solution of this problem more clearly?Thanks In Advance
•  » » 5 years ago, # ^ | ← Rev. 2 →   -8 Maybe these annotations will help:https://codeforces.com/contest/1178/submission/57488328https://codeforces.com/contest/1178/submission/57489552This illustrates a basic DP (dynamic programming) principle: solve the smallest subproblems first, then use the solutions to those subproblems to compute the larger ones
 » 5 years ago, # |   0 Can someone explain the states in problem F1-Short Colourful Strip? And how the recursive relation is being derived?
•  » » 5 years ago, # ^ |   -8 Maybe these annotations will help:https://codeforces.com/contest/1178/submission/57488328https://codeforces.com/contest/1178/submission/57489552This illustrates a basic DP (dynamic programming) principle: solve the smallest subproblems first, then use the solutions to those subproblems to compute the larger ones
 » 5 years ago, # | ← Rev. 2 →   -13 In the editorial of E, what's the meaning of s[2: −2]? Why can the index be negative?Edit : I found the explanation, doesn't matter anymore.
 » 5 years ago, # |   0 How to solve E if there may exist all the alphabet?
 » 5 years ago, # | ← Rev. 2 →   0 For those who may need help understanding the editorial and code for F1 and F2, I've plagiarized the editorial solutions, translated them to Kotlin, and added my own annotations:https://codeforces.com/contest/1178/submission/57488328https://codeforces.com/contest/1178/submission/57489552
 » 5 years ago, # |   0 In problem F1, what does lowest ID of a colour used in the final strip mean?
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 As stated in the problem description, the strip is colored with each color from 1 to n successively. Thus the minimum color for each segment is significant, as that index will be colored first before the others, and, crucially, that index can never be recolored again
•  » » 5 years ago, # ^ | ← Rev. 5 →   +5 Consider a simple example: 4 4 4 1 2 3 For len = 0 and len = 1, the answer is trivial, there is only one way such "subsegments" can be colored. Now we consider each subsegment of length 2: 4 1 1 2 2 3 It turns out that those answers are rather easy to compute, as there are only two ways any subsegment of length 2 can be colored: either a a -> b a -> b c, or a a -> b b -> b c (given a D[a=2][l=0] * D[a=2][l=2] = 1 * 2 = 2 1 1 0 -> D[a=2][l=1] * D[a=3][l=1] = 1 * 1 = 1 1 1 1 -> D[a=2][l=2] * D[a=4][l=0] = 2 * 1 = 2 which is 5. Therefore D[a=1][l=3] = left * right = 1 * 5 = 5Now we consider the original problem: D[a=0][l=4] 4 1 2 3 If you follow the steps laid out previously, left = 2 and right = 5, so the final result will be 2*5 = 10.After all that work though I realized that we never used any of the results D[a=x][l=3] in the final result, so there is probably some room for optimization here. But we can similarly see that for the problem: 4 4 1 2 3 4 When we get to the final iteration (D[a=0][l=4]), left = 1, but right = sum of: D[a=1][l=0] * D[a=1][l=3] = 1 * 5 = 5 D[a=1][l=1] * D[a=2][l=2] = 1 * 2 = 2 D[a=1][l=2] * D[a=3][l=1] = 2 * 1 = 2 D[a=1][l=3] * D[a=4][l=0] = 5 * 1 = 5 so the answer is 14 in this case.
•  » » » 5 years ago, # ^ |   0 For the example you gave, 4 1 2, shouldn't the four possible paintings be: 1 1 1, 1 1 0, 0 1 1, and 0 1 0? In your description, 1 1 0, and 0 1 0 are achieved from picking the left boundary, and 0 1 1 and 0 1 0 are from the right boundary. But this over counts 0 1 0. Am I missing something here?
•  » » » » 5 years ago, # ^ |   0 Actually it's 1 1 x and 0 1 x for the left boundary, and x 1 1 and x 1 0 for the right. As the choices are independent, we basically don't care where the other boundary is when considering the left and right factors separately. The math checks out, cause we then multiply the factors for the subresult, as that's what you do for independent choices in combinatorics (e.g. 5 dishes and 4 drinks = 20 meal choices, assuming one of each)
 » 4 years ago, # |   0 For question d i thought like the soln and also found the goldman conjecture conjectures: 1.Every integer greater than 5 can be written as the sum of three primes. 2.Every even number greater than 2 can be written as the sum of two primes. now i am unable to solve the problems using the these conjectures could anybody guide me
•  » » 4 years ago, # ^ |   0 betrand postulate there exits a prime p n < p < 2*n -2mindeg >=2 => E >= nThe problem is to represent 2E as sum of n primes. For that find E first. let E be nearest prime num to n Bertrands theorem guarentee E<2n-2any even number by goldman conjecture can be expressed as 2 num E-2(k-2) is even and can be express as u and vsince E<2n-2 u
 » 17 months ago, # |   -6 C is easy peasy lemon squeezzyy.