Hello, Codeforces!

My name is Ivan Udovin, and I would like to say, that the Codeforces Round #344 will be held on Thursday (March 3, 2016 at 19:35). This is our first round, but it doesn’t mean that problems will be boring and not interesting. The problemsetters of this round are me (wilcot) and Ilya Kheifets (iliya785). Thanks a lot to Alex Vistyazh (netman) and unknown person (he don’t want to be added in the announcement) for testing our round. Also I’d like to thank Fedor Korobeynikov (Fedosik) for his awesome idea for task E.

We thank Gleb Evstropov (GlebsHP) for his help in preparing the contest, Maria Belova (Delinur) for translating the statements into English, and, of course, Codeforces team and Mike Mirzayanov for unique Codeforces and Polygon platforms.

This round consists of five problems. Main heroes of this round: Blake — the owner of the "Blake Technologies" company, and Chris — an employee of this company, and others.

Scoring distribution: **500, 1000, 1500, 2000, 2500**.

Good luck, have fun.

**PS.** Editorial is ready.

**PPS.** Congratulations to the winners:

**Div. 2:**

**Div. 1:**

I miss a normal codeforces round. I think this one will be interesting. Good luck to everyone.

There is a small typo in the article — while the article says Wednesday, the actual round takes place on Thursday. Could you fix it please?

Thank you.

A new round, and an new hope to become expert ^_^

Or pupil >:)

probably yes :(

Hope you'll have a good round, though. Good luck!

thanks, for you too :D

So finally u became 'Pupil' :D

but it is important to know who tested a round for us. Generally, a round won't be interesting if people see it was tested by a newbie, but higher ratings can draw more attentions, right? So, at least writing the tester's rating can be useful here. Alternatives,

Thanks a lot to Alex Vistyazh (netman) and an International Master (who don’t want to be ...If the tester was someone unrated (or a "newbie") would you refuse to participate?

I am not talking about unrated users, but newbies or low rated ones. There are many reasons why tester's rating also matters. see these comments: http://codeforces.com/blog/entry/19849#comment-247087

nice short announcement. waiting for an interesting problem-set and best of luck for your first round.

thank you my good friend, wish you all the best!!!! may the best coder win

why so many downvote on this comment :o

It is inertia. If it happens so that the first person downvotes the comment, the others are inclined to do the same. It is also true if the comment gets upvoted first.

This psychological phenomenon clearly manifests itself here and on other internet platforms where people can see how others vote. It is highly exploited in the real life, for example, in advertising or presidential campaigns.

By the way, if you are interested, it is one of the many cognitive biases :).

Then I'm upvoting every comment I think should get upvoted.

expert next goal

How long did it take you to become a specialist?

you can check his profile if you are interested to know

Why do they always add

Codeforcesbefore the round? Who doesn't know this much? Or maybe its just a safety measure to stop people from asking questions likeWill the round be conducted on Codeforces?In that case, you can change the heading toRated Codeforces Round #344 (Div. 2)Did

Codeforces Roundmean conducted on Codeforces? How about previous round such as 8VC Venture Cup 2016? NoCodeforcesstuff in its round name.Pretty sure about the fact that every

Codeforces Round #xxxtype of round has been conducted on Codeforces so far, not exclusively though, like 8VC,Manthan,etc.Supposedly, it means that the round was mostly concluded with the support of Codeforces staff, than some other company (like VK Cup, AIM Tech, etc.) hence, they add "Codeforces" before the name of the round.

And by support of Codeforces staff, I don't mean just the Polygon system, I mean the help of translators (Delinur) and other outside help (

~~Zlobober~~RIP GlebsHP)How did you cross out the word? I used MS Word to cross text off, but when I copy paste it here, the cross out gets cancelled.

<strike>your text here</strike>

power of html

~~Thanks~~~~I'm an idiot~~Well this might mean, I'm not really stating I'm an idiot :D

Are you...heisenberg?

Editor input:

`<s>Totally Krossed Out</s>`

Result:

~~Totally Krossed Out~~~~Let me try that~~There's also a "preview option" for these matters...

Let me try that

Thank you for burying me, though it seems like I am still alive.

nice pp

So what?

"Main heroes of this round: Blake — the owner of the "Blake Technologies" company, and Chris — an employee of this company, and others." I think there is tree problem :3 , the root of the tree is Blake and Chris is one of the leafs :D . it will be so interesting if that's true :D .

What is the theory behind this?

Problems will be like

