Hi everyone!

Codeforces Round #367 (Div.2) takes place on 11th of August at 19:35 MSK. As usual, Div.1 participants can join out of competition.

This is my first round on Codeforces! I advise you to read all the problems. Hope everyone will find something interesting.

I'd like to thank GlebsHP for helping me in preparing this round, Yury_Bandarchuk and IvanVan for testing tasks. Of course, many thanks to MikeMirzayanov for great Codeforces and Polygon platforms.

**UPD:** Scoring is **500-1000-1500-2000-2500**

**UPD:** Editorial

**UPD:** The contest is over. Congratulations to the winners!

Div.1 winners:

1.anta

2.W4yneb0t

3.sugim48

4.uwi

5.Kmcode

Div.2 winners:

2.Shining

4.AwD

5.stjepanp

kiram to tarrahe in contest

## The problems producer is just blue like me.Why can I use those problems to be purple?

Why do your comment is hidden every time.

كفو

Simple brief statement, thanks a lot and hope high rating change for everyone =D

Sorry but that's impossible :(

yeah... these are CF contests.... (;

i have to wait 10 minute compiling my answer -_- it was shit not contest :(

RIP English

And as usual... scoring will be announced later! (maybe just before the contest! or after the contest!) Whyyyyyyyyy?!

Does it matter?

then why they announce?!!

It matters during the competition to help you divide your time

"Div.1 participants can join out of competition" What does the sentence mean, please? Could Red users join on Div.2 contests? It's always the case? Thank you. :)

Yes, they can participate. But their rating won't be affected.

Got it, thank you.

Hope this contest will be better than last Div2 only contest. Hope there won't be such a long queue during the contest because of so many people. (Hate the feeling knowing the contest is unrated after a 2hr-hardwork at midnight)

How do you know about last contest? Oh it's your new Div.2 account...

maybe he had new girlfriend ??!

Round he's talking about was unrated. I think that's a reason he is still out of rating.

Look at his profile "Registered: 25 hours ago" -_-

short GL & HF, I hope statement will be short as this :))

Hope for nice problems and strong pretests :)

Could someone explain to me the reason for downvotes on this comment?

It's Codeforces. You never know what happens to your comment.

Well said Tweety. (y)

Maybe you are new! but you can use up and down vote buttons instead of this comment!

Well said TD. (y)

In hindsight

FYI, I downvoted

but downvoting others won't decrease your negative contributions.

I hope the community loves me again :) I wrote a lot of stupid downvote worthy stuff to earn -47. Guess I won't be doing that again.

actually we upvote a comment if it is useful, fun, interesting ,... and we downvote a comment if it is useless, spam, ugly,...

if you want upvote then interest us!

That's not how this works. You never know which comment will be upvoted and which ones will get downvoted.

Downvote doesn't seem to work for me whenever I hit downvote the comment rating stays the same, is there any reason for this?

because others upvote simultaneously...

d

Today, give a stranger one of your smiles. It might be the only sunshine he sees all day.

+1 for pikachu dp

I hope this round will be more interesting than previous one)

Sorry, because of unknown reasons, I counldn't upload the picture)

it's not an unknown reason

the reason is that you don't know how to upload a picture

anyway, click

(CTRL + P)and put the link of the pictureYou're supposed to get the link to the image rather than the google image link https://i.ytimg.com/vi/LNX4dFILlm8/maxresdefault.jpg

Ok,thanks)

NBAH will you be one of the contestants in this round ? :p

"Are we poisonous?" the young snake asked his mother. "Yes, dear," she replied — "Why do you ask?" "Cause I've just bitten my tongue! "

I think They are using their time for coding :P so, they don't wanna waste their time and using random comments :P

MSK means??

Moscow Standard Time. Google it or click the link in the contest's description

or ask here!

Round of div2 member?

I hope there will not be an easy task!

