### 300iq's blog

By 300iq, 3 months ago, ,

Hi!

On Mar/19/2020 17:35 (Moscow time) we will host Codeforces Global Round 7.

It is the first round of a 2020 series of Codeforces Global Rounds. The rounds are open for everybody, the rating will be updated for everybody.

The prizes for this round:

• 30 best participants get a t-shirt.
• 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2020:

• In each round top-100 participants get points according to the table.
• The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
• The best 20 participants over all series get sweatshirts and place certificates.

The problems of this round were developed by isaf27 and me. Thanks to the testers mohammedehab2002, Taran_1407, Aleks5d, Endagorion, 74traktor, HIR180, dlwocks31,ToTheMoon, coyorkdow, Tzak, DomiKo, JustasLe, Hyado, Nemo, tattosha_aptan, Jatana, and (language corrector!) caoash.

Thanks to XTX, which in 2020 supported the global rounds initiative!

Good luck!

UPD: Score distribution: 500 1000 1000 (1000-1000) 2500 (2000-1500) 4000

UPD: Editorial!

Announcement of Codeforces Global Round 7

• +565

 » 3 months ago, # |   -13 I hope to get a t-shirt <3 :)
•  » » 3 months ago, # ^ |   -27 Why people are down voting? Is is offensive for a newbie to have a cherish for getting a T-shirt in CF?
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +39 being in top 500 in combined round means his real rate should be higher
•  » » » 3 months ago, # ^ |   +79 It's just ratism. Smh at least he said "I hope", not "I will"
•  » » » » 3 months ago, # ^ |   +28 Hope is a good thing.
•  » » » » » 3 months ago, # ^ |   +26 Being Realistic is better than having high hopes because it won't hurt you later
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   +57 let's be realistic and have high hope.
•  » » » » » 3 months ago, # ^ |   +65
•  » » » » » » 3 months ago, # ^ | ← Rev. 3 →   +6 “Remember, Hope is a good thing, maybe the best of things, and no good thing ever dies.”
•  » » » » » » 3 months ago, # ^ |   +6 I think you are very pessimist kind of a person XD XD.
•  » » » » » » 3 months ago, # ^ |   +11
•  » » » » » 3 months ago, # ^ |   +3 Maybe the best of things
•  » » » » 3 months ago, # ^ |   -49 yeah...Ratism exactly
•  » » » » 3 months ago, # ^ |   +148 What rating do you think that people will upvote for "I hope to get a t-shirt" at the top of the comments of a contest announcement? I don't think others are interested in his hope.I'm not saying that he can't hope for a t-shirt, but I think "I hope to get a t-shirt" is meaningless to me, and he also can't get any help — he can ask "how to improve on a specific topic" if he really wants to get a t-shirt.
•  » » » » » 3 months ago, # ^ |   +13 Well, I'm not saying one should upvote him. Maybe his comment is not useful, but it's not harmful or annoying too. I think amount of downvotes he's getting is a bit much and probably many people downvoted him because he can't do it.
•  » » » » » » 3 months ago, # ^ |   +83 IMO it's kinda annoying. It's just noise, and I think it's reasonable to discourage noise.
•  » » » 3 months ago, # ^ |   -25 Thank you for your support :)
•  » » 3 months ago, # ^ | ← Rev. 2 →   +40 don't let the downvotes frustrate you , It is all about a long journey of hard working . wish you the best ❤️
•  » » » 3 months ago, # ^ |   +11
•  » » » » 3 months ago, # ^ |   0 Thank you for not rickrolling
•  » » 3 months ago, # ^ |   0 Order online :P
•  » » 3 months ago, # ^ | ← Rev. 2 →   -30 From your words we can infer that your real rating is $2164$ instead of $1082$
•  » » » 3 months ago, # ^ |   -17 or even $3246$
•  » » » » 3 months ago, # ^ |   -12 I will reach to that rate and higher in someday
 » 3 months ago, # | ← Rev. 2 →   -27 This comment has been deleted due to negative feedback
 » 3 months ago, # |   +309
•  » » 3 months ago, # ^ |   +87 We are really sorry for the delay. :(
•  » » 3 months ago, # ^ |   +217 I guess you'll need smaller size now :D
•  » » 3 months ago, # ^ |   +10 Bruh I got one from Global Round 1 and still waiting.
•  » » 3 months ago, # ^ |   +3 According to the rules at most 50 people will get T-shirt but >=254 people are concerned about it. Nice!
 » 3 months ago, # |   -33 Well, I know I won't get anything, this doesn't mean I won't participate.Anyways, what Div is this?
•  » » 3 months ago, # ^ |   +2 Div1 + Div2 , it's rated for everyone.
•  » » » 3 months ago, # ^ |   -19 Yes it's correct!!!
•  » » 3 months ago, # ^ |   -32 Why is it getting so many downvotes, I didn't say anything wrong
•  » » » 3 months ago, # ^ |   +7 Why you won't get anything?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Give him a break. He obviously meant that he was not expecting to win any prize.
•  » » » 3 months ago, # ^ |   +22 You don't need to say anything wrong to get a lot of downvotes.
•  » » » 3 months ago, # ^ |   -19 You are getting down vote because you think yourself out of everybody.
•  » » » » 3 months ago, # ^ |   +13 Thinking yourself within everybody isn't helping you much, is it? :P
 » 3 months ago, # | ← Rev. 2 →   +11 Hope you have a good year.
 » 3 months ago, # |   -20 Is it very hard?? I'm a newbie so I don't know i can have a t-shirt.