As Blake is the CEO, he doesn't have time to solve this problem because he has bigger problems to solve, so he asks ChrisNo dynamic scoring please -_- Hope to see some interesting problems with good problem statement :D

Don't worry, usually standard CF rounds don't use dynamic scoring.

Thanks :)

Ufff.... seems I forgot to register on time. Solved the first task and found that cannot sumbit it. Can you please let me register still?...

Only in my device Google Chrome didn't open or brake Codeforses(last 30 minute)?

I might be the only contestant who got hacked on A. RIP :D

Don't worry. Many got hacked!

you have your friends...

2nd hacked aswell. motivation--

How can you see hacks of different people?

Go to status tab and filter out hacked solutions (in right)

Mom, got a camera, i am in a television!!!

Interesting problemset!

Can someone describe me solution for the fifth task ?

All I've came to:

You need to maximize value sum(A[j], A[j + 1], ..., A[i — 1]) — A[j](i — j) if i > j. Or value A[i] * (j — i) — sum(A[i + 1], A[i + 2], ..., A[j]) if i < j.

And print initialy characteristic + (diff > 0 ? diff : 0)

How to do this faster than O(n^2) I can't get:D

Then I supposed we will iterate over all

iand find indexjwith maximum value j*A[i]-sum[j] where sum[j] denoting sum of firstjelements forj>i. Similar way fori<j. But that again wasn't enough for anything faster :DYep, that's right. Here you can find how to do that in time with

O(n) preprocessing time.lol, some time ago I've tried understand this, but without success. Maybe now I'll come to success. Thanks for link)

Thanks. I heard for it normally, but I have never used it. I must learn several optimisations :)

We iterate the array. For ith index we will find the best position j, left to the i (it could be right instead of left, but we will compute the right in another iteration), which maximizes (this equals to change of the value of the array when we move jth element to ith position).

As I said before we do the same thing (almost the same thing, equations are little different of course) for right. Then, the answer is the value of the original array + max(0, max of all changes).

To find the best j for a particular i, we need to fiddle with the equations a little and represent every element as a linear line:

ps[0] = -ar[0]ps[i] =ps[i- 1] -ar[i]max_{1 ≤ j < i}{ps[i] -ps[j] -ar[j] *j+ar[j] *i} =ps[i] +max_{1 ≤ j < i}{( -ps[j] -ar[j] *j) +ar[j] *i}Now we can represent ith element as a linear line. ith line equals to

y=ar[i] *x+ ( -ps[i] -ar[i] *i).We first add the line 1. We then start iterating from index 2. When we're done with i (computed the result for it), we add the line i to our structure.

(To find the result for that position) When we're at a new position, let's again call it as i, we find the line which has the highest value for

x=i. We also need to increase this value byps[i].To find the best line, we can use the convex hull trick on a segment tree, since slopes aren't non-decreasing like in the case of traditional convex hull trick.

Time complexity:

O(NlogN)I swear, in next few CF rounds I will not hack! :(

How to solve C? I guess we have to sort three values i, ti and ri according to ri? How to do the same?

I did it with segment tree+two pointer. Phew! Lot of confusing code

I thought of solving the problem like this. Find maximum value of ri and it's position in input. Then all sortings done before this input will be useless. After this input, check for next largest value of ri and repeat this process. Obviously after finding ri we have to do something in array(I still need to find out more).

I thought along the same lines but this would fail for worst case as in:

Yea i thought of that case too but i think we can do something between finding next ri. Like if we say for t1=1, r1=10 and t2=2, r2=8 then we can say from 1 to 8 array is descending and from n=9 to 10 array is ascending. Now we choose numbers in array. I think it can be done nikitosoleil method(two arrays). I am not sure.

My solution is much more easier. I have two sorted arrays (increasing and decreasing order) and taking a look only at elements, that had changed their position. For every position I store will it be sorted at last time int dec or inc order. In first case I am placing in this position first unused element from dec array, in another case first from inc arr. You can take a look at my submission: 16494098 for better understading me. Hope that this will work. P.S. It was the first time when I have submitted three problems less than in one hour :) UPD: Failed.

UPD2: Bugged code, but right idea. Some little changes and AC: 16501782Damn! Ofcourse! Since we are only looking on right side of the segment for maximum, I could've simply done a suffix-sum calculation in O(M) lol

No wonder you were expert. :) Sometimes contest go bad, very bad. :(

In this and two contests before I have done stupid mistakes in one problem, but on the previous contest I have done stupid mistakes in all problems)

What I did:

Found the maximum number of sorted elements from all queries, from 0 to x

Sorted [0,x]

