The problems A, C, D, G are authored and prepared by isaf27.
The problems B, E, F are authored and prepared by 300iq.
Tutorial is loading...
Jury solution: link
Tutorial is loading...
Jury solution: link
Tutorial is loading...
Jury solution: link
Tutorial is loading...
Jury solution: link
Tutorial is loading...
Jury solution: link
Tutorial is loading...
Jury solution: link
Tutorial is loading...
Jury solution: link
Let's discuss your ideas and solutions in the comments. Thanks for your participation!
Thanks for the fast editorial ! :)
Thanks for Editorial giving so fast
Why do you have so many down votes? QwQ
it's the same words as the first one who got 14 up votes...
Maybe only the first person has the right to thanks for the fast editorial. (laughing
Its because first one is Candidate Master ,and he is a Newbie..
Accept or not but ratism do exists.
whats up with the down votes
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?
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.
can anyone give me detailed explanation of E?
Thanks in advance!!
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.
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?
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.
Can anyone please give a detailed explanation of D? Thanks.
I divided question into two parts
1.Till how much prefix and suffix are same
2.Using manchers algorithm find longest palindrome at each point
Then for each index check if it touches with common prefix points and it's your solution.
My Solution — 74734509
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?
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$$$.
And would you please explain the prefix function?
https://cp-algorithms.com/string/prefix-function.html
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.
Same;)
Thanks for the link ! but there is no explanation for why the complexity is O(n). Would you explain it ?
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
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.
nice, thank you so much, I've learnt it !
Could you please tell where my code fails i am not able to debug it :( https://codeforces.me/contest/1326/submission/73832292
UPD : Found it , error in prefix function XD
You can find an extensive explanation for prefix function here : https://youtu.be/nJbNe0Yzjhw
w = s[k+1..n−k] + "∗" + rs[k+1..n−k]
What is the use of "*"?
Split the string into two part, after the operation, there will not exist a palindrome cross two independent parts.
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.
deleted
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
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) ?
For example when $$$s = "aaaaaa"$$$, then we use a character(like '#' or '*') to limit the prefix-function.
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)?
No we cant.
In the third question, the explanation for the third test case seems to be wrong which was quite confusing.
What is wrong about it? Are you sure you just don't misunderstand the explanation?
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
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.
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.
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.
55555(n-1 times)8(1 time) also works.
999...98 works as well
33....38 works too.
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).
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?
3 out of the 4 you gave are counterexamples lol
2223 % 3 = 0, 4443 % 3 = 0, 8888888889 % 9 = 0
ending in 3, 6, and 9 all don't work cus of the same reason :(
They aren't counter examples 23333 43333 89999 Just repeat the other digit.
Yes, I think so. But I don't have enough mathematical knowledge to prove that it's right, so it's my guess.
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 3
ending in 1, 2, 4, 5, and 8 don't work and idk about 7
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 4
Thus Numbers ending with 14, 34, 54, 74, and 94 are not divisible by 4. Now repeat any odd digit and that's the answer.
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?
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.
Hey Monogon, thanks for the solution, that is pretty intuitive! Would you suggest similar problems as Div2C for the above one?
Look at problems with the combinatorics tag and difficulty 1000-1500.
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.
I don't understand why, but problems B, C and D1 were much more intuitive to me than A was.
Yeah! about that, the more one thinks the harder it gets. These first questions are really surprising these days.
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.
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.
ABalobanov, 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?
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.
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:
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 here
Ps. Thanks to Kallaseldor for the idea to solve the problem using retroactive priority queue
despite of partial retroactive priority queue, can you tell me which algo i need to know to solve E as a beginner
read the editorial?
Wy this submission My submission to problem D2 gives TLE if the complexity is O (n)
Instead of doing this
Try doing this :
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.
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.
Could someone point out the idea behind solving F1 (that won't work for the harder version)? Thanks.
For example this 73757219 naive recursion with memoization.
calc(mask, last)
calculates the answer for the rest of the men (given bymask
) withlast
being currently the last man in the sequence. Complexity seems to be O(n*2^(2n)) with a good constant.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)$$$
You are right, thank you.
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.
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
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!!
KMP O(n) solution (Longest palindromic prefix)
https://discuss.interviewbit.com/t/kmp-o-n-solution-longest-palindromic-prefix/29112
Can someone please explain the logic behind the code. Thanks!!
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!
How does CF compile c++14?
I submited problem D
On test2:
case input: q
Real 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 contest
Help me pls.
Probably your solution on your machine didn't output just "qq", but "q<some control character, which is invisible in terminal>q" 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.
thank you for the information. I'll be careful next time when coding
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?
Isn't 2222...29 also a possible solution for Ugly Bad Numbers?
No if $$$n-1$$$ is divisible by 9
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}$$$.
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.
Could the problem be:
since it is resetting the entire array for every single test case?
I haven't considered of such problem.
You are right. Thanks a lot。:)
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
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
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
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 :(
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:
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:
It costs 826 ms at the test#4. 73757350
I add
flush
aftercout << 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. 73756448
In 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. 73756516
It 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.
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.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
I don't think so. You use 30 and 30 is not a prime.
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.
I have never seen someone use a non-prime as base for string hash...
BTW I got AC using double hashing.
You can use a prime as base, it will AC: https://codeforces.me/contest/1326/submission/73752592
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.me/contest/1326/submission/73767232
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 passes
It will be very helpful if you can clarify this to me
That's because of hacks against those specific hashes.
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...
A Permutationforces round.
why is the editorial of D2 not given?
*D1
My solution for C was failing on pretest 5. Has any1 faced the same problem?
maybe you forgot to module 998244353?
No, I did it.
Here is my code.
#include <bits/stdc++.h>
using namespace std;
#define MOD 998244353
int 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<n;i++) cin>>a[i]; int sum= n*k — (k*(k-1))/2; cout<<sum<<" ";
}
Useless editorials
I like this editorial. It's great.
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 !!
The number 998 224 353 appears three times in the problem and it is long and strange enough for you to discover it.
By doing this, if some problem of the contest uses NTT, the modulo won't give it away.
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.
If someone can explain approach of question D2 in simple words it would be great help
Summary
Steps
Manacher's Algorithm
"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}
References
Thanks a lot buddy ! Really it was amazing video and tutorial provided by you was quite helpful!!! :)
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.
can you please help me understand why this (https://codeforces.me/contest/1326/submission/73942810) is giving wrong answer?
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).
Helped me a lot, thanks brother!!
if(i-radius[i]+1 <= 0 || i+radius[i]-1 >= n-1)
can u plz explain this line?? thank u
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 beabc...cba
. Then you want to find the largest inner string that touches either the initialabc
part or the lattercba
part. So we run manacher's ondedx
and find thatded
is the longest inner palindrome that touches theabc
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).Can somebody please explain the perfix function in problem D2??
You can check out prefix function here : https://youtu.be/nJbNe0Yzjhw
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.me/contest/1326/submission/73769004
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.
with base=29 and mod=1e9+7 my solution failed for test case 104, I then modified my mod to 998244353 and it passed.
Your words make me not feel alone. :)
The same happened for lots of people, for example my friend davooddkareshki, it seems that it was kind of anti-hash test cases.
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.
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.
You're right. I heard of it before.
So must we use hashing with 3 mods?
No. Even that can be hacked if you don't randomize your base and modulo. You should make your base(s) random.
So the hack needs the code's modulo, base or both?
Both.
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?
https://codeforces.me/blog/entry/60442
thx.
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).
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!
Try this 471D
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?
How can a number ending on $$$3$$$ in decimal representation be divided by $$$2$$$?
Sorry, typing mistake. It was "divisible by 3". Just edited it now.
$$$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$$$.
How to Solve problem D1 and D2, Please tell the complete approach.
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 3
The 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
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
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)?
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.
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?
Yes
...
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):
n=int(input())
li=[]
for i in range(n):
for ele in li:
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.
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
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?
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.
See also https://codeforces.me/blog/entry/21851
Can anyone elaborate explanation of E problem ? Thanks in Advance
Who likes parsing — like
In C, where did n-k+1 come from?
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)
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.
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.
https://www.youtube.com/playlist?list=PLl4Y2XuUavmsf8Os2QTsRgi6Gn5M1dWO8
Uploaded solution videos of problems A — D2 on this link.
I got TLE in (D2) 73954184 . I use string hashing. help pls. thanks in advance xd
In Problem F2, is there another choice besides using FWT to calculate the convolution of g_ai quickly?
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?
For problem D my code is failing on TEST 16 can someone find the test_case for which its failing. My code :https://codeforces.me/contest/1326/submission/80047216
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
I don't understand why D2 solution is true. Can anyone prove it?
Mybe we have a smaller k but a longer palindrome that makes answer bigger.
I have the same doubt , if you figured it out by now , please explain
I understood it!
If we have m<k then we can increase l , r by 1 and remove the last(or first) character of a. then the length of our string increase by 1.
So if we choose m<k then we have a longer string.
seems like editorial solution of D2 didn't include hashing which I used to solve