•  » » 3 months ago, # ^ |   0 Extremely.
•  » » 3 months ago, # ^ | ← Rev. 2 →   -110 [The post that you want to dislike ,currently do not exists]
•  » » » 3 months ago, # ^ | ← Rev. 2 →   -90 [Deleted]
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +47 He didn't ask the difficulty of solving all problems, so the "truth" is: there are problems from the ones which can be easily solved by a pupil to the ones which are challenging for a grandmaster.
•  » » 3 months ago, # ^ |   -21 try to solve at least 2. its hard but you can .
 » 3 months ago, # |   +6 How many problems are there and what's the score for each problem?
•  » » 3 months ago, # ^ |   +12 It will be announced 3 seconds before the contest start
 » 3 months ago, # |   +47 I hope this round will have strong pretests. :)
 » 3 months ago, # |   -24 MOOSAGA HAHAHAHA
 » 3 months ago, # |   +5 No thanks to Mike. I am very afraid.
 » 3 months ago, # |   +12 Really excited for the classical competitive programming questions. Global codeforces rounds are always great for learning.
 » 3 months ago, # |   +75 Ivan and Ildar are trusted authors :sunglasses:
 » 3 months ago, # |   +141
•  » » 3 months ago, # ^ |   +16 But I think this condition is at least better than that of Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!) — solving less than 2 problems :)
 » 3 months ago, # |   +6 It's good to see another combine round here. I hope everyone doing well with their rating.
 » 3 months ago, # |   -25 only want to solve problems and learn as much as I can.
 » 3 months ago, # |   +2 I hope to get a t-shirt <3 :)
•  » » 3 months ago, # ^ |   0 Good luck ❤️
 » 3 months ago, # | ← Rev. 2 →   +55 Off-topic, but I found this interesting. There's a search option on the Contest page to search for particular contests. Not many platforms have this feature. I don't know how many of you knew that already.
•  » » 3 months ago, # ^ | ← Rev. 4 →   -22 But it's better to use CTRL+F to search. Because that works far better than cf search feature, like I searched div 3 and it did not work(because I missed the dot), because it matches with the exact word. But using chrome's ctrl+f it was successful to find the result.Edit: Why am I getting downvotes? Is there anything wrong?
•  » » » 3 months ago, # ^ |   0 Yeah! I do that all the time.
 » 3 months ago, # | ← Rev. 3 →   +15 Hope that I can solve ABC ❤️Good luck guys ❤️
 » 3 months ago, # |   -13 They had us in the first half, not gonna lie. Hoping for a great contest.
 » 3 months ago, # |   +30 May I know who is the coordinator? :P
 » 3 months ago, # |   -13 How could you guys forget thanking MikeMirzayanov for the amazing platform.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +43 Does MikeMirzayanov even care thanking him?
•  » » » 3 months ago, # ^ |   0 But some users care
•  » » » » 3 months ago, # ^ |   0 And some users are busy maintaning the database.
 » 3 months ago, # |   +13 tourist vs MiFaFaOvO !!
•  » » 3 months ago, # ^ |   0 wxhtxdy　！！！！！！
 » 3 months ago, # |   0 What's more difficult? Securing a rank under 500 or getting a Tshirt after that?
•  » » 3 months ago, # ^ |   +7 I think getting a tshirt. Because getting under 500 rank depends on your hard work, but getting that random depends on luck.
 » 3 months ago, # |   0 300iq contest means troll problems. Time to become cyan!
•  » » 3 months ago, # ^ |   +27 Cyan is the most fashionable color man. Be happy. :))
•  » » » 3 months ago, # ^ |   0 True. Even Umnik is cyan on atcoder.
 » 3 months ago, # |   -26 Yesssss!!! ... I think my rank gonna be 500 and I am so happy because rank 31 to 500 INCLUSIVE, not EXCLUSIVE!!!! gonna get a t-shirt randomly ... so lastly I am likely to get a t-shirt... Thanks GOD!!!
 » 3 months ago, # |   0 I will get 0 points :(
 » 3 months ago, # |   0 High ratings everyone :)
 » 3 months ago, # |   0 I hope the statement of problems be short like the blog :D
 » 3 months ago, # |   +1 I need not to stand 1st but will very happy if I can solve 3 problems. :)
 » 3 months ago, # |   +3 Hi! The codeforces app here .
 » 3 months ago, # |   +6 How many problems will be there?
 » 3 months ago, # | ← Rev. 2 →   -10 are we going to see a dp problem after all?
 » 3 months ago, # |   -14 Please, help me to solve this problemIt is about polygon
 » 3 months ago, # |   +1 How long is it gonna be?
•  » » 3 months ago, # ^ |   +7 2 hours and 30 minutes
 » 3 months ago, # |   -8 Hoping it to be a div 2 level contest with 6 problem having strong pretest cases. :)
 » 3 months ago, # |   +12 With how many problems?
 » 3 months ago, # |   +21 Me After 1 successful submission. Let's Check Leader Board and friends standings :)
 » 3 months ago, # |   +2 According to the time left before contest the contest is suppose to start at 08:05. Please have a look
 » 3 months ago, # |   +4 All the best guys, hope this round will also be very enjoying, and will bring some new concepts in the box..♥♥
 » 3 months ago, # |   0 If XTX is gone, who is sponsoring the prizes this time then?
•  » » 3 months ago, # ^ |   +50 Thanks to XTX, which in 2020 supported the global rounds initiative!This blog also has XTX logo. I don't think XTX is gone.
 » 3 months ago, # |   +4 My best wishes to everyone in the house, hope this round will bring new developments in you, and will be marked an amazing experience for you all... ♥♥♥
 » 3 months ago, # |   0 Best of luck to everyone!
 » 3 months ago, # |   +4 Expert will belong to me again after this round haahahahahahaahaaaaaaaaaaaaaaaa
 » 3 months ago, # |   +6 Score distribution??
 » 3 months ago, # | ← Rev. 2 →   +61 Effect of Corona Virus situation. 17500+ registration.
 » 3 months ago, # |   +6 Hope for best, Number of Problem solved == Number of people cured from covid19
 » 3 months ago, # |   +29 everyone wash your hand and start coding. All the best...
 » 3 months ago, # |   +10 Cant submit, i keep getting: You have submitted exactly the same code before
