### majk's blog

By majk, history, 5 weeks ago, ,
Code
Code
Code
Code
Code
Code
Code
Code
Code

• +151

 » 5 weeks ago, # |   +67 the fastest editorial in the west
 » 5 weeks ago, # |   -86 I am ready to downvote who comment "Fast editorial!! wow!!!" Thanks for the great contest btw
 » 5 weeks ago, # |   +404
•  » » 5 weeks ago, # ^ |   +88 You just want contribution, go away!
•  » » 5 weeks ago, # ^ |   +15
•  » » 5 weeks 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 weeks 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 weeks 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 weeks ago, # ^ | ← Rev. 3 →   +2 .
•  » » 5 weeks ago, # ^ |   +11 You can read about Prime Gap
•  » » 5 weeks ago, # ^ |   +30 Look at some of the results here:https://en.wikipedia.org/wiki/Bertrand%27s_postulate#Better_results
•  » » 5 weeks 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 weeks ago, # ^ |   -11 I just queried Wolfram Alpha for all primes less than 1000.
•  » » 5 weeks ago, # ^ |   0 can find to the reason of that????
 » 5 weeks 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 weeks ago, # ^ |   0
 » 5 weeks ago, # |   +34 "To optimise it to O(n^3) just note that the selection of a and b is independent."
•  » » 4 weeks ago, # ^ |   0 Did you realize this statement?
 » 5 weeks 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 weeks ago, # ^ |   +11 Oof it's been hacked. apparently it altered my placement. good to know ig
 » 5 weeks 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 weeks ago, # ^ |   0 Take long long int instead of int. (to stop overflow)
•  » » » 5 weeks ago, # ^ |   0 I am still getting wrong ans after using long long. I have a macro #define int llilink
•  » » » » 5 weeks ago, # ^ |   +1 Take your variable 'a' as long long. It is the one that is overflowing
•  » » 5 weeks 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 weeks ago, # ^ |   0 Thanks for clarification :)
 » 5 weeks ago, # |   0 For Problem G, is a lazy segment tree possible instead of sqrt decomp? Is sqrt just to make implementation easier?
•  » » 5 weeks 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 weeks ago, # ^ |   0 Thank you, I finally understand now.
 » 5 weeks ago, # |   -8 In problem D, how can we say that there is always a prime in the interval [n,3n/2] ?
•  » » 5 weeks ago, # ^ |   0 Just list all primes less than 1000 by writing a simple program or querying Wolfram Alpha.
 » 5 weeks 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 weeks ago, # ^ |   +7 I have now made a habit to use long long int instead of int. It really was frustrating back then.
•  » » » 5 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |   +153 You had polish contest today or something?
•  » » » » » » » » 5 weeks 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 weeks ago, # ^ |   -25 Let's downvote Swistakk to make his contribution out of top 15.
•  » » 5 weeks ago, # ^ |   +65 Or, you know, calculate which one u need.
•  » » » 5 weeks 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 weeks ago, # ^ |   +5 using long long instead of int is for the weak
 » 5 weeks 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 weeks ago, # ^ |   +57 Modified kinetic tournament? What are these mysterious words xd?
•  » » 5 weeks ago, # ^ |   -12 Could u please give some good tutorial links for the data structure.
•  » » » 4 weeks 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 weeks ago, # ^ |   +24
•  » » 4 weeks ago, # ^ |   +5 Can you share your proof?
•  » » » 4 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |   0 I get whatchu mean. In CEOI testing, I was surprised that I'm the one with readable codes.
 » 5 weeks 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 weeks ago, # ^ |   0 Can you prove that works? It looks like it doesn't (but I may have misunderstood something).
•  » » » 5 weeks 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 weeks ago, # ^ |   0 I think you are trying to apply greedy solution. It clearly doesn't work... This was solvable due to such constraints...
•  » » » 5 weeks 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 weeks ago, # ^ | ← Rev. 3 →   0 What's your answer for s = "AbccbAWpqrstW"? Important characters I have written in uppercase...
•  » » » » » 5 weeks ago, # ^ |   0 IMPOSSIBLE
•  » » » » » » 5 weeks ago, # ^ |   0 I have changed the TC... What's your answer then?
•  » » » » 5 weeks 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 weeks ago, # ^ |   0 yeah. got it. Thanks for help.
 » 5 weeks ago, # | ← Rev. 2 →   0 Can anyone please explain what S[2 : -2] means in problem editorial E?
•  » » 5 weeks ago, # ^ |   0 S[2:-2] is S except for the first 2 and last 2 elements.
•  » » 5 weeks 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 weeks ago, # ^ |   0 Got it! thanks! :)
 » 5 weeks 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 weeks ago, # ^ |   +26 ax + ay + bx + by == (a + b)(x + y)
