### isaf27's blog

By isaf27, history, 10 months ago,

The problems A, C, D, G are authored and prepared by isaf27.

The problems B, E, F are authored and prepared by 300iq.

• +315

 » 10 months ago, # |   +21 Thanks for the fast editorial ! :)
 » 10 months ago, # |   0 Thanks for Editorial giving so fast
•  » » 10 months ago, # ^ | ← Rev. 2 →   +10 Why do you have so many down votes? QwQit's the same words as the first one who got 14 up votes...
•  » » » 10 months ago, # ^ |   0 Maybe only the first person has the right to thanks for the fast editorial. (laughing
•  » » » » 10 months ago, # ^ |   0 or maybe only the first one has the right to thank for a fast editorial :3
•  » » » 10 months ago, # ^ |   +45 Its because first one is Candidate Master ,and he is a Newbie..Accept or not but ratism do exists.
•  » » 10 months ago, # ^ |   0 whats up with the down votes
 » 10 months ago, # |   -12 Nice Contest,Wish Every One good rating!
 » 10 months ago, # |   0 For the jury solution of D, on line 41, shouldn't the substring be from L to size — L, not from L to size — 2 * L?
•  » » 10 months ago, # ^ |   +38 In the C++ substring function, the arguments are (start index, length), not (start index, end index). Since we trim a prefix and a suffix of length L from the string, the length should in fact be size — 2 * L.
 » 10 months ago, # | ← Rev. 2 →   0 somebody care to explain D2 problem
•  » » 9 months ago, # ^ | ← Rev. 4 →   0 Let me try: start i from 0 and j from n-1 in the reverse direction. Now, while s[i] == s[j]: i++, j--; When s[i]!= s[j] stop. You already have one(may be not optimal yet) solution: it is tm = s[0, to i-1] + s[j+1 to n-1];Now start searching for a palindrome either from i up to j. Or from j up to i. Attach it in between your solution and you have your answer.Let us call string from i to j as 'a':The problem reduces to: find the longest palindrome which is a prefix of string 'a' (and do the same for reverse of 'a').You need to study KMP. Build the pie table of the string a + '#' + reverseof(a). Pie table's last value is the len of your string which is a palindrome and also a prefix of 'a'. Repeat this process for reverseof(a). You are done. Here is my submission: 77356255
 » 10 months ago, # |   +26 can anyone give me detailed explanation of E?Thanks in advance!!
•  » » 10 months ago, # ^ |   +83 I get the conclusion in the tutorial by Hall Theorem during the contest.This is my understanding: To check whether answer is $x$, we consider the largest $n-x$ number, and link edges to the bombs on it right, so we need to check whether there is a perfect match. According to Hall Theorem, every subset of these number $A$, and it links bombs set $B$, $|A| \le |B|$. Actually, we do not need to check all the subset, we only need to check all the suffixs, and this is the conclusion in the tutorial. And you can see, if all the suffixs satisfy this condition, all the subset also satisfy it.
•  » » » 10 months ago, # ^ |   +1 Can you please give some detail into how actually segment trees can be used to check the condition? I mean what are we actually maintaining in the nodes and how are we using it?
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   +6 The check condition is:There is at least $1$ bomb after the rightmost value which is $\ge n - x$.There are at least $2$ bombs after the next rightmost value which is $\ge n - x$....There are at least $x$ bombs after the $x$-th rightmost value which is $\ge n - x$.So each of the key position $p$ whose value is $\ge n-x$ should satisfy that the number of suffix key position is larger than the number of suffix bombs. We minus these two suffix sum, and in each node of segment tree, we actually maintain the number of suffix bombs minus the number of suffix key position.When we add a bomb at $q$, all the value in $[1, q]$ should $+1$. When we try to add a key position $p$, all the value in $[1,p]$ should $-1$. And if some position's value is negative, check failed. So we only need to maintain global minimum.
 » 10 months ago, # |   0 Can anyone please give a detailed explanation of D? Thanks.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 I divided question into two parts 1.Till how much prefix and suffix are same2.Using manchers algorithm find longest palindrome at each pointThen for each index check if it touches with common prefix points and it's your solution.My Solution — 74734509
 » 10 months ago, # |   0 Can someone explain the given solution for 1326D2 — Prefix-Suffix Palindrome (Hard version). For example, if the input string is "xkcddckyyx", the answer should be "xkcddckx" a="xkcddck" and b="x", can somebody explain how you will reach the value of 'k' ( k is given in the solution above) here?