•  » » 3 months ago, # ^ |   0 yup, I got the same issue, it was around 5 minutes late for B ~ 20points
•  » » 3 months ago, # ^ |   0 My solution is just too simple, you may know it but i still wanna say that if you add a comment line or just couple of slashes at the end of your code, then its done, you can submit it.
•  » » » 3 months ago, # ^ |   0 I know this, but I was getting this error for every code I try to submit, for about 5 minutes I couldn't submit anything.
•  » » » » 3 months ago, # ^ |   0 0_0 thing are getting weird, look at this one, ow man 0_0this one
 » 3 months ago, # |   -12 Such Long Queues !!
 » 3 months ago, # |   0 God bless adamant !
 » 3 months ago, # |   +51 Subtasks === poor problemset
 » 3 months ago, # | ← Rev. 2 →   +236 Me when I read problem F:
•  » » 3 months ago, # ^ |   0 You did not do round though? ;)
 » 3 months ago, # |   +46 ![ ]()C, WA on pretest 5.
•  » » 3 months ago, # ^ |   +14 same i also got Wa
•  » » 3 months ago, # ^ |   +17 Same here, and I had to wait for the feedback, because of the long queue :(
•  » » 3 months ago, # ^ |   +11 I also got WA at pt-5 for several time. Finally got AC.
•  » » 3 months ago, # ^ |   -10 Any idea of how to solve it?
•  » » 3 months ago, # ^ |   0
•  » » » 3 months ago, # ^ |   +14 Almost 2000 lines of templates, lol =))
•  » » » » 3 months ago, # ^ |   +11 As a friend of mine, an author of this round, said, 2000 lines of templates is like putting on your trunks not in the dressing room near the pool, but at home in order to swim faster.
•  » » » 3 months ago, # ^ |   0 orz
•  » » » » 3 months ago, # ^ |   0 orz...
 » 3 months ago, # |   -21 Good Job everybody!!! Thanks God for not missing this global round! :)))) And also hope every pupil to get cyan just like me :)))
•  » » 3 months ago, # ^ |   0 Don't say bullshit =)
•  » » 3 months ago, # ^ |   0 First of all congratulations!Second, can you tell me how did you solve C? my idea is to add to a variable largest k numbers, then number of valid sequences is to increment another variable with distance between every k big numbers (But I hit WA 5).If my approach is wrong, then what's the correct one?
•  » » » 3 months ago, # ^ |   +3 When you are taking the largest k numbers at that time you can mark those position of permutation. Then For number of valid sequence you need to iterate the whole array of your marked position in the reverse order and increase a counter until your marked position doesn't come. If it comes just multiply the variable with your ans of valid partition and decrease the counter to 0. Don't forget to start your iteration from a marked position as well as your initial ans should be 1.
 » 3 months ago, # | ← Rev. 2 →   +1 How to solve D? Upd: can it be solved without Manacher's algorithm?
•  » » 3 months ago, # ^ |   +15 i passed it with Z algorithm for finding longest prefix palindromic string
•  » » » 3 months ago, # ^ |   0 Can u explain?
•  » » 3 months ago, # ^ |   0 D1 was shear brute force D2 needs knowledge of Longest Palindromic prefix in a string in linear or n logn time though I cant implement D2.
•  » » 3 months ago, # ^ |   +14 I did a kind of greedy approach; first peel off the biggest word $w$ and $w.reverse$ from the beginning and end of $s$; then on the remaining substring $t$, apply Manacher's algorithm to $t$ to find the largest palindrome $v$ that is a prefix or suffix of $t$. Then the answer is $w+v+w.reverse$
•  » » 3 months ago, # ^ |   +1 I used Manacher Algorithm. It has a array represent palindrome radius, which is really helpful.
•  » » 3 months ago, # ^ |   +1 First check with two pointers, how many characters from suffix and prefix make a palindrome. Store them in left and right strings. Now in the remaining string find longest palindromic prefix and suffix, I used KMP to do this in O(n). Let's call this remain. Your final answer is left + remain + right string.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Can you share from where you studied about the longest palindromic prefix in a string? Thank you.UPD: Got it here. It's a nice explanation.https://www.quora.com/What-are-different-algorithms-for-converting-a-string-into-a-palindrome-by-adding-characters-to-the-end-other-than-appending-the-reverse-of-the-string-to-itself
•  » » 3 months ago, # ^ |   0 or just use rolling hash
•  » » 3 months ago, # ^ |   +7 I solved it using KMP.
•  » » » 2 months ago, # ^ |   0 how?? got completely stuck.
•  » » 3 months ago, # ^ |   0 yes, it can be solved using prefix function
 » 3 months ago, # |   -12 Queue,Speed,Think,String and Math FORCES.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 /* Forces
•  » » » 3 months ago, # ^ |   0 just concatenate with previous parts
 » 3 months ago, # |   0 How to solve C and D ?