cried my contribution ((( Dislike for each my post((( soon the absolute value of my contribution will surpass Errichto

Dislike me who wants to help me!

As u wish

sorry but i upvoted for u :)

Fact : 367 is a prime number

salam

namifahmid chi migam chera manfi midid?

a round without the IOIers ?

Not many of them are Div2 anyways.

Did you just assume their division?

triggeredis it rated ??

Why everytime there is someone ask that?

if a contest is unrated, they will tell it in announcement ... maybe as an update

Hope for a good and interesting contest. :)

I hope this contest won't have so many commercials for games and movies. Just clear tasks.

You think the one about avengers was with help of commercials?, u think they ask codeforces community to create probs about them?..

Yes,dude ... NEVER :)

Too late for Asia......Too familiar :)) :))

Ah

I think it's too good time for Bangladesh <3

I have a dream, that there will be more contests ends before 12 m.n. in my local area for me to get at least a purple... At this rate it would probably take several months to wait for a contest which my brain can function normally.

Randomness of likes and dislikes will one day be used as a random number generator :v

Like if you disagree :v

Today is Codeforces NBA match ;) Wow!! That's great to play on computer too. Thank u very much NBAH. Best of performance for everyone in this match :)

Is there anyone who could help me to solve this problem or give any other approach.Thanks in advance http://codeforces.com/blog/entry/46505

[user:jibancanyang]Come on,believe yourself,and tonight you must be the candidate master!

a;;;;;;;;;;;;;;;;flbgoqwgowqeiufhhdvbka;bdkasbf;efowofowjo#inwohndlandsfl!

I guess you will be hidden again.... 0.0

Anyone here knows how to unregister I'm not sure if I will be able to write codeforces today PELASE HELP

Just don't submit anything or open page of participants >> find your handle >> click the red (X) button to the right of your handle to unregister yourself

If you don't submit, your rating won't be affected.

If you didn't submit anything,they won't check your rating.