•  » » 10 months ago, # ^ |   +12 First try understanding that for every $x <= k$, the string $s[1..x]$ is equal to reverse of string $s[n-x..n]$, and for any other $x > k$ the string $s[1..x]$ is not equal to reverse of string $s[n-x..n]$. So that lets iterate over $i$ from 1 to $n/2$, if the strings were equal, then $k >= i$, otherwise $k < i$, it can be done in $O(n)$, if $s_i == s_{n-i+1}$ then just continue iterating, otherwise break the loop, $k$ will be the biggest $i$ before breaking.Now we have $k$, try finding maximum palindrome prefix and maximum palindrome suffix using prefix-function(or hashing) on string $w = s[k+1..n-k] + "*" + rs[k+1..n-k]$, where $rs$ is the reverse of string $s$.
•  » » » 10 months ago, # ^ |   +3 And would you please explain the prefix function?
•  » » » » 10 months ago, # ^ |   +15
•  » » » » 10 months ago, # ^ |   +23 For this algorithm, i really recommend cp-algorithm, the site is very useful in lots of competitive programing topics, specially it's prefix-function. I used the same code as cp-algorithm in my solution.
•  » » » » » 10 months ago, # ^ |   0 Same;)
•  » » » » » 10 months ago, # ^ |   +3 Thanks for the link ! but there is no explanation for why the complexity is O(n). Would you explain it ?
•  » » » » » » 10 months ago, # ^ |   0 I did the same question with Z-function, you can see its asymptotic behavior (proof) of O(n) in this blog — https://cp-algorithms.com/string/z-function.html
•  » » » » » » 10 months ago, # ^ |   +8 Let me explain why its $O(n)$, first you should know that the prefix-function wont increase more than 1 each time, i mean there is no $i$ such that $pi_{i+1} > pi_i+1$, the value names came from cp-algorithms implementation. So $pi$ will increase at must 1 in each step, so the maximum number of increases we can have is $n$, so we cant decrease our value more than $n$ times at most, because we have to keep them non-negative and $pi_1$ is zero and also $pi$ increase at most 1, then for $i$ such that $pi_i$ is grater or equal to $pi_{i+1}$, we have to perform 1-2 action(s), but for $i$ such that $pi_i > pi_{i+1}$, we have to perform more than 2 actions(at most $pi_i - pi_{i+1}$ actions), as i said above, we cant decrease more than $n$ times(i.e sum of $pi_i - pi_{i+1}$ over every $i$ in range $1..{n-1}$ is at must $n$. So we have to perform at most $O(n)$ actions.
•  » » » » » » » 10 months ago, # ^ |   0 nice, thank you so much, I've learnt it !
•  » » » » » 10 months ago, # ^ |   0 Could you please tell where my code fails i am not able to debug it :( https://codeforces.com/contest/1326/submission/73832292
•  » » » » » » 10 months ago, # ^ |   0 UPD : Found it , error in prefix function XD
•  » » » » 10 months ago, # ^ |   0 You can find an extensive explanation for prefix function here : https://youtu.be/nJbNe0Yzjhw
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 w = s[k+1..n−k] + "∗" + rs[k+1..n−k] What is the use of "*"?
•  » » » » 10 months ago, # ^ |   +3 Split the string into two part, after the operation, there will not exist a palindrome cross two independent parts.
•  » » » 10 months ago, # ^ |   0 How to prove that it is optimal to take such k and then find longest palindromic prefix on remaining string. I don't understand statement from editorial.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 deleted
•  » » » » 10 months ago, # ^ |   +3 For example: string s: "aybxpbtdtbya" if you choose prefix:"ay" and suffix:"ya" then take the suffix string:"btdtb" from the remaining string:"bxpbtdtb"then you can see that if you choose prefix:"ayb" and suffix:"bya" then take the suffix string "tdt" from the remaining string:"xpbtdt"the results are same. so you can simply choose the same character from the prefix and suffix and it has no effect to the answer
•  » » » 10 months ago, # ^ |   0 Thank you I understand and appreciate
•  » » » 10 months ago, # ^ |   0 can you tell me why doesn't it works if we set w = reverse(s) and why it works when we set w = s + "#' + reverse(s) ?
•  » » » » 10 months ago, # ^ |   0 For example when $s = "aaaaaa"$, then we use a character(like '#' or '*') to limit the prefix-function.
•  » » » » » 10 months ago, # ^ |   0 what do you mean by limit the prefix function? what my understanding is we are using delimiter to reset the matching count to 0 and start matching on the reversed part of string. so can't we just set s to reverse(s)?
•  » » » » » » 10 months ago, # ^ |   0 No we cant.
•  » » » » » » » 10 months ago, # ^ |   0 how does it effect the solution?
•  » » » » » » » » 10 months ago, # ^ | ← Rev. 3 →   0 I am not sure but I hope I am correct:For example when s="aaaaa" using aaaaaaaa will make the answer 8 using aaaa#aaaa will make the answer 4
 » 10 months ago, # |   0 In the third question, the explanation for the third test case seems to be wrong which was quite confusing.
•  » » 10 months ago, # ^ |   +1 What is wrong about it? Are you sure you just don't misunderstand the explanation?
•  » » » 10 months ago, # ^ |   0 yeah right. sorry, I misunderstood.
 » 10 months ago, # |   0 May be its too basic, but I couldn't understand the mathematics behind solution of problem A. Can anyone explain how this works? I know this solution will work but unable to know how to come up with this solution
•  » » 10 months ago, # ^ |   +3 We will form the number with just 2s and 3s, For a number to be divisible by 2, it should have 2 at the end. So we will keep 3 at the end. Thus it is not divisible by 2 now. For a number to be divisible by 3, its digit's sum should be divisible by 3. So sum of digits of our number is of the form 3k + 2, which can never be divisible by 3 for any value of k.
•  » » 10 months ago, # ^ |   +11 It's probably just some guess work. The way I thought about it is that instead of thinking of a lot of digits, why can't we just have a lot of digits which keep repeating? This highly simplifies your solution space. So suppose your number has only one digit, let's say a; then your number is aaaa....aaa but in that case, it is divisible by a. That means, we should think of having two digits in the number. Clearly 1 can't be a digit. What else do we have? If we take 2 as one of the digits, the other digit can be 3(as in the solution) or 5 or 9. I hope this gives you some form of intuition in regard to the problem.
•  » » » 10 months ago, # ^ |   0 AdsT, daman1209arora, Thank you very much for the explanation. Now it's more clear
•  » » 10 months ago, # ^ |   +3 233...33, is not divisible by 2 as number must end with 2 to be divisible by 2 and number is also not divisible by 3 as the sum of digits is never gonna divisible by 3 as it always short by 1 number.
•  » » » 10 months ago, # ^ |   +18 55555(n-1 times)8(1 time) also works.
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   +5 999...98 works as well
•  » » » » 10 months ago, # ^ |   0 5555(n-1 times)4(1 time) works too :)
•  » » » 10 months ago, # ^ |   0 33....38 works too.
•  » » 10 months ago, # ^ |   +3 There is another AC solution. We just need to write n-1 times ‘9’ and at the end we should write ‘8’. Why this works? Because of rule of divisor 8 (find it yourself, my English level not good enough to explain my thoughts).
•  » » 10 months ago, # ^ |   +3 I intuitively think it's OK to just choose an odd number and an even number. For example, "2.... 3" or "4.... 3" or "5.... 8" or "8.... 9". Can anyone prove it?
•  » » » 10 months ago, # ^ | ← Rev. 2 →   +10 3 out of the 4 you gave are counterexamples lol2223 % 3 = 0, 4443 % 3 = 0, 8888888889 % 9 = 0ending in 3, 6, and 9 all don't work cus of the same reason :(
•  » » » » 10 months ago, # ^ |   +2 They aren't counter examples 23333 43333 89999 Just repeat the other digit.
•  » » » » » 10 months ago, # ^ |   0 Yes, I think so. But I don't have enough mathematical knowledge to prove that it's right, so it's my guess.
•  » » » » » » 10 months ago, # ^ |   0 oh my bad, then ending in 3, 6, and 9 will always work, since the sum of digits will have a nonzero remainder mod 3, unless the first digit is also divisible by 3ending in 1, 2, 4, 5, and 8 don't work and idk about 7
•  » » » » » » » 10 months ago, # ^ |   0 It will work with 7 also. 27777777 47777777 87777777
•  » » » » » » » 10 months ago, # ^ |   0 ending with 4 also works. Divisibility Test of 4:Let a number $N$ represent in digits as follows: a[1] a[2] a[3].... a[k-1] a[k];then $N$ is divisible by 4 if and only if 10*a[k-1] + a[k] is divisible by 4Thus Numbers ending with 14, 34, 54, 74, and 94 are not divisible by 4. Now repeat any odd digit and that's the answer.
•  » » » 10 months ago, # ^ |   0 Not really true, what about "2.... 5"? 2 is an even number, 5 is an odd number, but "25" doesn't work (it's divisible by 5).
 » 10 months ago, # |   0 Can someone pls explain how the second part of problem C is done?? i mean why ai+1-ai works here in finding number of segments?