•  » » 5 weeks 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 weeks ago, # ^ |   0 Now I got it, thank you so much)
•  » » » 5 weeks 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 weeks ago, # ^ | ← Rev. 3 →   0 For selected l and r you need 1 for loop to calculate all a's.
 » 5 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |   0 Link does not work
•  » » » 5 weeks ago, # ^ |   0 Updated.
 » 5 weeks ago, # |   0 In question E could someone explains to me why the answer would never be Impossible?
•  » » 5 weeks 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 weeks ago, # ^ |   0 Thank you :)
 » 5 weeks ago, # |   0 I need help understanding the DP in B. What is the intuition behind it? What do the a, b and c in the code mean?
•  » » 5 weeks ago, # ^ |   0 Maybe it is easy to learn./*if(s[i-1]=='v'&&s[i]=='v')num_vv++;if(s[i]=='o')num_vvo+=num_vv; if(s[i]=='v'&&s[i-1]=='v')num_vvovv+=num_vvo; */The num_vv is 'a' . The num_vvo is 'b' . The num_vvovv is 'c'.For each 'o', the number of 'vv' before * the number of 'vv' after is the number of 'vvovv' that can be formed by using this'O'.For example,the answer to "vvoovv" is 2,because there are four wows: vvo.vv and vv.ovv
 » 5 weeks ago, # | ← Rev. 2 →   0 For C, may someone please explain how 2^(w+h) was derived? Thanks.
•  » » 5 weeks ago, # ^ |   0 Work for 1-D array then add another 1-d layer to it u will see
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Ok, so it seems that the first row and column decide the rest of the entire grid. And for each of those cells there are 2 possibilities, except for the leftmost and rightmost one. That cell has 4 possibilities. How is this taken care of though?EDIT: nvm literally just figured it out. When w + h, that cell is added twice, so 2*2 = 4.
 » 5 weeks 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 weeks 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.).
•  » » » 4 weeks 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.
•  » » » » 4 weeks ago, # ^ |   0 Noted. Thanks man.
•  » » 5 weeks 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 weeks ago, # | ← Rev. 3 →   +2 An one-line solution of C using python: print(pow(2,sum(map(int,input().split())),998244353)) 57432100
•  » » 5 weeks ago, # ^ |   +90 A nice one-line solution of E: print(input()) Unfortunately, doesn't work after the checker update :(
 » 5 weeks ago, # |   0 i don't understand problem C, the solution proposed by majk isn't clear for me, somebody has another solution, please explain me
 » 5 weeks 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 weeks ago, # ^ |   0 if anyone can find the mistake , here is the code i used... http://www.ideone.com/ocV6az
 » 5 weeks 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 weeks ago, # ^ |   +10 My solution works in $O(n^{2}+m)$.
•  » » » 2 weeks ago, # ^ |   0 Thank you, got it.
 » 5 weeks ago, # |   0 can some one tell me how to use c++14 in atom ide?
 » 5 weeks ago, # |   0 Why memory limit exceeded in my solution to problem B? Code
•  » » 5 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |   0 Yes, for the bonus there are some cases in which no solution exists.
 » 5 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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...
•  » » 4 weeks 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 weeks ago, # |   0 in problem E 1st test case why cabac is not a valid solution ??
•  » » 5 weeks ago, # ^ |   0 It is.
 » 5 weeks 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.
•  » » 2 weeks 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!
•  » » » 13 days ago, # ^ |   0 Didn't realize this until now. Big thanks!!!
 » 5 weeks 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 weeks 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 weeks ago, # |   0 Can someone explain the states in problem F1-Short Colourful Strip? And how the recursive relation is being derived?
•  » » 5 weeks 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 weeks ago, # |   0 In problem C editorial code, I saw constexpr for the first time, and what I understood from GeeksforGeeks that it's something for performance improvement of programs by doing computations at compile time rather than run time. So why submitting the code[submission:57476357] that using constexpr is slower than the code 57476357 that doesn't use it!I expected the opposite
 » 5 weeks 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 weeks ago, # |   0 How to solve E if there may exist all the alphabet?
 » 5 weeks 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 weeks ago, # |   0 In problem F1, what does lowest ID of a colour used in the final strip mean?
•  » » 5 weeks 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 weeks 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.
•  » » » 4 weeks 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?
•  » » » » 4 weeks 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)
 » 2 weeks ago, # |   0 In problem D how i↔i+n2 this work ? Can anyone explain ?