Why people are down voting? Is is offensive for a newbie to have a cherish for getting a T-shirt in CF?

don't let the downvotes frustrate you , It is all about a long journey of hard working . wish you the best ❤️

From your words we can infer that your real rating is $$$2164$$$ instead of $$$1082$$$

We are really sorry for the delay. :(

I guess you'll need smaller size now :D

Bruh I got one from Global Round 1 and still waiting.

According to the rules at most 50 people will get T-shirt but >=254 people are concerned about it. Nice!

Div1 + Div2 , it's rated for everyone.

Why is it getting so many downvotes, I didn't say anything wrong

Extremely.

[The post that you want to dislike ,currently do not exists]

It will be announced 3 seconds before the contest start

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 :)

Good luck ❤️

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?

Does MikeMirzayanov even care thanking him?

wxhtxdy　！！！！！！

I think getting a tshirt. Because getting under 500 rank depends on your hard work, but getting that random depends on luck.

Cyan is the most fashionable color man. Be happy. :))

2 hours and 30 minutes

Thanks to XTX, which in 2020 supported the global rounds initiative!
This blog also has XTX logo. I don't think XTX is gone.

yup, I got the same issue, it was around 5 minutes late for B ~ 20points

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.

You did not do round though? ;)

same i also got Wa

Same here, and I had to wait for the feedback, because of the long queue :(

I also got WA at pt-5 for several time. Finally got AC.

How true!

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?

i passed it with Z algorithm for finding longest prefix palindromic string

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.

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$$$

I used Manacher Algorithm. It has a array represent palindrome radius, which is really helpful.

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.

or just use rolling hash

I solved it using KMP.

yes, it can be solved using prefix function

/* Forces

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.

1. for first part of answer just find the sum of first k maximum values
2. for second part multiply different of adjacent indices in the obtained indices vector and modulo it with given number ...
3. finally output both the parts..

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.

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 :)).

Lazy segtrees :") (I got the soln in last few minutes, spent the rest of the time trying to implement retroactive Priority queue without luck)

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

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...

"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 xD

And 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.

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.

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<ll> 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".

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$$$.

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://mirror.codeforces.com/contest/1326/submission/73727428 (Hacked)

Code: https://mirror.codeforces.com/contest/1326/submission/73773544 (Accepted)

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.

lol ask boboniu (ranked 3rd in this contest), he hacked mine even though I considered my bases quite safe.

;_;

Only submissions after 20 minutes from beginning of contest are judged.

I guess they're ignoring everything submitted before 0:19 for now...

Have you any idea about what kind of problems we solve here?

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

Yeah, I come up with this solution too when isaf told me the problem.