•  » » 10 months ago, # ^ |   +14 Let's denote the places of the largest elements by stars, and the other elements by dashes. For example, it might look like: --*--**--*- Then our goal is to count the number of ways to add dividers that split up all the stars. For example: --*-|-*|*--|*- The i-th divider must be between $a_{i}$ and $a_{i+1},$ so it has $a_{i+1}-a_i$ places it can go. The choices for all dividers are independent, so we multiply all these numbers together.
•  » » » 10 months ago, # ^ |   0 Hey 1-gon, thanks for the solution, that is pretty intuitive! Would you suggest similar problems as Div2C for the above one?
•  » » » » 10 months ago, # ^ |   0 Look at problems with the combinatorics tag and difficulty 1000-1500.
•  » » 10 months ago, # ^ |   +8 Lets first solve the following problem, you have $n$ different eggs in a row, you want to take a prefix from eggs(probably empty or all eggs), how many ways you can choose the prefix?, lets say that we want to choose a border and then our prefix is the eggs in the left of the border(border is just a stick between two eggs or before or after all eggs), you can choose the border in $n+1$ ways.Now go back to the problem $C$, its easy to see that every segment must have exactly one number bigger than to $n-k$, so lets change it a little bit, we want to find exactly $k-1$ borders, such that first border is between $a_1$ and $a_2$, second border is between $a_2$ and $a_3$ and so far, what you think the answer will be?($a_i$ is $ith$ number in the array which is bigger than $n-k$), choosing border are independent, there is exactly $a_{i+1} - a_i$ ways to choose $ith$ border.
 » 10 months ago, # |   +5 I don't understand why, but problems B, C and D1 were much more intuitive to me than A was.
•  » » 10 months ago, # ^ |   0 Yeah! about that, the more one thinks the harder it gets. These first questions are really surprising these days.
 » 10 months ago, # | ← Rev. 2 →   +15 I have slightly different approach for problem E which does not use observation in the editorial. First how to check that the answer is at least $x$? Let $a_i = 1$ if $p_i \ge x$ and $0$ otherwise. To check it in linear time go from left to right maintainng $cnt_1$ — current number of ones. If $a_i=1$ increment $cnt_1$ by one. If there is a bomb in the $i$-th cell do $cnt_1 = max(cnt_1 - 1, 0)$. If $cnt_1 > 0$ at the end then the answer is at least $x$. To solve original problem maintain current answer which equals to $n$ at the beginning, and you have two type of events : assign $a_i = 1$ and put a bomb in some cell. You can do it with segment tree storing for each node $cnt_1$ — the number of ones left at the end if we will go through this segment and $cnt_0$ — the number of times there was a bomb but there was not a one($cnt_1 = 0$). With this data we can calculate desired $cnt_1$ at the end. And as answer never increases at the beginning of each iteration decrease current answer until $cnt_1 > 0$ at the end and at the end of each iteration do an update of the bomb.
•  » » 10 months ago, # ^ |   +11 Your solution is very intuitive. Thanks a lot. I noticed that bombs could be modeled as ')' and numbers greater than current ans i.e 1s as '('. Now this question is similar to regular bracket sequence. I was getting WA earlier as I was using -1 for bombs earlier. But this bomb cancels even numbers on the right. Hence we needed to maintain two values in the segment tree.
•  » » 7 months ago, # ^ |   0 AleksanderBalobanov, can you provide a link to your submission? I'm having trouble understanding how the segment tree is maintained. Specifically, what information is stored at each index?
•  » » » 7 months ago, # ^ |   0 Here's my submission 73741605. To calculate amount of ones left at the end we should also store another value — the number of times there was a bomb but there was not a one. We should do it because we do not decrease number of ones if there are no of them. So we store these two values in every node of the segment tree. And with this information we can calculate these values in the node using values in it's left and right child. You can see how to do it in my code. Ask if you have questions.
 » 10 months ago, # | ← Rev. 3 →   +73 There is a beautiful solution to problem E using partial retroactive priority queues. In a partial retroactive priority queue, it is allowed to perform five types of operations: Insert / Delete a Push(x) operation at time t; Insert / Delete a Pop() operation at time t; Get the smallest element inside the priority queue at present time. Demaine describes in the following article how to implement a partial retroactive priority queue in $O(\lg n)$ time per operation.So, you can Push all values $p_i$ inside the data structure at time $i$ and, after each bomb, insert a Pop operation at time $q_i$.If you want more details, you can see my code herePs. Thanks to Kallaseldor for the idea to solve the problem using retroactive priority queue
•  » » 10 months ago, # ^ |   -31 despite of partial retroactive priority queue, can you tell me which algo i need to know to solve E as a beginner
•  » » » 10 months ago, # ^ |   +8 read the editorial?
 » 10 months ago, # |   0 Wy this submission My submission to problem D2 gives TLE if the complexity is O (n)
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Instead of doing this p = p + s[i]; pp = s[j] + pp; Try doing this : p += s[i]; pp += s[j]; reverse(pp.begin(),pp.end()); Cuz the above operations takes O(|p|) each time you add a character, but the this method appends the characters into string taking O(1) each time you add a character to string.
•  » » » 10 months ago, # ^ |   0 I thought the operation y = s [j] + y was O (1). Thank you very much I still did not find the error and it cost me 13 TLEs in the competition and in the end I could not accept it.
 » 10 months ago, # |   +8 Could someone point out the idea behind solving F1 (that won't work for the harder version)? Thanks.
