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!

I hope to get a t-shirt <3 :)

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

being in top 500 in combined round means his real rate should be higher

It's just ratism. Smh at least he said "I hope", not "I will"

Hope is a good thing.

Being Realistic is better than having high hopes because it won't hurt you laterlet's be realistic and have high hope.

“Remember, Hope is a good thing, maybe the best of things, and no good thing ever dies.”I think you are very pessimist kind of a person XD XD.

Maybe the best of things

yeah...Ratism exactly

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.

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.

IMO it's kinda annoying. It's just noise, and I think it's reasonable to discourage noise.

Thank you for your support :)

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

+Inspiration

Thank you for not rickrolling

Order online :P

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

or even $$$3246$$$

I will reach to that rate and higher in someday

This comment has been deleted due to negative feedback

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!

Well, I know I won't get anything, this doesn't mean I won't participate.

Anyways, what Div is this?

Div1 + Div2 , it's rated for everyone.

Yes it's correct!!!

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

Why you won't get anything?

Give him a break. He obviously meant that he was not expecting to win any prize.

You don't need to say anything wrong to get a lot of downvotes.

You are getting down vote because you think yourself out of everybody.

Thinking yourself within everybody isn't helping you much, is it? :P

Hope you have a good year.

Is it very hard?? I'm a newbie so I don't know i can have a t-shirt.

Extremely.

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

[Deleted]

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.

try to solve at least 2. its hard but you can .

How many problems are there and what's the score for each problem?

It will be announced 3 seconds before the contest start

I hope this round will have strong pretests. :)

MOOSAGA HAHAHAHA

No thanks to Mike. I am very afraid.

Really excited for the classical competitive programming questions. Global codeforces rounds are always great for learning.

Ivan and Ildar are trusted authors :sunglasses:

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

It's good to see another combine round here. I hope everyone doing well with their rating.

only want to solve problems and learn as much as I can.

I hope to get a t-shirt <3 :)

Good luck

`❤️`

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.

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?

Yeah! I do that all the time.

Hope that I can solve ABC ❤️

Good luck guys

`❤️`

They had us in the first half, not gonna lie. Hoping for a great contest.

May I know who is the coordinator? :P

How could you guys forget thanking MikeMirzayanov for the amazing platform.

Does MikeMirzayanov even care thanking him?

But some users care

And some users are busy maintaning the database.

tourist vs MiFaFaOvO !!

wxhtxdy ！！！！！！

What's more difficult? Securing a rank under 500 or getting a Tshirt after that?

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

300iq contest means troll problems. Time to become cyan!

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

True. Even Umnik is cyan on atcoder.

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

I will get 0 points :(

High ratings everyone :)

I hope the statement of problems be short like the blog :D

I need not to stand 1st but will very happy if I can solve 3 problems. :)

Hi! The codeforces app here .

How many problems will be there?

are we going to see a dp problem after all?

Please, help me to solve this problem

It is about polygon

How long is it gonna be?

2 hours and 30 minutes

Hoping it to be a div 2 level contest with 6 problem having strong pretest cases. :)

With how many problems?

Me After 1 successful submission. Let's Check Leader Board and friends standings :)

According to the time left before contest the contest is suppose to start at 08:05. Please have a look

All the best guys, hope this round will also be very enjoying, and will bring some new concepts in the box..♥♥

If XTX is gone, who is sponsoring the prizes this time then?

Thanks to XTX, which in

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

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

Best of luck to everyone!

Expert will belong to me again after this round haahahahahahaahaaaaaaaaaaaaaaaa

Score distribution??

Effect of Corona Virus situation. 17500+ registration.

Hope for best, Number of Problem solved == Number of people cured from covid19

everyone wash your hand and start coding. All the best...

Cant submit, i keep getting: You have submitted exactly the same code before

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.

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.

0_0 thing are getting weird, look at this one, ow man 0_0

this one

Such Long Queues !!

God bless adamant !

Subtasks === poor problemset

Me when I read problem F:

You did not do round though? ;)

![ ]()

C, WA on pretest 5.

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.

Any idea of how to solve it?

How true!

Almost 2000 lines of templates, lol =))

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.

orz

orz...

Good Job everybody!!! Thanks God for not missing this global round! :)))) And also hope every pupil to get cyan just like me :)))

Don't say bullshit =)

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?

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.

How to solve D? Upd: can it be solved without Manacher's algorithm?

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

Can u explain?

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.

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

or just use rolling hash

I solved it using KMP.

how?? got completely stuck.

yes, it can be solved using prefix function

Queue,Speed,Think,String and Math FORCES.