•  » » 3 months ago, # ^ |   0 For C read 1. Read statement carefully : 2. Find first k maximum elements of the permutation and store their indices in a vector. 3. these vector contains sorted indices as we traversed from 1 to n to store indices of first k maximum values. for first part of answer just find the sum of first k maximum values for second part multiply different of adjacent indices in the obtained indices vector and modulo it with given number ... finally output both the parts..
•  » » » 3 months ago, # ^ |   +1 .... That's easy ? :<<<
 » 3 months ago, # |   0 How to solve E?
 » 3 months ago, # |   +58 A little disappointed by the contest.Not much to think in Problems A,B,C,D .
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 I can't agree any more. But it need much more careful to implement them. I finished 5 problems but only got 4 problem's score.
•  » » 3 months ago, # ^ |   +10 I could only solve A & B :(. So it just depends on your experience, I reckon... But again, I'm a Pupil, so you might be right :)).
 » 3 months ago, # |   +25 First thing came to my mind when I read title of problem D — link
 » 3 months ago, # |   0 How to solve E? I figured out I need a structure that holds pairs (x, y) and allows me to answer queries "what is the maximum y for x > c", but I don't know how to do that.
•  » » 3 months ago, # ^ |   0 Lazy segtrees :") (I got the soln in last few minutes, spent the rest of the time trying to implement retroactive Priority queue without luck)
•  » » 3 months ago, # ^ |   +40 The answer is at least $res$ if there exists some suffix with more values at least $res$ than bombs.Thus, to check if the answer is at least $res$, make a segment tree with range sum and maximum, store in it suffix sums, where each value at least $res$ is $+1$ and each bomb is $-1$, and check if there exists some suffix sum that is greater than zero. If there does, the answer is at least $res$. Otherwise, answer is less than $res$.Lastly we just need to note that the answer never increases, so we can maintain this segment tree, making in total at most $2n$ changes and $2n$ queries.Code: 73693217
 » 3 months ago, # |   +54 So what's F1? By the number of people who got it it seems to be much easier than F2, but the weird scoring (2000-1500) suggests that F1 requires the harder step in whatever the full solution is. What's up with that?
•  » » 3 months ago, # ^ |   +5 F1 is meet in the middle that, without any particular optimisations (at least I didn't try any), works in ~1s. Since MITM increases exponentially, the step from F1 to F2 isn't straightforward, but it might be some stupid constant optimisations...
•  » » » 3 months ago, # ^ |   0 Well my MITM ran in 52sec locally and obviously TL-ed on the system. Half an hour of optimisation didn't get me any further. Obviously mine sucks so could you give some details on yours?
•  » » » » 3 months ago, # ^ |   +15 vector cnt[1<<14][14]; for(int i = 0; i < (1<>j)&1) cnt[i][j].resize(1<<6, 0); for(int i = 0; i < N; i++) cnt[1<>j)&1) for(int k = 0; k < N; k++) if(!((i>>k)&1)) for(int s = 0; s < (1<<5); s++) cnt[i|(1< rev(1<>k)&1); vector ans(1<<(N-1), 0); for(int i = 1; i < (1<>j)&1) for(int k = 0; k < N; k++) if(!((i>>k)&1)) for(int s1 = 0; s1 < (1<<(N/2-1)); s1++) { int s_start = (2*s1+G[j][k]) << (N-N/2-1); for(int s2 = 0; s2 < (1<<(N-N/2-1)); s2++) ans[s_start+rev[s2]] += cnt[i][j][s1] * cnt[(1<
•  » » » » 3 months ago, # ^ |   +10 Fix the midpoint $[n]$. Partition the remaining $n-1$ elements into halves of size $n/2$ and $n-1-n/2$. Solve these halves by DP or by enumerating all permutations, counting how often you can make each of ${0, 1}^{n/2}$ (or ${0, 1}^{n-1-n/2}$ respectively). Paste everything together in $2^{n-1}$ time.
•  » » 3 months ago, # ^ |   0 "but the weird scoring (2000-1500) suggests that F1 requires the harder step in whatever the full solution is" — that's not the correct logic in subtasks xDAnd I guess you can come up with many solutions to F1. Mine looks on the first sight as $O(4^n)$, but it is in fact $O(3^n)$. Maybe fact that $\sum_{k=0}2^k {n \choose k} = 3^n$ will lead you on the right track.
•  » » 3 months ago, # ^ |   +20 I passed pretests on F1 (73723311) with a meet-in-the-middle approach that probably shouldn't have worked.First calculate for every subset of up to $\left\lceil \frac{n}{2} \right\rceil = h$ wise men, how many ways there are to put them in a row such that the last one is wise man $i$ and the adjancencies are some mask $m$, just like how you would solve the Hamiltonian path problem. This part takes $\mathcal{O}(\binom{n}{h} n^2 2^{h})$ work.Then just naively combine these, by looping over first $h$ wise men, the two wise men that we will join the two parts on, and the adjancency masks of both parts. This part is $\mathcal{O}(\binom{n}{h} n^{2} 2^{n})$ work, which is around $10^{10}$, but the constants are good enough that the code works in around half the time limit.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Mine was of the same complexity. It ran for ~1 minute locally and wasn't close to passing :|
•  » » 3 months ago, # ^ |   +67 F1 is stupid.Calculate $\mathrm{dp}[\mathrm{mask}][i][s]$ — the number of ways to build the string $s$ if we have already visited the people in $\mathrm{mask}$, with the last visited person being $i$.This seems like it's obviously too slow, but we can notice that the length of the string $s$ is smaller if the popcount of the mask is small. Implement the DP table as vector dp [1 << MAX_N][MAX_N], and let the length of $\mathrm{dp}[\mathrm{mask}][i]$ be $2^{\mathrm{popcount}(\mathrm{mask}) - 1}$.I verified, before coding it, that calculating this takes about $10^8$ "operations".
•  » » 3 months ago, # ^ |   0 I managed to solve it with a standard $O(n^2 2^n)$ DP for a given string $x$ by exploiting the similarity between sequential strings, which in most cases differ only in a couple of lower bits. Therefore, when solving for string $x$, you can reuse a lot of the memoized solutions for DP states that you computed for string $x-1$.
 » 3 months ago, # |   0 someone pls give me a hint (not solution) for E ?
 » 3 months ago, # |   -22 Who liked the round put the "class" (the round was prepared by my classmate)
 » 3 months ago, # | ← Rev. 2 →   +31 FactCheck: The number of friends of tourist is even greater than number of global contest participants.
 » 3 months ago, # |   +5 Is it possible to solve D with hashing?