•  » » 10 months ago, # ^ |   +3 For example this 73757219 naive recursion with memoization. calc(mask, last) calculates the answer for the rest of the men (given by mask) with last being currently the last man in the sequence. Complexity seems to be O(n*2^(2n)) with a good constant.
•  » » » 10 months ago, # ^ |   +6 I guess it is more like $\sum\limits_{k=0}^n {n \choose k}2^n$ which adds up to $3^n$, or at least this is number of states (for each $k$ there are ${n \choose k}$ sets of $k$ men and $2^k$ possible sequences so far), time complexity might be times $n$ because transitions are in $O(n)$
•  » » » » 10 months ago, # ^ |   0 You are right, thank you.
•  » » 10 months ago, # ^ | ← Rev. 4 →   +11 I ran through all of the partitions of the people by two (almost) equal groups (there are C_14^7 of them, it's around 3500).For the first half of every partition I pre-counted d[fin][res] – the number of ways to go through this half stopping in fin and getting a result mask equal to res.For the second half of every partition I pre-counted d[start][res].Now you can go through all of the partitions, but also through all of the end and start points and all of the result masks in every half. It works in #(partitions) * 7 * 7 * 2^6 * 2^6.It's too long. So we also need to pre-count d[start_mask][res] for the second half of every partition. Here start_mask is a set of vertices where you can start.Now once you fixed a fin you don't need to go through every start. You just need to look at the set of adjacent to fin and the set of all others. This will work in #(partitions) * 7 * 2 * 2^6 * 2^6 and gets AC.
 » 10 months ago, # |   0 In Question D2"In order to find the longest palindrome which is a prefix of some string, a, let's find p from the prefix function of the string a+ '#' +a¯, where a¯ represents the reverse of a."Could someone please explain what this means.Thanks
•  » » 10 months ago, # ^ |   +6 We want to find the longest prefix which is also a palindrome, lets call it string $a$(the longest palindrome prefix). What do we do now?, we use prefix-function(prefix-function is an algorithm which can find the longest prefix of a string, which is also a suffix of the string and is not equal to the string itself, in $O(n)$, you can find it in cp-algorithms). Then lets run prefix-function on string $s[k+1..n-k]+"|"+rs$, where $rs$ is reverse of string $s[k+1..n-k]$.Why the prefix-function's return is the longest palindrome prefix?, you can understand it yourself!!
 » 10 months ago, # |   0 KMP O(n) solution (Longest palindromic prefix)https://discuss.interviewbit.com/t/kmp-o-n-solution-longest-palindromic-prefix/29112Can someone please explain the logic behind the code. Thanks!!
•  » » 10 months ago, # ^ |   +1 Suppose the string $S=AB$, where $A$ is a palindrome. Then the code computes the KMP array for $S\text{#} S'=AB\text{#} (AB)'=AB\text{#} B'A.$ Note that $A$ is both a prefix and a suffix of the string, and the KMP array computes the longest proper prefix that is also a suffix. That is, the last KMP array value will be at least the length of $A$.Conversely, suppose we have the longest prefix that is also a suffix of the string $S\text{#}S'.$ Clearly, it cannot contain the $\text{#}$, because it does not appear elsewhere in the string. So, we have the longest prefix of $S$ that is a suffix of $S'$. But these are just the same characters in reverse order, so we must have a palindrome!
 » 10 months ago, # | ← Rev. 4 →   0 How does CF compile c++14?I submited problem DOn test2:case input: qReal Ouput: qq my ouput: q\$q. But on my pc my output was like the real output "qq"I didn't realize that mistake 'til, I saw the real test after contestHelp me pls.
•  » » 10 months ago, # ^ |   +6 Probably your solution on your machine didn't output just "qq", but "qq" and did the same on the server, which is not considered a correct answer. And if not then you have some type of undefined behaviour.
•  » » » 10 months ago, # ^ |   0 thank you for the information. I'll be careful next time when coding
 » 10 months ago, # |   0 Can somebody tell me all the various ways of solving D2? I used string hashing, editorialist used prefix function, did anyone use any other method too?
 » 10 months ago, # |   0 Isn't 2222...29 also a possible solution for Ugly Bad Numbers?
•  » » 10 months ago, # ^ |   +14 No if $n-1$ is divisible by 9
 » 10 months ago, # |   +20 Case 3 of G: Furthermore, the last edge on the path from $i_x$ to $i_{x+1}$ must equal to the first edge on the path from $i_{x+1}$ to $i_{x+2}$.
 » 10 months ago, # |   0 I don't know why a manacher alogrithm for D2 which should be O(n) get TLE. Does anyone know the reason or got AC by using it? Thank you.
•  » » 10 months ago, # ^ |   +16 Could the problem be: memset(f,0,sizeof f); since it is resetting the entire array for every single test case?
•  » » » 10 months ago, # ^ |   0 I haven't considered of such problem.You are right. Thanks a lot。:)
 » 10 months ago, # |   0 Can someone tell me the dp approach to solve D (dp is mentioned in tags, but I am having a hard time finding dp approach for this.)
 » 10 months ago, # |   0 Sorry to bother, but why my O(n) solution in problem B got TLE in the system test but got AC just now when I submitted exactly the same code? Could somebody please tell me the reason? Thx a lot. 73666334 73748630