Then from that query looped to the end of the queires reversing the array from 0 to query's length, keeping track of what order was used last time. If the order changed, then reversed the array, otherwise did nothing.

I think your solutions fails for this test : in

I have hacked a similar solution with this test.

What is your test? I can not see it.

Sorry, now check again

I won't know until system tests are over, but I did the following: EDIT: Failed on test 13. I think the main idea is correct though, so check the last paragraph.

If there are n numbers, create an array of size n (orderings) of integers, initialized at 0.

Read input numbers and put them in a linked list. Create empty stack too.

Read managers. For each manager, set orderings[r] = t (1 or 2).

Set sorted = false. For i = n — 1 until 0:

4.1. if (ordering[i] != 0 && !sorted) list.sort(), sorted = true;

4.2. if ordering[i] == 1: pop from the left of the list and push to stack.

4.3. else: pop from the right and push to stack.

It's not exactly that, because when ordering is 0 you have to look at the last order, unless no sort has been performed yet.

I'm not sure about whether it's right or left for orderings 1 or 2, because I don't remember which one was nonascending/descending, nor the default order of list.sort(). But when ordering is 0 you always pop from the right (if no sort has been done yet, else you follow the previous left-right rule).

The idea is that if the largest sort is n — k elements, the last k are in the initial order. From there, the n — k — 1 indexed element is the biggest/smallest number left (depending on the direction of the last sort of that size), the list is reduced in each step this way, until you get to the empty string.

I simply took maximums of type_1 query and type_2 query except for the last query, if in case last query is for type_1 then i first sorted max(type_2) in non-descending order and then sorted max(type_1) in non ascending order,and vice versa for the type_2 query in the last query. hope it works... :)

Somebody know why KMP on problem D might give WA14? And how did you solve that problem? I thought of KMP, but now I see that I could use hashing also.

Check for overflow in your solution. Test 14 is a big one.

I used Z-function

Wow C has 1k submissions!! It took me lot of time to code C

I think a lot of them would fail System Test

From your earlier comment it seems that your solution is more complicated that it needs to be.

Yeah, prefix/suffix sums mostly ditch me in contests because I always end up coding segment tree

So, what was the hack cases for A and B?