•  » » 3 months ago, # ^ | ← Rev. 3 →   +7 Yes, I solved it this way with hashing: Get the longest prefix + suffix that matches(are equal).Then, get the longest palindrome in the mid of the string that doesnt contain the prefix and the suffix. To get this palindrome, use rolling hashes for all ranges (l, i) and (i, r), where l and r denotes de range of the mid of the string.Code: https://codeforces.com/contest/1326/submission/73773544 (Accepted)
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 This is exactly what I did but got WA-2, I used double rolling hash
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Is hashing still a safe approach to D? I saw a lot of hashing based solutions that are failing system testing.
•  » » » » 3 months ago, # ^ |   0 I hope so, still waiting to discover it :)
•  » » » » » 3 months ago, # ^ |   +3 :/
•  » » » » 3 months ago, # ^ |   0 I passed system testing with hashing
•  » » 3 months ago, # ^ |   +1 can be done by hashing.I used kmp though.My solution:find the longest prefix and suffix to be equal.Then in the remaining string, find the longest palindromic prefix or suffix. In order to do that, link. I wish I had bothered to Googled for this earlier, could have saved almost 30 minutes of mine.
 » 3 months ago, # |   -59 Thanks a lot to pikmike and vovuh for not coordinating this round.
 » 3 months ago, # |   -56 There was already a youtube video explaining the solution for problem E
 » 3 months ago, # |   +141 Yet another reason to hate subtasks at Codeforces: I solved D2 first, but my submission was stuck in the queue for 3 minutes. That situation either forces you to take the risk to get a WA on pretests on both problems, or to get 3 minutes more penalty on the first subtask. On other online judges this is a non-issue, as a submission to a problem is automatically a submission to all of its subtasks.
 » 3 months ago, # |   -15 Welcome to a permutation contest ...
 » 3 months ago, # | ← Rev. 3 →   +1 Can anyone hack my solutions for D? They are accepted even if my bases for hashing < 26For D1: 73684043 For D2: 73683903
•  » » 3 months ago, # ^ |   +13 lol ask boboniu (ranked 3rd in this contest), he hacked mine even though I considered my bases quite safe. ;_;
•  » » » 3 months ago, # ^ |   +1 Differenr from you, I used two different small bases and diffirent mods lol
•  » » » » 3 months ago, # ^ |   -8 I don't think that will be hard either, two small bases further increase the chance of collisions.Not sure, but I think collisions should be more evident in your case.
 » 3 months ago, # |   +42 What the hell is going on with order of judging submissions?
•  » » 3 months ago, # ^ |   0 Only submissions after 20 minutes from beginning of contest are judged.
•  » » 3 months ago, # ^ |   +3 I guess they're ignoring everything submitted before 0:19 for now...
•  » » » 3 months ago, # ^ |   0 And also submission sent 1 second before the end of the contest has already been judged: 73734244
 » 3 months ago, # |   -97 Hello, I wanted to propose that there are problems that seek to minimize the coronavirus transmission curve. Perhaps problems where data are given on the populations by age of different parts of the world, even the least populated and their communication channels, run a simulation of the interactions over time and wonder what would be the best strategy. A first intuitive solution would be, for example, to divide the inhabitants by age or risk groups and those least prone to getting sick, to send them to the densest urban centers and the least prone to the least dense urban centers, once they have been infected and cured. healthier they can go back to less populated places, so there would be less spread. What do you think ?.
•  » » 3 months ago, # ^ |   +49 Have you any idea about what kind of problems we solve here?
•  » » » 3 months ago, # ^ |   -68 Yes. But it is not impossible to replace to search for strategies (algorithms).
 » 3 months ago, # |   +3 i use KMP to solve D2 but i give TLE i think my code is O(sizeof(string)) for each test case anyone know why? my code
•  » » 3 months ago, # ^ |   +7 ss = s + s[i] is the problem, s = s + y is O(|s| + |y|) , much better is to use s+=(y) as this is O(|y|) . I think that will solve the TLE issue , since I used KMP too
•  » » » 3 months ago, # ^ |   +3 Thanks
 » 3 months ago, # |   +45 Anyone used EERTREE + binary jump on D? XD
•  » » 3 months ago, # ^ | ← Rev. 2 →   +29 Yeah, I come up with this solution too when isaf told me the problem.
•  » » 3 months ago, # ^ |   0 I wrote it on the contest.But you don't need binary jump, you can use DSU.73699237
•  » » 3 months ago, # ^ |   0 I used EERTREE without binary jump 73696641.
•  » » 3 months ago, # ^ |   -6 I solved D in the way you said. XD73700725
 » 3 months ago, # | ← Rev. 2 →   -8 how is this solution correct https://codeforces.com/contest/1326/submission/73692335I tried a hack on it but the verdict said unsuccessful hack attemptt-110the result came out 2222222237 which is divisible by 7
•  » » 3 months ago, # ^ |   +23 2222222237 / 7 = 317 460 319,571429
•  » » » 3 months ago, # ^ |   +29 My Calculators approx value cost me 50 points.... :(
 » 3 months ago, # |   +33 how does the system test work? it looks like it doesn't sort the submissions in time order
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 It looks like only submissions after 0:20 are being judged
•  » » 3 months ago, # ^ |   +3 Till now what I see, it seems kind of random...
 » 3 months ago, # | ← Rev. 2 →   0 In the permutation partition problem I had applied the same logic as given in the editorial but I got wrong answer in pretest 5.Please help[submission:73710370]