•  » » 10 months ago, # ^ |   +14 There isn't much difference between 982ms and 1000ms. Expect ~30ms difference. It may be due to overload on servers at that moment etc.... You soln is O(n) but input/output takes too much time here. It's close to 2MB (2^21 chars). I added this line for fast input output in your code and it runs in 124ms. 73749515 Fast Input Outputios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
•  » » » 10 months ago, # ^ |   0 Yeah thx now I get it and will be careful next time. Hope they could rejudge this submission but it's kind of unrealistic. SO SAD :(
•  » » 10 months ago, # ^ |   +2 My code is similar to yours, but mine runs fast at the forth test case 73756081. Why your solution runs so slow is mainly because input/output takes too much time, as @aryanc403 said. In my code, output here is independent: rep(i, 1, n) cout << a[i] << " "; This will take advantage of IO buffers, which makes the compiler happy. To verify my conclusion further, I edited your code to become four versions. The first is your original code: cin >> n; rep(i, 1, n) { cin >> x; ll now = x + ma; ma = max(now, ma); cout << now << " "; } cout << endl; It costs 826 ms at the test#4. 73757350I add flush after cout << now << " "; in the second one. It costs 857 ms at test#4. 73757273I extract the output part to make it independent in the third version, like my code. It costs 529 ms at test#4. 73756448In the fourth version, I flush the IO stream after each outputs, in the basis of the third version. It costs 841 ms at test#4. 73756516It is found that independent IO without flush runs fast, but with flush runs slowly; the in-independent IO without explicit flush runs slow, as well as the in-independent IO with explicit flush runs slowly.It is shown that the in-independent IO runs flush implicitly, the independent IO does not run flush unless you specified explicitly. I guess the reason for the former is that there are both input and output in the for-loop, which makes the IO stream flush quickly.Could someone who is familiar with the internal working mechanism about iostream in C++ tell me more? Thanks a lot.
•  » » » 10 months ago, # ^ | ← Rev. 3 →   0 flushing the buffer is slow, so you shouldn't use endl for newlines (if there are a lot of them) because they flush. Instead use '\n'. Also adding ios::sync_with_stdio(0); cin.tie(0); at the beginning of your main function will make input faster. I think the input is the problem in your code because mine looks similar and it runs in <200ms.
 » 10 months ago, # | ← Rev. 2 →   +3 The largest bloody lesson I learned from this contest is to use two primes to hash instead of just one prime.My D2 get WA during system test due to hash collision.I was able to be in 500th and join the T-shirt lottery but now my rating even drops...So sad Orz
•  » » 10 months ago, # ^ |   0 I don't think so. You use 30 and 30 is not a prime.
•  » » » 10 months ago, # ^ |   0 Because I treat every character as a digit, made the string a base 30 number. 30 is not the prime I use for hashing.The hash trick is $h(i)=num(s_1...s_i)\%MOD$, where $MOD$ is a prime.
•  » » » » 10 months ago, # ^ |   -7 I have never seen someone use a non-prime as base for string hash...
•  » » » 10 months ago, # ^ |   0 BTW I got AC using double hashing.
•  » » » » 10 months ago, # ^ |   +3 You can use a prime as base, it will AC: https://codeforces.com/contest/1326/submission/73752592
•  » » » » » 10 months ago, # ^ | ← Rev. 2 →   +4 I think using any number as base is basically the same, as long as you don't use a base that smaller than 26. Since every string converts to number is a unique value, using a prime as base or not shouldn't affect the probability of collision.I think I'm just unlucky that can't get passed with single hashing...Still, your code seems better than mine. I could learn a lot from your code. Thanks a lot anyway :)UPD: got AC using single hash and I personally think its prettier: https://codeforces.com/contest/1326/submission/73767232
•  » » » » » 10 months ago, # ^ |   0 I have one doubt.I tried to submit by using primes as base, but I was surprised to se that taking bases as 29 and 31 failed system tests, but prime no. like 53, 103 and others were passing.Is it entirely based on luck if we use single hashing.Also if we take mod as 1e9+7 with base 31, it fails but if we take mod as 1e9+9 it passesIt will be very helpful if you can clarify this to me
•  » » » » » » 10 months ago, # ^ |   0 That's because of hacks against those specific hashes.
•  » » » » » 10 months ago, # ^ |   0 It will... With about 80-90% chance(depending on how the tests are made). That 10-20% chance made me get WA in contest which made me miss out on top 30...
 » 10 months ago, # | ← Rev. 3 →   +42 A Permutationforces round.
 » 10 months ago, # |   0 why is the editorial of D2 not given?
•  » » 10 months ago, # ^ |   0 *D1
 » 10 months ago, # |   0 My solution for C was failing on pretest 5. Has any1 faced the same problem?
•  » » 10 months ago, # ^ |   +5 maybe you forgot to module 998244353?
•  » » » 10 months ago, # ^ | ← Rev. 2 →   -7 No, I did it.Here is my code.#include using namespace std;#define MOD 998244353int mul(int x, int y){ return (x*1ll*y)%MOD; }int main() { int n,k; cin>>n>>k; int a[n]; for(int i=0; i>a[i]; int sum= n*k — (k*(k-1))/2; cout<=(n-k+1)){ if(j>0) num=mul(num,count+1); j++; count=0; } else count++; } cout<
•  » » » » 10 months ago, # ^ |   +1 $k, n\leq 200,000$ $k\times n\leq 4\times 10^{10}$
•  » » » » » 10 months ago, # ^ |   0 thanks, got it
•  » » » » » » 10 months ago, # ^ |   0 I had the same problem..could you tell what the issue was and what you did to rectify the problem(test case 5)?
•  » » » » » » » 10 months ago, # ^ |   0 I initialized sum,n and k as long long int instead of int . As the product of n and k can be out of int's range.
•  » » » » » » » » 10 months ago, # ^ |   0 Thank you I got it.
•  » » 10 months ago, # ^ |   0 store in long long maybe or wouldn't have taken mod. Check this out https://codeforces.com/contest/1326/submission/73709693
 » 10 months ago, # |   -44 Useless editorials
 » 10 months ago, # |   +4 I like this editorial. It's great.
 » 10 months ago, # |   -92 Why do they give mod = 998 244 353 instead of 1e9 + 7 ?? Got 3 wrong submissions because of that !!! And if they do ...they should have highlighted that !!
•  » » 10 months ago, # ^ |   +36 The number 998 224 353 appears three times in the problem and it is long and strange enough for you to discover it.
•  » » 10 months ago, # ^ |   0 By doing this, if some problem of the contest uses NTT, the modulo won't give it away.
 » 10 months ago, # |   +1 Trie Solution for D1 Link to solution Approach :- Insert all suffixes in Trie and iterate over all prefixes and search if whole prefix or some part of it is present in Trie and return it's length. If length of suffix is equal to length of prefix then you find one solution and update answer. If it's not then for the remaining part of the prefix which is not found in the suffix of Trie check whether it it is palindrome or not. If it is update the answer. Same you do with suffixes and insert all prefixs in another Trie. Do the same thing. Complexity :- O(n^2) (For every prefix or suffix you will iterate at max it's length.) Though a little long solution but it just clicked in the contest so I wrote it and was accepted.