We should wait 9 days for next contest :((

And two week for next div 1 contest!

So far!

wow! it's a long time for you!!!

You can still practice with div 2 contests, and it's more comfortable since there's no rating on the line.

The Olympic season is here and we have some Codeforces rounds scheduled too. We should have an Olympic themed contest.

Wish Good luck to all :)

Queue is back. :/

my source is still in queue for long time. does this happens to anyone else?

Codeforces queue :/ . Please do compensate for the time we have lost in this and are still losing.

queue 2 : the nightmare

make it unrated:/

ياخرى حليت 4 شو unrated ؟

unrated بطيزك يامنيك

behave your self . gotosleep

give us time so the queue is fucking us :(

i hope it's not going to be unrated again!

Auto comment: topic has been updated by NBAH (previous revision, new revision, compare).I guess it's another unrated contest, unfortunately.

Stupid person shut ur mouth

LOL

I thought the queue problem was solved! I submitted B. Waited for 5 minutes, still in queue. Went to solve C, submitted C, found out B was WA. And now C has been on queue for 3 minutes. wtf! -_-

Thank god it's unrated for me. I'm out.

لطيزي

how did you make it unrated for yourself?

he participated out of comptetion.

My solution to C is not even in the queue. I am not able to submit it! -_-

Finally was able to submit by uploading the source file. I am having this problem since many days, not able to submit code that is copy-pasted in the editor.

!

Please, don't make it unrated.

It would be unfair for participants who got WA after one hour. :/

Who told you life is fair ;)

Besides, it will be unfair to those who got their solutions judged in time. Its just like contest time. Some countries benefit from the time, some have troubles. You won't complain about that would you?

if there's long queue, no one will get their solutions judged in time. and really a wa verdict after a long time makes it unfair for the contestant.

R u sure u got wa after an hour? I really think what ur saying is false..All my submissions passed is <=10 mins...and just look at the number of people who solved each problems.. the stats say ur lying

One hour :o ? I submitted program at 5min, 10min, 30min, and 70 mins. I had to wait for more then 5 mins for pretests only for 2nd (which was at 10 min) Rest all submissions were quick in judging (less then 5 mins for sure)

Congrats, good work! ^==^'

Wow, really great curve of number solved. And this is only halfway through the contest.

مو قلتلك حاج تعلق ؟! روح استمني عحالك .

On a completely off topic, how many people on codeforces follow Silicon Valley (TV show) ?

I do :D

Well, I don't think you can get your answer if you ask this question here. After some yes/no, people will stop replying due to negative votes (spamming). You should rather create a poll externally and give the link here.

C was a dp problem right? I was starting to get it but I didn't have enough time to debug :(

From the fact that it was called "Hard Problem" and that some people submitted it in 4 minutes, I am guessing there is a non DP solution but sadly I don't see it. Can anyone share their solution?

Can you explain what your DP solution was? Just so I know if I was on the right track (if you don't mind).

d[i][t] = minimal cost with last element i, and t = 1 if we don't reverse it, t = 2 if we reverse i-th string.

Glad to know I was pretty close lol. Thanks for the help.

انت مخنث ؟

Lol I like my hair though so I think I'll keep it (if you're making fun of my hair).

Edit: Also I'm 100% male.

العق مؤخرتي

بندوق مغكر حالك بتعرف تستخدم google translate ?

Don't even bother replying him.

Apparently some people did write dynamic solution in 5 minutes e.g. #19788803. I'm impressed.

Yup. You could view it as a graph problem and then it is finding the shortest path in dag from 1 to n that could be done in O(n + m) There are 2*n vertex and every vertex has max of 2 outgoing edges.

I was considering representing it as a dag too. Thanks for the help.

let's call l[i] is the list of strings and r[i] is reserved string of l[i]. Then we have dp[i][0] means min cost of list from 1->i that l[i] is not reserved, and dp[i][1] means l[i] is reserved. First dp[i][0] = Inf, if l[i] >= l[i-1] dp[i][0] = dp[i-1][0], if l[i] >= r[i-1] dp[i][0] = min(dp[i][0],dp[i-1][1]). Then dp[i][1] = Inf, if r[i] >= l[i-1] dp[i][1] = dp[i-1][0] + c[i], if r[i] >= r[i-1] dp[i][1] = min(dp[i][1],dp[i-1][1] + c[i]). Res = min(dp[n][0],dp[n][1]). If Res = Inf then Res = -1. That is my solution and it passed present test.

I implemented a 1D DP solution. Here is the link to the solution.

I don't like man :P. When I get 20 minutes penalty and a WA just because I wrote a statement twice . :D

And by the way was it only me who took Manhattan distance in Problem A and passed 6 pretests? :D

I used taxicab geometry too, and I found out I was wrong about it on the 7th pretest :/

same same :P

Got response from judge after 20 min from submission.(long queue)

Also sad as i got to know it was wrong after 20 min. :(

Will this be a rated contest?

How to solve D? Thank you.

I solved it using Trie

It can be solved by trie, easily. I supposed that you know task to find the biggest xor of two elements in array ( you can find solution on internet easily too). Here you only need to story how many times you went through some node ( because sometime you must delete some edges).

Look at Problem 1 in this article: Trie Tutorial

In my solution we write every number in binary using 35 bits, we use leading zeroes if required.

I let the map M[i,j] save how many integers x satisfy that when you only look at the bits in the first j positions you get i.

Both updates and queries can be done in time

Dang I wish I'd thought of this I made a mess trying to implement a Trie

Use Binary Trie.

This is my idea, haven't tried it yet.

Convert every input(number) to binary system. Put it in BST (1s go right, 0s go left). Make sure that all numbers in binary system are the same size. So 6 -> 110, but if max value is 1e9, it became 0000....110.

When you search start from leftmost digit and go through BST and pick side different than current digit. When you reach the last node it's your answer.

It looks like greedy solution, can you prove that it right in all cases?

2^t > 2^(t — 1) + 2^(t — 2) + 2^(t — 3) + ... + 2^0.

That part is not so hard, because the every bit is clearly more important than all of the bits to its right, combined .

Thanks.

What will you do if both children have same digit with current digit?

Oh, stupid on me. Both children definitely won't have same digit with current digit at the same time.

It's efficient for searching. But wouldn't it be hard when we're gonna do deleting operation on the tree?

I would do same as search, when you reach last node, go up.

Ah I see, I've already considered that method in contest but stumbled in delete operation. Thanks for the info.

Wow, CF servers are fast, my first hack on this submission (19791945) takes over 5 × 10

^{9}iterations and it ran in sightly less than two seconds.It's not the "extremely fast servers", but probably the O2 optimization that cut the number of iterations.

What O2 optimization ?

Had no idea Tries were this standard, so many people solved D.

I think my rating will drop to below 900 :/

you guessed right

It is ok I am only doing this for fun for now.

you mean you get fun by solving 0 problem?

I solved 2 actually just couldn't get them right within the contest time and 2A got rejected during testing(WA on test 41) because I didn't set precision to 7 digits after decimal point.

well try to upsolve the rest 3 as well. It won't help unless you gradually develop some new techniques, will it ? :/

Yeah, I am learning some basic algorithms and doing problems on SPOJ, I only started doing this regularly from a month ago, at the moment I don't think I can solve C-E.

Anyone else think that the time limit for E was a bit too strict?

I don't know but if the target was split

O(q(n+m)) and then it was not strict.There was a solution in q(n+m)? Wow... at least I managed to implement a working treap for the first time

I wrote the same O(q*n*log n) with treaps as well. I think it was a bit too tempting to come up with some online algorithm that uses treaps of segment trees to fairy solve this problem.

Yep, The good intuition to this solution represents the structure as beads that connecting by a thread with a neighborhood, in this case, you can split

O(n+m) thread and connect it by another way.So, basically a quad-linked list? Thanks!

Yes

any full description of "quad-linked list"? is it smth like sqrt-decomposition of list? Google gives smth strange.

Thanks in advance

Tried treap but TA11:(

UPD just wondering how the hell is possible to distinguish fast c++ qmlog(n) from slow java qm...

Basically there is set of nodes representing the fields of the matrix. Each node is connected via a pointer to its upper, lower, left and right neighbor.

Statement that rectangles doesn't share common side makes so much more sense now ;) Actually I'm surprised that not much people came up with this solution, as it isn't complicated at all.

Ok thanks, already read it in solution, seems to me that coded something similar once

Thanks! So trivial yet so hard to think!

What about this

O(QNM) solution?http://codeforces.com/contest/706/submission/19802812

I know, this solution utilizes the fact that modern machines are very good at copying large amounts of memory around.

This just proves that the time limit itself, although the problem and its solution are very interesting, doesn't make any sense.

This round is totaly interesting :) Although I couldn't solved problem D (wish that i could learn Trie earlier) but today it is fine!

That moment when ur solution is in queue for more than 15 min. And On top of that you get a verdict as a wrong answer . Ruins everything :(

i always thought that the feature of rejecting the exact same submission was useless. after this contest i really appreciate it. it saved lots of precious 50-points as i had to submit 10 solutions to see one of them got into the queue.

okay really codeforces what the fuck is happening!

i get WA after 30 min from submit ! :)

it should be unrated like Eran Contest

yup...i got WA after 20 min of Submit.

Same Here :(

Yeah now lucky people who didn't get Wrong answer will vote down this comment :)

if someone solved their solution correctly at one go, it doesnt make them lucky, it makes them more aware and smart

they are smart because they didn't get WA ?

they are smart yeah but they are lucky too because they don't wait 20 min and lose many points and resubmit solution also lose 50 point :)

in 20 min i can solve B instead of fix small mistake in 'A' problem

smart only isn't enough

Just solve all problems and your rating won't decrease:D

u are so genius bro congratulations :D

Does anybody know why my submission 19801619 got compile error? Thank you!

the queue was so long in the start of this contest please consider this.

كول خرا

Who else has used graph to solve C?

I spent an hour implementing D using multiset, so I guess this will be my motivation to learn trie finally :D

Do you mean that you did it using standard multiset? Can you post a link please

http://codeforces.com/contest/706/submission/19810298 It should work, I tested it with a bruteforce solution and there was no difference, but of course I might be wrong. Edit : It works if anyone wonders :)

Can you light upon your solution? Your approach looks interesting. Implementing Trie is too mainstream for this problem. :P

exact same thing happened with me .... difference being that I could debug my solution after the contest ended :(

I see many solutions who got WA#5 in problem D, like me. Good round!

WA in #5 is probably from not considering that 0 is always in the set.

Yeap, you're right.

I knew that the problem D could be solved by using Trie but I failed to implement it ;(

same here...I had bugs in my remove number function...got it working 5 minutes after the contest ended. :(

This is the second time I know that a problem can easily be solved by trie but failed to implement it. I think tries are tricky to implement so people must have coded them once and use their own code every time I guess.

Solved D 5 minutes after the contest ended! I'm too slow!

I think, this contest should be RATED.

it is unfair towards people who waited for 20 minutes for each problem

I quite don't understand what everyone is so distraught by long queue of +/- 15 minutes. Every major competition. APIO 2016, CEOI 2016, JBOI 2015 all are really famous for their judging fuck ups. Why does CF need to make this unrated simply to prevent decrease of people's ratings, when such major competitions often end up deciding people's future and college etc.

The competitions you mentioned don't have time penalties.

When there are fuck-ups in our local onsite contests, we usually blame the system saying to the organizers that in respectful contests like Codeforces rounds such things would be considered very wrong and wouldn't be allowed. Codeforces should stay an example for a good platform with good contests.

I'm pretty sure every platform is allowed to mess up once in a while. The first time they did, they made the contest unrated. Fair enough.

About time penalty not actually mattering, really? You didnt feel that maybe if there wasn't the 1 submission per 5 minutes thing in APIO, your score would have not been affected?

It was a really bad idea to make Eran's contest unrated. Cuz now a lot of people are upset with the system's speed and it would be kind of unfair to leave it as it is.

E was very similar to problem G from Petrozavodsk Winter 2012 (standings)

(the problem is great anyway)

I think this contest should be rated. Judge lags were not bad than past contests.

umm... I wonder how to hack Q1. How did you hacked Question No.1?

of course because u didn't get WA :D !!!

No... This contest is much better than Round #365.

yeah but the same problem ' long queue '

no metter if it better or not

Pretest Passed at one shot 3 seconds before the contest ends. Am I the latest to submit ? :P ![](https://imgur.com/a/v2raK)

Making this round rated proves how unserious this website is

Submissions are being judged after 20 minutes. I came to know about my run time Error of question after 20 minutes. This round should be unrated. Many people would have been affected by this.

edit: nvm

What is the approach for D?

Use binary Trie https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems

Wow! I never imagined a trie can be used in this problem

Same approach :D. I finished debugging my sol two minutes late though.

At least you knew what to do!!

Any idea what Test 41 in A is? I assume it's one of the tests that was used to hack a bunch of solutions in A.

Precision Error,

One of my friend that has almost same solution but used float instead of doubles got WA on this test.

"In queue"for 15 minutes after submitting the question, has becomes a permanent feature of codeforces :(Make it rated please i have solved A and B under 20 minutes. and i am happy to do that !

`19793914 00:20:53 Hazemzz A - Beru-taxi Java 8 Accepted`

20 mins, 53 seconds is not ''under 20 minutes'' :)Make it rated please i have solved A and B under 20 minutes 54 seconds. and i am happy to do that ![user:latvian]

Nice contest! Brief statements. Unfortunately, finished D solution two minutes too late :/. Thoroughly enjoyable nonetheless.

In Problem C. I marked my dp[100005][2] with INF as 10e15 it gave a run time error. But when i use INF as 10e14 it works. Language used C++. Can anyone explain ? Thank you.

Edit1 : It's behaving in a weird manner. Sometimes i get correct answer but sometimes i get run time error in custom invocation. I will update once i get to know the reason behind it.

There are 10^5 numbers, so if you add 10^15 10^5 times, you get long long overflow. Maybe that's why

I was not adding them actually.I just initialised my dp table with INF. After that i was taking min of responses. It gave run time error on pretest1 itself. I later checked on custom invocation with 10e14 it works.

In c++ upto 1234567890123456789 is accepted(>1e18)..then its not possible that 1e15 will give any kind of runtime error :D Check again may be some kind of segmentation fault error must be there.

I used 1e15 keeping those 1e18 limits in mind only. Later i tried in custom invocation 1e14 works but 1e15 gives "runtime error: exit code is -1073741819"

Always better to keep it as -1 and then add additional checks :). I have made the same mistake before.

Agreed.

Waited for 20 minutes to get WA, why codeforces is so slow again? Will it be rated?

Only I get #WA41 on A?

"Print a single real value — the minimum time Vasiliy needs to get in any of the Beru-taxi cars. You answer will be considered correct if its absolute or relative error does not exceed

`1e-6`

."`cout`

just give the answer that its absolute or relative error does not exceed`1e-5`

.Fuck that shit, I`m out

A solution for D without using trie (though it hasn't passed the systests yet). Let's store all numbers in STL multiset. To perform the third operation, we can find y that gives maximal xor going from the leftmost bit to the rightmost. Given the 10^9 constraint for x, 30 to 0 is enough. Let's say we know some binary prefix of the answer, and that a number in multiset with such binary prefix exists. If x has 1 in this bit, we can just find the the minimal y with such prefix (using multiset.lower_bound()), and if it has 1 in this bit, then add it to the answer. If x has 0 in this bit, we can find lower_bound(answer | (1 << i)) and see if it does exist and isn't greater than answer + (1 << (i + 1) — 1), in order to guarantee the existence of such prefix in multiset, then add to the answer.

Is this solution for div 2-b correct http://pastebin.com/jrpYFphS, I lost so much time in contest because I was in queue, and now I can't submit a solution.

Just use upper_bound. No need to do all this stuff. :)

Solution

It will be unfair towards Eran who has created good problems, if this contest is rated

the lag in this contest wasnt as bad as the lag in the contest you are referring too, at most it was ~20 min, you could have moved on to some other question while it was in the queue

No it won't. Just enjoy solving the good problems and stop complaining. The queue wasn't long enough for the contest to become unrated.

Who cares about rate, it's all about learning new things...

I got a weird WA61 on problem C. I am sure about the idea, and probably the WA is because of checking whether we can have an answer. Why is my check wrong?

I've changed the way for checking the possibility to have an answer and now have an AC. Does anybody know why did this happen?

O(nmq) solution for E. AC in 2464 ms =)Can be improved to 2121 ms and 1669 ms with SSE.

I did it, too =)

http://codeforces.com/contest/706/submission/19808842

Have you tried combining your second solution with Duff's device?

That will not work for my cycle, because i have not only unrolled it, but also grouped some operations.

Nice. And here I coded standard treap hoping it'll pass. Turns out 12 seconds is the least it needs for my implementation :/

Can we expect editorial today itself??

will there be an editorial ?

Here was my approach to

D.It is easy to keep up with the set by using std::set and std::map to count the multiplicities.

The real deal is how to deal with the query ?.

First, change the given number to binary. We notice that we can take the high-value digits greedily.

Therefore, we do the following. We set

Xas the optimal number in the set. Iterate through the bits 29 0. If the binary form of the given number is 0, we want 1 there. If not, we want 0 there. If there are no numbers in the set that satisfies this, we would have to go with alternate path.Here's an example.

Assume that 111011, 011000, 101000, 000010 is in the set, and the original number is 001101. We want the first bit to be 1. Indeed, there are two such numbers — they are in the interval [32, 64). How do we check that there are numbers in that interval? By using lower_bound!

So we chose [32, 64). Now for the second bit we want 1 as well. Such numbers are in the interval [48, 64). We see that there is one. We want 0 to be the third bit, and such numbers are in the interval [48, 56). However, there are no numbers in that interval! Therefore, we would have to go with the third bit 1.

Continue this, and we would have our optimal

X. Now compareORIGINXORXandORIGINand return it. Complexity isI thought of this, but I couldn't convince myself that this is correct :/

Wow! Great idea! I thought about greedy solution but I could not implement it. As for me, you solutuion is better then in ediorial. Thank you!

Where is the editorial???

Kindly have a look at this test case generation program for Question 2 . I was unable to figure out why it was showing (invalid input verdict ) when I tried to hack this submission . (http://codeforces.com/contest/706/submission/[submission:19798157])

My code :

Please comment below if any one know the reason. I don't want to do that mistake again. But I was unable to figure out my mistake. (http://codeforces.com/contest/706/hacks/246947/test)

I think in hacking, you have to add a new line at the end of input

I tried that also but it did'nt work out .

test

There would be a extra space after printing values of each array in the above link but not in the original comment. Checker is strict for hacking maybe.

Have a look at these :

http://codeforces.com/contest/706/hacks/246936/test

http://codeforces.com/contest/706/hacks/246902/test

In both there is extra space at the end of second line.

Thanks I found my mistake .

You say there are 9999 values, but only print 9998

No I have print

`cout<<n;`

explicitly after the for loopFor hacking you have to give input, not input generating program.

No , If the inputs are more that 250 Kb size you are required to write a generator program .

Last line should be cout << 2 << endl;

See this

Extra space

in C anyone got WA in test case 18?

Me too, I set

`oo = 1e9`

, however, it should be`1e18`

.Turns out i was using INT_MAX for the max value (initialized value) for the dp table, but the sums can sum to be greater than INT_MAX!

i should have used 1<<60! such a silly mistake

Hope we will never meet that mistake again.

nice contest ,but slow system testing :P hoping to get high ratings

Sum of lengths of strings <= 100000.

The sum of lengths of all strings is at most 10^5, not the length of every string. So the worst case should contain all the strings with length , something like 315.

Total length of all string is

`1e5`

. Incase`n = 1e5`

, length of each string is just 1. Totally it is`O(n)`

.It was given in the question that the total length of the strings won't exceed 10^5.

Why did you change your comment? Nobody answered your question so far.

The number of operations is linear because every string is compared a constant number of times.

Thank you guys for making this awesome contest.The difficulty of problems is moderate for Div.2 contestants and have great and beautiful "solved" distribution.I kept thinking and implementing the whole contest.It's really exciting and fun.

Some personal experience: I got 2 RE on D for missizing the trie node pool and got 1 WA on C for a typo.When I start to handle E, I first thought to cope with it by splay tree(considering the difficulty of previous rounds) and failed to finish it.Right after the contest I figured out a better way(maintaining the position of original elements and do some interval add/distract, which can be completed in O(n) time because there is no online requests).

Long queue appear again in this contest.I guess this is caused by problem A.Maybe the special judge part in A make the judging machine laggy.

This contest is made by and for Div.2, this is awesome.Although the difficulty may seems lower than previous Div.2s(finish 3 and you and done, finish 4 for a high rank,finish all to go Div.1 directly), but it is really enjoyable for Div.2 contestants.

Hope you guys can make more great contests.

I don't hate this contest. I'm just expressing my bad opinion about the problemset, which I didn't enjoy, authors did their best anyway.

I do not consider this contest as "good". Here's a yellow point of view:

-A was okay, like normal A

-B was such a standard task...

-C yet another DP with same pattern. There was even a pretty similar problem on CF once.

-D come on, "code a trie" problem. There are many such problems in the internet. Seriously, even "find maximum xor" typed in Google would probably result in finding the solution immediately.

-E that was a fun one. Nah, just kidding :P If coding N treaps is a model solution, then wonderful problem 10/10. MrDindows did something awesome, check it out!

I'm not saying this contest was bad. But IMHO this contest should have been an Educational Round.

Which one?

This problem set is so much interesting. Really I enjoyed it to much.

Somewhat structured and verbose code for D: http://pastebin.com/Md2EtNXF (submission)

Can someone tell me why my solution to C (java) timed out?

I saw some other recursive solutions also passing, so did I make some mistake in the implementation?

Here's the code : 19801924

Thanks.

Edit : I got my mistake.

Someone can help me? In problem D, I'm use basicly pointers, in my computer it is ok, but in CodeForces gives Runtime Error.

Submission

I used only opinters, too. Check this code.

Why my all solution change to 'skipped' and I out of competition ?

It happens when someone cheats.

Why I get different answers between custom invocation and problem test?In 19790402 I got WA on test 79, However, I thought I got the correct answer when I used Custom Invocation.

What the problem is???I passed this problem by replace %ld with %d, but I do want to know Why I get different answers between custom invocation and problem test?

By the way, I'm glad to know how to cause this WA, since I thought there is no different between %ld and %d in GNU G++11 5.10 :)

Got 141 points, wow!

中文

Thanks for such a nice contest :)

where is the problem set ?

here.