•  » » 3 months ago, # ^ |   0 Your logic was correct but I'm afraid due to integer overflow during your calculation of: long long sum=n*k-k*(k-1)/2; you are getting wrong answer. Both n and k are declared int but their value can be 200000 and thus n*k >= INT_MAX.
•  » » » 3 months ago, # ^ |   0 yeah!! thank you! But what is the maximum accepted value in long long???
•  » » » » 3 months ago, # ^ |   0 long long range is : -9223372036854775808 to +9223372036854775807 (simply google it) Enough to fit calculated value. Just change type of n and k to long long and your code will be accepted. In general, I suggest you to always use long long type to avoid falling in overflow traps.
 » 3 months ago, # |   -89 Please increase python complexity. Even O(NlogN) gave TLE in question C. Please rejudge.
•  » » 3 months ago, # ^ |   +17 Don't think that you somehow deserve to get Accepted using Python.
 » 3 months ago, # |   +194 What about giving full score (without drain) for easy subtask if you have solved hard? It is not ideal, but solves some problems of current state.
•  » » 3 months ago, # ^ |   +15 There is a great satisfaction in having taken the risk to the solve the hard, then to get to do this pointless submission which you are sure will pass :p
•  » » 3 months ago, # ^ |   +3 I agree, but I believe this brings other complications. How would you handle wrong submissions? Would you give double penalty (one for each subtask) on non-AC verdicts?The main issue is that subtasks are treated as separate problems. That shouldn't happen. There should only be one task, where each submission gives partial points if it passes the small testset, and full points if it passes the big testset. Just as it is done in other judges. This way, contestants can stop worrying of compromising their score or having their submissions wait in queue. It's also easier to handle wrong submissions. Just penalize if a submission doesn't gain any points.
 » 3 months ago, # |   -58 I got a message saying my solution coincides with my alternate account"Your solution 55166209 for the problem 1175A significantly coincides with solutions karunk/55140411, sayuri/5516620"But I never logged into my alternate account! If you go to the profile, it says last login 7 months ago and there are no recent submissions...Could it be a case that both accounts are somehow mapped together because of a bug? Please help me because I dont want to be penalised for something which is not my fault!
 » 3 months ago, # |   -66 Coronavirus. Please help!. It helps in the containment of the Coronavirus.
 » 3 months ago, # |   +42 Does anyone know what is going on with the system tests for this contest?
 » 3 months ago, # |   +11 Very random order of system testing. Never seen something like this happen before.
 » 3 months ago, # |   +41 Why did systest halted?
•  » » 3 months ago, # ^ |   +85 Because, Now 300iq is performing different permutation on system testing
 » 3 months ago, # |   +3 Is the order of system testing decided beforehand or is the server going berserk on its own.
•  » » 3 months ago, # ^ | ← Rev. 3 →   +17 On my hours of waiting for system testing, i realized that the host has 20 cores, the algorithm it use is as follow: push all the submissions to the queue, in ascending order of time submitted/judged on pretests. add first 100 submissions in the queue, or all the remaining submissions if they are less than 100. judge them 20 by 20(or sometimes 1 by 1, it changed during the HOWFST(Hours Of Waiting For System Testing :P, its really close to "HOWFAST" but not the same). do things with newly judged submissions(for example update number of accepts for the problem, update standings and . . ., some of them were done in the time of judging, not sure about the exact algorithm as it changed a lot in the HOWFST) go back to line#1 if the queue is not empty, or go to line#5 otherwise. update everything. Probable the real algorithm is different, i did my best sorry if i let you down :)Note:Difference between 20 by 20 and 1 by 1 is that, the cores wait for each other to finish the judgement then they all go forward together in "20 by 20", but in "1 by 1" every core goes to the next submission which is not running or judged after it finished the judgement.P.S. I wrote 0 -> 1 -> . . 5 in the algorithm's lines, and the cf remade them using 1 -> 2 -> 3 . . 6, i didn't know cf is that much HI-TECH :D.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 You may say iam wrong with judging order, its more likely that they first started in a random order, then decided to make it more beautiful, then they sorted all the solutions in ascending order of time submitted/judged on pretests.
 » 3 months ago, # |   +131 very slow system tests...
•  » » 3 months ago, # ^ |   +33 Smh Internet Explorer is faster.
•  » » 3 months ago, # ^ |   0 xD at least internet explorer doesn't go back in time like what has happened in the last division 3 contest!
 » 3 months ago, # |   +4 I wish system test will have completed before I will go to sleep.
 » 3 months ago, # |   +31 Waiting for System testing!!
•  » » 3 months ago, # ^ |   0 Also waiting to upsolve the round :(
 » 3 months ago, # |   -77 Thanks for antihash test!!!!!!!!!!!!!!!!!!!It is really cool to make people writing 2 or more moduls!!!!!!!!!! It is really ideaful move!!!!!!Thanks!!!!!!
 » 3 months ago, # |   +88 Please codeforces make a gift to the people that donated money and upgrade the hardware. Codeforces it’s a great platform but people have to wait hours for system testing to complete every time when there is a contest.
 » 3 months ago, # |   0 Fast Editorial !!!
 » 3 months ago, # |   +8 I guess this is a lesson to me to never write an algorithm with a $0.2\%$ chance of failing per test case when there's no full feedback... 73689147 73740657
•  » » 3 months ago, # ^ |   +5 you don't realize it //this is such a bruh moment is an Overpowerful comment. Overrules the judge's verdict.
 » 3 months ago, # |   +1 Hey did anyone get this message wrong answer jury found longer string, jans = 12 > pans = 2. I got it as the message for a wrong solution to D.Can anyone tell what it means? My submission link if it may help https://codeforces.com/contest/1326/submission/73733467