•  » » 10 months ago, # ^ |   0 thanks bro
 » 10 months ago, # |   -10 For bad ugly numbers, I used this approach:if n-1 is divisible by 3: answer= 2222....2233Otherwise answer = 222...223
 » 10 months ago, # |   0 If someone can explain approach of question D2 in simple words it would be great help
•  » » 10 months ago, # ^ | ← Rev. 4 →   +9 Summary Find the longest matching prefix and suffix, where suffix = palindrome(prefix) Find the longest inner substring that is a palindrome and touches the prefix or suffix (or both) Combine these as final answer Steps From both ends of the string, find a prefix and suffix that are mutual palindromes. Store that for the final answer Strip off these matching prefix and suffix (if any) so you're left with just the inner string Run Manacher's algorithm on the inner string Using the output from step 3, find the max value (i.e. max palindrome length in inner string) that touches the prefix or the suffix (or both). Return [prefix] + [longest internal palindrome that touches either prefix or suffix] + [suffix] Manacher's Algorithm This algorithm finds all palindromes in the string in O(N). It treats each index as a "center" and finds the "radius" (or half length) of the palindrome around that center. It stores this radius for each index in the string. For instance, for "aba", the values returned would be [1, 2, 1] The algorithm starts off with a brute force palindrome search (i.e. from the first point, expand linearly in both directions to see how far the palindrome stretches). Then for the next point, first re-use pre-computed information, if that exists. Then continue linearly expanding to see how much further the palindrome stretches. Store this palindrome length ("radius") for that index. The key observation that's used here is that if the current index lies to the right of a known palindrome and falls within that palindrome's range, then you can simply copy over the pre-computed values from the left half to the right half, and then continue expanding on the right to see how much longer the palindrome on the right stretches. This is because the left half is an exact mirror image of the right. For eg. if the string is "abcdcba", then since we have a palindrome around "abc[d]cba" and both b's fall within its radius, palindrome_len("abcdc[b]a") = palindrome_len("a[b]cdcba") + {any additional palindromic text to the right} Side observation: it's sort of a DP equivalent approach where for any index, you first read what has been partially pre-computed (by virtue of the current index falling under the radius of a prior index), then manually expand beyond that, then save that value, then repeat for next index. References
•  » » » 10 months ago, # ^ |   +1 Thanks a lot buddy ! Really it was amazing video and tutorial provided by you was quite helpful!!! :)
•  » » » » 10 months ago, # ^ |   0 Sure thing! I've edited it further with an example, and some more clarifications.I had a tough time with the last contest (misinterpreted C and spent all my time trying to oversolve it), so I made it a point to try and upsolve a few of the other problems that I wasn't able to get to. D2 required a fair bit of reading to understand how Manacher's algorithm worked, so thought I'd share my notes here for the benefit of anyone who has not heard of this algorithm before. If anyone sees a more efficient way of doing this, I welcome your feedback.I've skipped a few details for readability. for eg. there's multiple approaches to it too — you could compute both manacher_odd and manacher_even indexes and use that, or you could modify the input string to insert a special character (for eg. "*") before and after every character in the string, and then do a single manacher run on it (which is what I have used in my input).I'm sure there are other ways to find the longest palindrome for D1/D2 (for eg. someone suggested a prefix method?) When I went through submissions of many of the top contestants, they had used manacher, but obviously the other approaches work just as well.
•  » » » 10 months ago, # ^ |   0 osm bro we need this
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 can you please help me understand why this (https://codeforces.com/contest/1326/submission/73942810) is giving wrong answer?
•  » » » » 10 months ago, # ^ |   0 I'm not familiar with the prefix function (I used manacher's algorithm instead), but the editorial uses that, and it says:In order to find the longest palindrome which is a prefix of some string, a, lets find p from the prefix function of the string a + "#" + reverse(a)Are you setting the string accordingly before you send it to the prefix function? Note that you'll need to repeat this for the suffix (per the editorial).
•  » » » 9 months ago, # ^ |   +1 Helped me a lot, thanks brother!!
•  » » » 9 months ago, # ^ |   0 if(i-radius[i]+1 <= 0 || i+radius[i]-1 >= n-1)can u plz explain this line?? thank u
•  » » » » 9 months ago, # ^ |   0 This is when you're trying to find the longest inner string that is a palindrome and also touches the outer string. Let's say the original string was abcdedxcba. Here the outer string will be abc...cba. Then you want to find the largest inner string that touches either the initial abc part or the latter cba part. So we run manacher's on dedx and find that ded is the longest inner palindrome that touches the abc portion of the outer string. This is because at i=1 (i.e. at the character 'e'), radius[i]=2 (and hence i-radius[i] + 1 = 0).
 » 10 months ago, # |   0 Can somebody please explain the perfix function in problem D2??
•  » » 10 months ago, # ^ |   0 You can check out prefix function here : https://youtu.be/nJbNe0Yzjhw
 » 10 months ago, # |   0 Can someone please explain the problem C.not getting actual the problem asking for?? :( tnx in advance
 » 10 months ago, # |   0 Please anyone give the brute force solution for D1...mine solution got TLE at test 6 73771787
 » 10 months ago, # |   0 can someone help me finding the mistake in my logic for problem E. I did similar thing as mentioned in editorial.After putting ith bomb 'ans' will be valid if for every index 'j' after 'position[ans] in array p' the number of bombs in prefix(starting from position[ans]) <= # elements greater than 'ans' till j — #elements greater than 'ans' till the previous bomb position just before poition[ans].I implemented it but got WA on TC-4. Can someone please find the mistake? Code: https://codeforces.com/contest/1326/submission/73769004
 » 10 months ago, # | ← Rev. 3 →   -16 It's really sad to get the result that I failed on System Test 32 in D2 using hashing. I use base=233,mod=998244353 in my hashing. I tried to modify the base or mod, both can get accepted. It seems that the test kills the hashing with base=233,mod=998244353. :(Anyway D is really a great problem. I was writing a messy code using manacher algorithm in contest before I realized it can be solved with hashing. It takes me a long time. Sorry for my poor English.
•  » » 10 months ago, # ^ |   +10 with base=29 and mod=1e9+7 my solution failed for test case 104, I then modified my mod to 998244353 and it passed.
•  » » » 10 months ago, # ^ |   +10 Your words make me not feel alone. :)
•  » » 10 months ago, # ^ |   +10 The same happened for lots of people, for example my friend davooddkareshki, it seems that it was kind of anti-hash test cases.
•  » » » 10 months ago, # ^ |   0 Maybe. Use hashing with 2 kinds of mod is more important than the time used to solve the problem. I just don't want to write more at that moment (since I have spent too much time on it) and get the FST. :( It teaches me a lot.
•  » » » » 10 months ago, # ^ |   +10 You can get hacked even with 2 different mods if you're unlucky enough to be in the same room as someone who knows how to do that.
•  » » » » » 10 months ago, # ^ |   0 You're right. I heard of it before. So must we use hashing with 3 mods？
•  » » » » » » 10 months ago, # ^ |   +10 No. Even that can be hacked if you don't randomize your base and modulo. You should make your base(s) random.
•  » » » » » » » 10 months ago, # ^ |   0 So the hack needs the code's modulo, base or both?
•  » » » » » » » » 10 months ago, # ^ |   +10 Both.
•  » » » » » » » 10 months ago, # ^ |   0 thx. I just have heard that it can be hacked with one mod without knowing base before. So, how to hack the hashing with 2 bases and mods? Can you teach me?
•  » » » » » » » » 10 months ago, # ^ |   +10
•  » » » » » » » » » 10 months ago, # ^ |   0 thx.
•  » » » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 Like that blog said, you shouldn't use time(0). Currently I can't hack you because for some reason the judge has stopped working(though definitely expect to be hacked when it's working again).
 » 10 months ago, # |   +4 Can anyone share similar problems to D1/D2 related to string searching? It would be really helpful for beginners to practice on this topic.Thank you!
•  » » 10 months ago, # ^ |   +10 Try this 471D
 » 10 months ago, # | ← Rev. 2 →   0 For 1326A — Bad Ugly Numbers, as the solution of the editorial if n = 13 then the output comes 2333333333333. But it is divisible by 3, which doesn't fit those conditions. Then isn't the solution wrong?
•  » » 10 months ago, # ^ | ← Rev. 2 →   +3 How can a number ending on $3$ in decimal representation be divided by $2$?
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 Sorry, typing mistake. It was "divisible by 3". Just edited it now.
•  » » » » 10 months ago, # ^ | ← Rev. 4 →   +1 $2333333333333$ isn't divisible by $3$.A number is divisible by $3$ if the sum of its digits is divisible by $3$. So, according to editorial, the sum of the digits of the answer will be $2+3*(N-1)$ and it's clear that this sum is never divisible by $3$.
•  » » » » » 10 months ago, # ^ |   0 sorry sorry, my mistake again, 2333333333333/3 googled it, and it showed that divisible. But after checking manually, I can understand it is not divisible.
 » 10 months ago, # |   +4 How to Solve problem D1 and D2, Please tell the complete approach.
 » 10 months ago, # |   +3 Can someone please explain D easy version? The approach that I used is as follows:- first check if the given string is a palindrome, if yes, print given string and go for next test case else do the following. 1. set L=1 2. remove all possible substring of length L, one by one and each time check that the remaining string is a palindrome or not. If it is a palindrome then print it, break the loop and go for the next test case. Else continue to check rest substring removals. 3. After checking all substring removal, increase L, that is L++ 4. go to step 2 until you get a palindrome in step 3The code is as follows:-t=int(input()) for _ in range(t): s=input() if s==s[::-1]: print(s) else: n=len(s) l=1 flag=True while flag: for i in range(n-l+1): p=s[:i]+s[i+l:] print("p =",p) if p==p[::-1]: print(p) flag=False break l+=1
 » 10 months ago, # | ← Rev. 3 →   0 For the problem D1, I used the following approach: Suppose the answer is the string t = a + b, length(a) > length(b), a is prefix, b is suffix, then there is a prefix of a that is same as string b and the remaining part of a is a pallindrome in itself. Similar approach can be used length(**a**) < length(**b**), with the change being that there exist a suffix of b that is the same as a. I'm getting wrong answer on test case 16. Can anyone point out the flaw in this approach? It'll be really helpful.73818028
 » 10 months ago, # |   0 PROBLEM C DOUBT can someone explain me the definition of partition, segment and partition value(in this problem) in layman's term (first a non — mathematical followed by a mathematical)?
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 partitioning — divide the complete array into continuous ranges. segment — a continuous range of the array or a portion of the array. partition value — sum of maximum values in each partition.
•  » » » 10 months ago, # ^ |   0 so for 2 7 3 1 5 4 6 {[1,2],[3,5],[6,7]} So here 1,2 and 3,5 and 6,7 are indices? and 2,7 and 3,1,5 and 4,6 are the corresponding elements?
•  » » » » 10 months ago, # ^ |   0 Yes
 » 10 months ago, # | ← Rev. 2 →   0 ...
 » 10 months ago, # | ← Rev. 3 →   0 I am a python user and it's been almost 24 hours since I have been trying to solve the D1 problem of codeforces global round 7. My code works fine in all the test cases I can think of and can easily handle a string of length 5000. But, I am getting time limit exceeded error in test case 5 of codeforces. Here is my code; if there's any python user out there, please, help me out.SOURCE CODE:def palindrome(s,si,ei): l=len(s) if si>=ei: return True elif(s[si]==s[ei]): return palindrome(s,si+1,ei-1) else: return Falsen=int(input())li=[]for i in range(n): li.append(input())for ele in li: stm=palindrome(ele,0,len(ele)-1) if stm: print(ele) else: longest=1 final_str=ele[0] for i in range(len(ele)): prefix=ele[0:i:1] for j in range(i+1,len(ele)+1): suffix=ele[j:len(ele):1] new_str=prefix+suffix lll=len(new_str) stm_1=palindrome(new_str,0,lll-1) if stm_1: if lll>longest: final_str=new_str longest=lll break print(final_str)Again, this code is working for all the test cases the human brain can think of but fails to pass test case 5 of codeforces for reasons which have been tormenting me for a while, since I don't know the reason at all.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Unfortunately there is no way of downloading the full test data, but your implementation is O(n^3) so is likely to be slow for large test cases. Also recursion is quite slow in Python, and best avoided as far as possible.This can be reduced to O(n^2) by breaking the problem into parts: find how much of the start of the input string matches the reversed end of the string, this will be the start and reversed end of the result. find the longest palindrome at the start or end of the middle section of the string and put it in the middle of the result string. My solution following this strategy is here
•  » » » 10 months ago, # ^ |   0 you have written your code in PyPy3. I am familiar with python only, but when I saw your code which is written in pypy3 I found a lot of similarities. can you explain what is the difference between the two?
•  » » » » 10 months ago, # ^ |   0 PyPy3 is an alternative compiler for Python 3. There are some slight differences from the standard CPython compiler (see https://doc.pypy.org/en/latest/cpython_differences.html) but I have never found any of them significant for competitive programming. The main difference is that PyPy3 compiled code runs considerably faster.
 » 10 months ago, # |   0 For those who did not understood D2 from given tutorial.Prerequisite KMP Algo.
 » 10 months ago, # |   +1 Can anyone elaborate explanation of E problem ? Thanks in Advance
 » 10 months ago, # |   0 1326B — Maximums Let's restore a1,a2,…,an from left to right.a1=b1.For i>1, xi=max(a1,…,ai−1), so we can maintain the maximum of previous elements and get the value of xi. Using this value, we can restore ai as bi+xi.
 » 10 months ago, # |   0 Best tutorial for ques D Hard https://cp-algorithms.com/string/prefix-function.html
 » 10 months ago, # |   0 Who likes parsing — like
 » 10 months ago, # |   0 In C, where did n-k+1 come from?
•  » » 10 months ago, # ^ |   0 So you want the k largest numbers to be in separate partitions so the total partition value is the greatest. Because a is a permutation of numbers from 1 to n, the k largest numbers are n, n-1, n-2 ... n-k+2, n-k+1 (n-k is the k+1th largest number as n-1 is the second largest)
•  » » » 10 months ago, # ^ |   0 I see now, thank you so much!
 » 10 months ago, # |   0 isaf27 Can you please share the test generation strategy for Problem D. I was trying to generate test cases during the contest for stress testing and it turned out that even a random string comprising of Just two character say just 'a' and 'b' for $N$ = $2*10^5$ had answer almost around 30-50. I was curious to know about the strategy you used to create test cases for actual task because they were really strong.
•  » » 10 months ago, # ^ |   +6 It is true, that for random strings the length of the answer isn't big, because you have a very very small probability to get the long string in the answer (there are many pairs of symbols that should be equal). So, in the generation of the random strings, you will never get some extreme test cases.About test generation strategy: it's hard to share it because I had some generators, which are not obvious to understand. But some idea of how to generate the string with the long string in the answer: just generate some palindrome first, after that split it randomly and add some symbols between the parts.
 » 10 months ago, # |   0 https://www.youtube.com/playlist?list=PLl4Y2XuUavmsf8Os2QTsRgi6Gn5M1dWO8Uploaded solution videos of problems A — D2 on this link.
 » 10 months ago, # |   0 I got TLE in (D2) 73954184 . I use string hashing. help pls. thanks in advance xd
 » 10 months ago, # |   0 Can anyone please help me in my code .I got TLE in (D2)73975705.I just followed editorial to write my code.. Thanks in advance!
 » 10 months ago, # | ← Rev. 4 →   0 Can somebody explain why my solution got WA on test 35? I used the same idea as the tutorial and used hash to identify palindrome strings. Is it because hashing algorithm is imprecise or there are some bugs in my code? Thank you. Here is my solution: https://codeforces.com/contest/1326/submission/74035587
 » 10 months ago, # |   0 In Problem F2, is there another choice besides using FWT to calculate the convolution of g_ai quickly?
 » 10 months ago, # |   0 74680175 Why I am getting TLE in Problem 2 complexity of my soln is O(n^2) I have used += everywhere using string operation and the code is working fine of TC 2 on my laptop but it is giving TLE on cf why?
 » 9 months ago, # | ← Rev. 2 →   0 In Div2C"In the first test, for k=2, there exists only two valid partitions: {[1,1],[2,3]} and {[1,2],[3,3]}. For each partition, the partition value is equal to 2+3=5. So, the maximum possible value is 5 and the number of partitions is 2."But 1+3=4.... I don't understand this part how this gives 5 as well?
•  » » 8 months ago, # ^ |   0 This is the position of the partitions not their value.{1,1}{2,3}->Max Value from position 1 to 1 is 2 ->Max Value from position 2 to 3 is 3Hence, the max sum is 5. Same goes for{[1,2],[3,3]}.
•  » » » 8 months ago, # ^ |   0 Thank you
 » 9 months ago, # | ← Rev. 9 →   0 Thanks for the great editorial! Some small questions to ask(1) In the editorial of problem f2, f(s1)=f(s2) if s1 and s2 have the same multiset. But in the test example 2 of the problem , 001 and 010 both have multiset [1,1,2], why f(001)=2 f(010)=6 ? 300iq(2) In the problem g, what is the definition of 'way' (i,j)? isaf27Or is there anyone can clarify the logic related to above questions?
 » 9 months ago, # |   0 For problem D my code is failing on TEST 16 can someone find the test_case for which its failing. My code :https://codeforces.com/contest/1326/submission/80047216
 » 8 months ago, # |   0 Please can someone tell me why I am getting TLE in Prefix — Suffix Palindrome (HARD) I have maintained to hash array one for forward and one for backward Then I first used two — pointers to get the common elements from first and end. Then I checked the largest palindrome that is in prefix and in suffix in the remaining string (after I removed the common elements ) using forward and reverse hash. This is the link to my solution
 » 6 months ago, # |   0 https://codeforces.com/contest/1326/submission/89761164 Please find out where i am going wrong I got wrong answer on test case 3 and number 414
 » 3 months ago, # |   0 video tutorial of D2. Prefix-Suffix Palindrome (Hard version) https://youtu.be/shxZAqLE084