I tried to hack for int overflow in A. But I am stupid there will be no int overflow. In B, I tried hacking TLE submissions but i failed! :(

There can be overflow Input 1 536870911 536870911

Only if you've used short int datatype, or char, or bool ;)

Answer is 1,073,741,822.

Answer fits in int.

There will be no overflow because input is restricted till 2^29 and if we 'OR' all powers of 2 from 1 to 2^29 we will get 2^30 — 1. Then adding we will get 2^31 — 2 which fits in int range.

536870911 + 536870911 is almost twice less than 2

^{31}.B: If you update the grid after each operation, worst-case complexity is O(k * max(n, m)).

Ah I see. I thought there is some tricky case...

Second problem with O(k*n) k = 100000 n = 5000 failed in hacking. So fast...

Same there:D

i was able to hack with this test case

WHAT ? :|

This gave me unsuccessful hacking attempt :\

`

why is this unsuccessful on bruteforce

Operation 1 is much faster than 2. (memory access time)

Even operation 2 doesn't seems to work atleast for me. Here's the solution i was trying to hack: http://codeforces.com/contest/631/submission/16492474

The submission used

`long long int b[n][m];`

so the memory is contiguous. (especially you specified`m = 1`

)Had it be

`b[5000][5000]`

your hack would be successful.Yes i think you are right. Others are doing this with m=5000 n=20 to fit into n*m <= 10**5

codeforces' server is very fast

Same here, I didn't get it. Wasted 30 min learning how to hack with generated input and trying to understand why it didn't work, and I in the end I just got some negative points.

I did exactly the same except of this

`cout << 2 << ' ' << 2 << ' ' << 2 << endl;`

I wrote

`cout << 1 << ' ' << 1 << ' ' << 2 << endl;`

But if i remember correctly for k=100000, it gave input data size was too large.

So i used k=10000

i choose 2 so that there will be cache problems with array

How was your input size less than 256bytes for k=100000?

You should use generator program for test case for large inputs.

You can write a generator program instead of manual input. That's the second tab of the pop up window after you click the "Hack" button"

Facepalm! I could have hacked atleast 2-3 submissions in my room.

I hacked 8 solution in n=5000 k = 100000 case :)

In my case it was not accepting n=5000 k=100000 due to large input size!

I used generator. :)

Good estimation is 10^9 ops per second (from my experience).

for Python also?

No, python is much slower (from my testing 40 times slower) and I don't recommend it as a programming language for contests.

10^9 is a good estimation for C++, C# and Java.

noticed my solution for B is wrong after locking it , so hacked 10 people :p

What's that special test case that failed 10 solutions?? o.O

TLE probably. I did an analysis sometime back, and I concluded that codeforces can compute approx 2.7x10^8 trivial instructions(assignment,increment, arithmetic +/-,stuff like) that in 1 sec. Anything more than that is TLE, and if somebody had 10^9 instructions/sec pass then compiler probably optimized something.

I wonder what was test 7 for problem D. I really can't figure out what was wrong in my solution... anyway, if A, B, and C all pass, it will still be a good result. :)

May be something like this:

3 3 3-a 2-b 3-a 1-a 2-b 2-a

Is the answer 1 ? I guess so...

I saw the test. Actually, my implementation of KMP algorithm was wrong. :'(

How to solve C?

Let's assume we have instruction 1-n. Everything before that instruction doesn't matter. So let's find the last instruction 1/2 — n. If that doesn't exist the number stays the same, if it does we have to take the smallest or the largest number in the array. After that we search for 1/2 (n-1) that is after our previous instruction and do the same process, but we also have to remember what was the last instruction that was made(if it was 1 or 2 so we know what number do we have to search for). We can sort the instructions and also use the set to get maximum/minimum and to remove elements(after we have used them already) so the complexity is O( (n+m) (log n + log m))

What if there are consecutive instructions like for n = 10 1 10 2 9 1 8 2 7 1 6 2 5 1 4 2 3 1 2 1 1 this will sort the array 10 times right?

After the first instruction we know, that result[10] is equal to biggest number in array, and it won't change, after the second one we know that result[9] is equal to smallest number in array without the biggest number — so smallest number, after third we know, that result[8] is equal to the biggest number in array without biggest and smallest number etc, you don't need to sort it every time

My submission is failing for test case #14 Can you check it? http://codeforces.com/contest/631/submission/16502485

At first I read OR as XOR in A. Anybody else coded for XOR lol

Give me five!) It taken 10 minutes to understand why WA2

I was confident about my code so I immediately went to check the problem statement. Wasted 8 minutes coding for XOR lol.

I've got sillier case: coded for 1-2 minutes, but couldn't get my mistake for 10 minutes)

Same here! Although I didn't wasted 8 minutes coding for XOR because then I just changed XOR to OR. I let it be O(n*n) rather than changing to O(n).

I changed it to O(n) by simply commenting the n^2 code.

Me too :)

I did it initially. But soon I could realize when sample test cases didn't pass on my local machine

SunitSwn

Lol same here. i even submitted the solution with an O(n**2) solution, but luckily it failed in pretest 1 only :P

My XOR even passed first five tests. No idea why. I got -50 because of this. :( Here's my solution Link

Ohh, now i recall that what i stated above happened to me on problem 2. The first one gave me ans as 42 with xor which i spotted before submitting. Yours passed pretests 2 too because you are taking max sum of xor of (A[i..j] + B[l..k]) where [i..j] may or may not be equal to [l..k]. It had to be equal according to problem statement.

Yes. I even asked an official clarification question so everybody can permanently see in the problem history how dumb I was.

Official answer was "There is no XOR. There is only OR. You are a fool."

(Part of it was not written but clearly implied).

I didn't know this problem history feature until you mentioned it.

What?

Oh dear I didn't mean to insult the problem setters, I was totally joking!

Your message was of course not rude at all. But my question DESERVED a rude reply, that's what my "joke" meant. I sure hope you at least THOUGHT it was a dumb question, because it was. :-)

Anyway, I loved the problem set. A and B were perfect difficulty but even after solving them the editorial showed a much better solution for A by thinking a little bit about the data instead of blindly coding, so it was a great lesson. And C was very doable, another excellent learning problem. Thank you!

Same!

problem A can't hack in n^3

I hope there will be me many TLE on problem A and B after system testing.

My hopes are broken(((

So, maybe authors could comment why they picked so tight input limits on problem B? Basically what I don't like about this — brute-force solution wasn't cut.

I too was disappointed. May be n.m <= 100000 should be alright. Why n,m <= 5000?

This was done to ensure that the solution should pass on a Python.

very nice problems and I enjoyed... I understood u love optimizing algorithms a lot :)) tanQ guys :)

wanted to act like an expert and went for C first without even looking at A and B. Spent too much time on C and could not submit B :v Looks like my being blue was just a fluke. I am not ready yet :v

And , as a result, today I will go back down to my rightful place. How the heck people solve problem like C in 20 minutes -_- . My brain feels dizzy after 1:15 hours of non-stop storming on C :/

I don't think it is a good idea to go for C+ right away if you are below like red or something.

But it is a good idea after solving first easy tasks (A, B and sometimes C) to read all others.

no, I know it takes something special to start right away from D or E. But C is kinda different to me. To solve C, you only need to be proficient in some basic algos. Whereas D and E often requires expertise on some special algos too. (Of course, we have seen exceptions in past contests where C was quite hard too, but i am just expressing the general scenario)

I only read C first in rounds which have both div 1 and div 2. For rounds with div 2 only like this, C is usually harder.

Isn't it the other way round?

By "rounds which have both div 1 and div 2" I mean rounds that have 2 separate contests, one for div 1 and the other for div 2 :P

so according to you today's C was hard? :v

That's kinda good to know. If I heard I had wasted 90 mins to solve an easy problem, it would be devastating

and after the system test, a lot of people failed on C which I passed. If only my brain worked 1 min faster :/ I just had to submit B (even the code was complete) :/

I thought 5*10^8 operations can be done in 1 sec :(

The tight input limit is somehow silly, why they didn't make it something like 1<=n, m<= 10^5 ,If they want a better algorithm.

http://codeforces.com/contest/631/submission/16492693 My solution with 5*10^8 operations passed

codeforce i want to say thank you !!!! such a interesting question and help full for improve my coding skills. again thank you.

without submitting a solution?

absolutely loved this contest, waiting for the next contest from wilcot and iliya785

Wow i thought i flunked this contest but rank went from 1.8k to 1.3k. I guess my rating will go down by only few points.

It feels bad when you fail something you spent 1:20 hrs on ;_;

Curse of the tourist. Never make fun of tourist ;_;

TLE in PyPy (16491742) and AC in Python (16500293) with exact same code. :|

Isn't PyPy supposed to be faster? Also, aren't Python/PyPy time limits supposed to be 5x that of default time limits?

As I know on codeforces time limits are the same for all programming languages.

Oh :-( Overflow... :-(

http://codeforces.com/contest/631/submission/16496133 vs http://codeforces.com/contest/631/submission/16500541

Overflow doesn't allow me to get AC from all of the problems of this contest. :-(

I know the feel: http://www.codeforces.com/contest/631/submission/16500781 vs http://www.codeforces.com/contest/631/submission/16496451

define int long long It's the future.

When will we see the rating change?

In very short time after the system test. :P

Auto comment: topic has been updated by wilcot (previous revision, new revision, compare).Can the Div. 2 D be solved using KMP? My approach was like I would compress multiple characters to single character and form a string. Then I'd use KMP to find the matching between the two. I keep tract of (l, c) pairs. I know their frequency and where they match. With this much information please help me find the answer. My code : http://ideone.com/yb5JCW

Thanks in advance.

I did the same, but I got WA7 because I made a mistake when implementing the KMP Algorithm... >< But honestly, I still believe it works. Maybe I should try again now.

i made a kmp too, searching for a match with the second text without first and last( they can have size smaller than in the first string ) and got WA 9 http://codeforces.com/contest/631/submission/16501632

AC using KMP

http://www.codeforces.com/contest/631/submission/16500781

It was a really nice problemset. Thanks!

I think there is a little problem. I solved two problems, you can check it in the standings (465th).

BUG！

10 days without contests?

New contests could be announced in between.

Congratulations..

contest was be very interesting. especially the last question is very interesting :) but I can not solve this in contest )

Thank you. We tried our best :)

How to sort 2d array according to first column? I know how to do it for 2 columns(using pairs) but how to do it when columns are more than 2?

Creating a custom struct/tuples with custom sort function or pair< int, pair<int, int> > should work

you can use vector of vectors :-)

My submission for C is failing for test case #14. Can someone check it? http://codeforces.com/contest/631/submission/16502485

how many operations the codeforces server do in one second? ◉_◉

What the hell man? Why did you stole my pic?

I think that you stole my pic

I think that you both are liers. It's my face on your avatars. Please ban.

anyone on how to solve c? i sorted queries on basis of ri>rj and implemented sorts while skipping ones with ri<r(i-1)&& i<j. some people solved it with segment tress . please explain it?

## thanks_in_advance

You solution has complexity. I suggest you read an editorial.

Hi ! iliya785 . i've read the editorial.and this implementation was result of it? help me in how should i begin implementing it?