•  » » 3 months ago, # ^ | ← Rev. 2 →   +8 Well, your task was to find the longest string that satisfied the conditions in the question. Since the intended answer is a string longer that the one you output, it showed a wrong answer
•  » » 3 months ago, # ^ |   0 Same case for me. My submission : https://codeforces.com/contest/1326/submission/73732348 Did you get any test case for which your code produce wrong output? If yes,share please.
•  » » » 3 months ago, # ^ |   0 I got my mistake.
 » 3 months ago, # |   -13 I received a message saying that my code matched with the other two: rmodi9942,Black_Level. I checked on ideone and saw that my settings were public and they have copied the code. In order to prove it you can 1. check my submissions for C,B and A , the submission for D1 has the same template as that of A,B and C and theirs is different. In fact all my submissions for the past 1 month have the same template. 2. Both of them have ratings under 1000 and are newbie and hence the probability of them copying my code is high. I'm really sorry that i forgot to make ideone settings as private, and will surely change it to private.
•  » » 3 months ago, # ^ |   -8 Infact i found another proof : rmodi9942 has copied in the previous contest also. I just checked his profile and his submissions for previous contest Codeforces Round #628 (Div. 2) has been skipped. Black_Level has also copied solution for the previous contest as can be seen on his profile the contest in which he copied is Codeforces Round #601 (Div. 2). Infact you should ban both of their accounts, since in their contest/submission history most of their solutions are skipped. Please give me my ratings back, you can see my profile is clean and it was only in this contest that i became their victim.
 » 3 months ago, # |   0 Today, I learned a harsh truth (sadly, after contest) that string concatenations aren't constant time even for single character concatenations. See the two submissions below:The only difference is that I've replaced all concatenations (inside the for loops, don't ask me why I chose to do it in the first place) with their equivalent substr counterparts. If there're more things in this context that might be helpful knowing, please share. Thanks.
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 Well in your TLE code you can just replace pref = pref + s[i] with pref += s[i], and this is constant time. After that, suf is just the reverse of pref. No need to change to substr if you didn't want to.
•  » » » 3 months ago, # ^ |   0 Thanks, can you tell me why are these two assignments treated this differently?
•  » » » » 3 months ago, # ^ |   0 Well if you do a = a + b then you are creating a new string a + b and then assign back to a, so the time complexity for that is $O(\text{a.size() + b.size()})$. In the case a += b, you just extend a b.size() more characters, so the time complexity is $O(\text{b.size()})$.
»
3 months ago, # |
+76

Hi! Thanks for participation. This round broke all records for popularity: 18180 registrations and over 2.5M pageviews! Taking into account a large number of tests in easy problems, system testing turned out to be too long. I apologize for it.

I'm glad to announce the winners of the t-shirts! They are:

List place Contest Rank Name
1 1326 1 tourist
2 1326 2 Um_nik
3 1326 3 boboniu
4 1326 4 jiangly
5 1326 5 cuizhuyefei
6 1326 6 TLE
7 1326 7 WZYYN
8 1326 8 PavelKunyavskiy
9 1326 9 kefaa2
10 1326 10 Benq
12 1326 12 Swistakk
13 1326 13 RomaWhite
14 1326 14 aid
16 1326 16 ecnerwala
17 1326 17 ko_osaga
18 1326 18 DCXDCX
19 1326 19 yosupo
20 1326 20 amnesiac_dusk
21 1326 21 djq_fpc
22 1326 22 .I.
23 1326 23 Egor.Lifar
24 1326 24 Maksim1744
25 1326 25 FizzyDavid
26 1326 26 I_love_chickpea
27 1326 27 kraborak
28 1326 28 Golovanov399
30 1326 30 duality
53 1326 53 kobae964
76 1326 76 Maripium
95 1326 95 Celesta
97 1326 97 vasilescu_mihai
127 1326 127 Toxel
137 1326 137 jo_ulej
138 1326 138 Atreus
146 1326 146 Temotoloraia
174 1326 174 JaeminPark
232 1326 232 Kloze
273 1326 273 Ari
281 1326 281 ngtkana
292 1326 292 hyjtxdy
300 1326 300 BZZB
303 1326 303 gyz_gyz
312 1326 312 ddytxdy
396 1326 396 aropan
469 1326 469 uruuru8888
486 1326 484 Java
499 1326 499 Sahaand
•  » » 3 months ago, # ^ |   -15 Java orz
•  » » 3 months ago, # ^ |   -6 How are the random t-shirts determined (random numbers between [31,500])? I also happened to get 281th place.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   -19 My calculation says that yes, let me say what ive dont, first for every two continues winners, $sum += (a_{i+1} - a_i) ^ 2$, the array $a$ is the ranks of the winners with higher rank than 30 in increasing order, then lets find the smallest sum we can get when choosing $a_i$s, then the displacement of the array $a$ will be $ds(a) = sum(a) - sum_{mn}$, $sum(a)$ returns the defined value $sum$ for an array, and $sum_mn$ is the lowest $sum$ we can get from any valid array $a$. You will see that choosing a random array $a$ should give us a quite low $ds(a)$, for example less than $n$, and the results of a good randomized array should give $sqrt(n) < ds(a) < n$, in my opinion. So the winners are well randomized so far. It's really my opinion and i really thought about it.P.S. I hope you liked my calculations :).
•  » » » » 3 months ago, # ^ |   0 I can't tell if you're trolling or not.
•  » » » » » 3 months ago, # ^ |   -6 I am not, its just my opinion about how an array is well-randomized.
•  » » » » 3 months ago, # ^ |   0 Oky i should say it was just a random idea about how to check an array is well-randomized or not, but in fact it was all done for nothing, as every valid array have the same probability =(.
 » 3 months ago, # |   0 Offtopic question, but do you get a penalty if you get WA on the first pretest? also, do you get a penalty if you get WA on the Tests included in the statement?