/* Forces

just concatenate with previous parts

How to solve C and D ?

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.

.... That's easy ? :<<<

How to solve E?

A little disappointed by the contest.Not much to think in Problems A,B,C,D .

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

First thing came to my mind when I read title of problem D — link

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.

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

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?

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

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?

Here

`cnt[i][j][k]`

is the number of ways to get string $$$k$$$ if we use subset $$$i$$$ and the last used element from $$$i$$$ is $$$j$$$. Then we combine "set $$$i$$$ ending with $$$j$$$", "edge $$$j-k$$$" and "set $$$\lbrace1\ldots N\rbrace\setminus i$$$ ending with $$$k$$$, reversed order", with $$$N/2-1$$$, $$$1$$$ and $$$N-N/2-1$$$ characters respectively;`rev[i]`

is just to get the reverse of any binary string $$$i$$$ with length $$$N-N/2-1$$$.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.

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

Mine was of the same complexity. It ran for ~1 minute locally and wasn't close to passing :|

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

someone pls give me a hint (not solution) for E ?

Who liked the round put the "class" (the round was prepared by my classmate)

FactCheck: The number of friends of tourist is even greater than number of global contest participants.

Is it possible to solve D with hashing?

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/73727428 (Hacked)

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

This is exactly what I did but got WA-2, I used double rolling hash

Is hashing still a safe approach to D? I saw a lot of hashing based solutions that are failing system testing.

I hope so, still waiting to discover it :)

:/

I passed system testing with hashing

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.Thanks a lot to pikmike and vovuh for not coordinating this round.

There was already a youtube video explaining the solution for problem E

Spoilerhttps://www.youtube.com/watch?v=dQw4w9WgXcQ

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.

Welcome to a permutation contest ...

Can anyone hack my solutions for D? They are accepted even if my bases for hashing < 26

For D1: 73684043

For D2: 73683903

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

;_;

Differenr from you, I used two different small bases and diffirent mods lol

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.

What the hell is going on with order of judging submissions?

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

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

And also submission sent 1 second before the end of the contest has already been judged: 73734244

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

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

Yes. But it is not impossible to replace to search for strategies (algorithms).

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

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

Thanks

Anyone used EERTREE + binary jump on D? XD

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

I wrote it on the contest.

But you don't need binary jump, you can use DSU.

73699237

I used EERTREE without binary jump 73696641.

I solved D in the way you said. XD

73700725

how is this solution correct https://codeforces.com/contest/1326/submission/73692335

I tried a hack on it but the verdict said unsuccessful hack attemptt-

1

10

the result came out 2222222237 which is divisible by 7

2222222237 / 7 = 317 460 319,571429

My Calculators approx value cost me 50 points....

:(

how does the system test work? it looks like it doesn't sort the submissions in time order

It looks like only submissions after 0:20 are being judged

Till now what I see, it seems kind of random...

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]

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.

yeah!! thank you! But what is the maximum accepted value in long long???

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.

Please increase python complexity. Even O(NlogN) gave TLE in question C. Please rejudge.

Don't think that you somehow deserve to get Accepted using Python.

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.

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

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.

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!

Coronavirus. Please help!. It helps in the containment of the Coronavirus.

Does anyone know what is going on with the system tests for this contest?

Very random order of system testing. Never seen something like this happen before.

Why did systest halted?

Because, Now 300iq is performing different permutation on system testing

Is the order of system testing decided beforehand or is the server going berserk on its own.

On my hours of waiting for system testing, i realized that the host has 20 cores, the algorithm it use is as follow:

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

very slow system tests...

Smh Internet Explorer is faster.

xD at least internet explorer doesn't go back in time like what has happened in the last division 3 contest!

I wish system test will have completed before I will go to sleep.

Waiting for System testing!!

Also waiting to upsolve the round :(

Thanks for antihash test!!!!!!!!!!!!!!!!!!!

It is really cool to make people writing 2 or more moduls!!!!!!!!!! It is really ideaful move!!!!!!

Thanks!!!!!!

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.

Fast Editorial !!!

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

you don't realize it

is an Overpowerful comment. Overrules the judge's verdict.

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/73733467Well, 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

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.

I got my mistake.

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.

Infact i found another proof :

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.

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:

https://codeforces.com/contest/1326/submission/73726135 (TLE) https://codeforces.com/contest/1326/submission/73741382 (AC)

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.

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.Thanks, can you tell me why are these two assignments treated this differently?

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()})$$$.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:

Java orz

How are the random t-shirts determined (random numbers between [31,500])? I also happened to get 281th place.

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

I can't tell if you're trolling or not.

I am not, its just my opinion about how an array is well-randomized.

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

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?

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

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.

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

Are you kidding yea? problems differ.

They're both submission to problem B.

Sorry for wrong reply

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.E is cool. A is too hard.

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.

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

I got my mistake..

I have solved two problems for the fist time in a contest!! :D

https://www.youtube.com/playlist?list=PLl4Y2XuUavmsf8Os2QTsRgi6Gn5M1dWO8

Will 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

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.

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

## include <stdio.h>

## include <string.h>

## include <math.h>

## 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;

}

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

}

why current solutions are stuck in queue for an hour