•  » » 3 months ago, # ^ |   0 You wont get penalty for WA on the first test/pretest in normal cf rounds, educational rounds and global rounds and . . ., but iam not sure about the rest, i bet on "no they dont have penalty".
•  » » » 3 months ago, # ^ |   0 Thanks a lot!I think you do get penalty, my latest contest i had 6 WA on the second and third pretest(part of the statement) and i think my score is way off because of it.
 » 3 months ago, # | ← Rev. 2 →   0 Sorry to bother, but why my O(n) solution 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
•  » » 3 months ago, # ^ | ← Rev. 2 →   -7 Are you kidding yea? problems differ.
•  » » » 3 months ago, # ^ |   +1 They're both submission to problem B.
•  » » » » 3 months ago, # ^ |   0 Sorry for wrong reply
•  » » 3 months ago, # ^ |   0 You can see that your AC solution us barely passed the tests. If you are using c++ with cin/cout then you should check this out. IO actually requires a lot of times.
 » 3 months ago, # |   +1 E is cool. A is too hard.
 » 3 months ago, # |   0 After I read the Problem A, my mind is full of 3 and 8. But I thought that to verify 338 and 38 are not divisible by 8 is more troublesome than to verify 34 is not divisible by 4. And finally I chose 3 and 4.
 » 3 months ago, # |   +1 Can anyone give me any case for which my solution of D2 get WA?I got verdict WA on test case 3.My Submission: https://codeforces.com/contest/1326/submission/73732348
•  » » 3 months ago, # ^ |   0 I got my mistake..
 » 3 months ago, # |   +9 I have solved two problems for the fist time in a contest!! :D
 » 3 months ago, # | ← Rev. 3 →   -21 https://www.youtube.com/playlist?list=PLl4Y2XuUavmsf8Os2QTsRgi6Gn5M1dWO8Will be uploading solution videos of problems A — D2 on this link.(I don't understand the reason behind so much hate (-25). A to C have been uploaded, D1 & D2 will be uploaded soon)UPD: Solution videos of D1/D2 and E have been uploaded
 » 3 months ago, # |   0 I screwed in D2 trying to insert in a StringBuilder. Remember java users insert has a time complexity of O(n). Its better to append and then reverse the operations.
»
2 months ago, # |
Rev. 2   +3

The below code is getting TLE for D2, may anyone help me to know why?

# define MAX 500005

char text[MAX]; int min(int a, int b) { int res = a; if(b < a) res = b; return res; }

int findLongestPalindromicString() { int N = strlen(text); if(N == 0) return -1; N = 2*N + 1; //Position count int L[N]; //LPS Length Array L[0] = 0; L[1] = 1; int C = 1; //centerPosition int R = 2; //centerRightPosition int i = 0; //currentRightPosition int iMirror; //currentLeftPosition int maxLPSLength = 0; int maxLPSCenterPosition = 0; int start = -1; int end = -1; int diff = -1;

//Uncomment it to print LPS Length array
//printf("%d %d ", L[0], L[1]);
for (i = 2; i < N; i++)
{
//get currentLeftPosition iMirror for currentRightPosition i
iMirror  = 2*C-i;
L[i] = 0;
diff = R - i;
//If currentRightPosition i is within centerRightPosition R
if(diff > 0)
L[i] = min(L[iMirror], diff);

//Attempt to expand palindrome centered at currentRightPosition i
//Here for odd positions, we compare characters and
//if match then increment LPS Length by ONE
//If even position, we just increment LPS by ONE without
//any character comparison
while ( ((i + L[i]) < N && (i - L[i]) > 0) &&
( ((i + L[i] + 1) % 2 == 0) ||
(text[(i + L[i] + 1)/2] == text[(i - L[i] - 1)/2] )))
{
L[i]++;
}

if(L[i] > maxLPSLength)  // Track maxLPSLength
{
maxLPSLength = L[i];
maxLPSCenterPosition = i;
}

//If palindrome centered at currentRightPosition i
//expand beyond centerRightPosition R,
//adjust centerPosition C based on expanded palindrome.
if (i + L[i] > R)
{
C = i;
R = i + L[i];
}
//Uncomment it to print LPS Length array
//printf("%d ", L[i]);
}

int idx = 0, len = 0;
for(int i = 0; i < N; i++) {
if(i - L[i] == 0) {
len = L[i];
}
}

return len;

}

int main() { int t; scanf("%d", &t);

while(t--) {
char S[MAX];
scanf("%s", S);

int len = strlen(S);
int l = 0, r = len - 1;

while(l <= r) {
if(S[l] != S[r]) break;
++l, --r;
}

if(l > r) printf("%s\n", S);
else {
for(int i = 0; i < l; ++i) printf("%c", S[i]);
int top = 0;
for(int i = l; i <= r; ++i) {
text[top++] = S[i];
}
text[top] = '\0';

int midLen = findLongestPalindromicString();
int top1 = 0;
for(int i = r; i >= l; --i) {
text[top1++] = S[i];
}
text[top1] = '\0';

int revLen = findLongestPalindromicString();
if(midLen > revLen) {
for(int i = l; i < l+midLen; ++i) {
printf("%c", S[i]);
}
}
else {

for(int i = r-revLen+1; i <= r; ++i) {
printf("%c", S[i]);
}
}

for(int i = r+1; i < len; i++) printf("%c", S[i]);
printf("\n");
}
}

}

 » 2 months ago, # |   0 why current solutions are stuck in queue for an hour