Hello everyone! Codeforces Round #FF(255) is coming soon! We invite you to participate in this round, the round will be held in both divisions.

In this round, the boy DZY appears again! As we all know, he loves many things. This time he also brings us many interesting problems, which are easier than the problems in last round, but he still needs you help. In return, he will present rating to you.

Many thanks to Gerald for giving us much advice and helping us to prepare the round. Also many thanks to MikeMirzayanov, who created such a wonderful platform.

The problem setters are jcvb, jiry_2 and me. This is our first Codeforces round :)

Come and join us in helping DZY again, and you will take the high rating home!

Good luck and have fun! :)

**UPD**

In Div. 1, scores for each problem will be **500-1500-1500-2000-2500**.

In Div. 2, scores for each problem will be **500-1000-1500-2500-2500**.

**UPD**

The contest is over. Thanks for participating.

Congrats the winners.

Division 1:

Division 2:

You can find editorial here.

What round 255? You mean Codeforces Round #FF (Div. 1), Codeforces Round #FF (Div. 2), no? :D

Yep:)

According to russian traditions, you need to say "Yept" instead of "Yep"

easier than the problems in last round— sounds great! BTW, in last round every problem was solved by >=10 contestants, hard to believe that this time problems will be even easier. But if they do — it will be nice:)Surely it will be :) Wish you high rating ~

You were not serious about

easier problems, right?)Thanks for interesting contest. I personally think that problems were a little bit too hard. First 3 problems are enough to get into top-5, and nobody solved E... You expected such results? Could you please tell us what was your prediction of AC range for every problem before contest?

We've compared each problem in our round with the round #254. And we think our problem is easier.T^T

Hope this time problems could be more interesting than the last ones :).

We will try our best.

if i remember correctly, in the last round most of the problems were about you.

maybe now it is time for some revenge. ;) we will see.

hope not to be in your room :D like TC srm :|

Having skilled challenger in your room gives some advantage on CF. It increases chances of your wrong solution being cracked during round so you'll have an opportunity to fix it and get some points (instead of flat 0 without that challenge).

well, i am certainly not a "skilled challenger". :P

i actually had to resubmit my 250 (which explains my low score of ~

100) because i found bug in my code after i submitted.as it turned out,

4others in my room also failed on the same case as my first submission.P.S. ofcourse, your point about having a good challenger in your room is true. :)

LOL, but i changed nothing for you. your solution would have

Failed System Testanyway.but ofcourse it changed something for me, i got

+50points for making it. :)Challenge Succeededbut you should not have challenged the problem of a guy who wished you luck before the contest :P

In that case. Best of luck everybody.

LOL, nothing personal, as u know. :)

in fact, i don't even look at the

handlewhen i open code of participants in my room.Chinese(Hangzhou Xuejun High School) round again!

Looking forward to Raccoon Round :D

you give me A Pretty Good Idea on setting a Contest！ Racoon Round may come soon~

## FF :) С юбилеем!

Early annovzbbsbsnxnnsnd...

Seem that, DZY himself is the problem setter this time.

Is it easy??

It's obvious that the problems will be much more difficult than you've expected.

to khubi!

So cute profile picture :3

If you meet xiaodao

herselfsome day,you will find she is much more cute than the profile picture.>_<What do you mean? Lol, I don't understand xD Anyway, now I

havetomeet her :DWOW, super cute girl but sorry I hate China.

Last time I didn't really enjoy DZY problems... Wish this time better than last time...

Why Codeforces Round #FF(255) but not Codeforces Round #255 ?

because 255 is a

very big and specialnumber... It's the biggest numberchar(C++) orbyte(Pascal) can hold! (UPD: thanks vas.and.tor, who points out my mistake that unsigned short contains 0..2^16-1... Fixed.)I guess it's "unsigned char" in C++. Biggest "unsigned short" can be around 32767.

maybe this is why.

I like

he also brings us many interesting problemsand I like morewhich are easier than the problems in last roundThis is the first contest dzy493941464 hold. Hope him success in this contest

Thx :)

I think Div 1 E will be 3000...

That awkward moment when you don't even realize how hard Div 1 E is...

Many people know that feel, bro.

Ha ha. That's why I never read div 1 E..

NO 3000 but also NO 1000

Crap. It's DZY again. I'm scared.

You should also mention about the unusual time of this round so that no one might miss it.

It seems that the "Event Time Announcer" is wrongly showing this: Event Time in Moscow, Russia

`5:00`

While it's going to start in`17:00`

(Likely a mistake --> 17 = 5 p.m) So its start time doesn't really differ from the last one ;)i think what m17 means is that most CF rounds start at

1930MSK, but this one starts at1700MSK.easy problems are not good, because the rating matters how fast you solve the problems :/

Easi

erproblems are good, because it matters how many problems you solve and not just how fast you can solve them.First of all sequence of problems should be without large gaps in dufficulty, so a bit stronger contestant may easier overcome weaker one by number of problems and not just by time — we are competing in solving first of all, not in typing speed, right? Otherwise there is no difference — "500 guys solved 3 problems, 20 guys solved 4+" and "500 guys solved 1 problem, 20 guys solved 2+" are almost same scenarios for me.

As I mentioned in russian topic after last round, that round was pretty good — every problem was solved by 10+ users, nobody solved all 5 problems, number of AC is decreasing from A to E...

And I compared that round with "standard 1/5/50/500 round" (talking about number of users with first 5/4/3/2 problems solved). In my personal opinion rounds like previous one are way more interesting than "standard 1/5/50/500".

a math round?

It's only a normal CF round. :) Wish you high rating ~

Hello, ladies and gentlemen! It's DZY's show time! :)

I will get Violet

As it is Ramadan, is it possible to shift the contest at least 30min ? Current Contest starting time is same as the iftar time here in Bangladesh.

But great time in Iran! After the contest and system testings we have about 40 minutes to solve the unsolved problems and guess what after that! Iftar time! :)

And it's similar for Russia! (But just for their international time! As you know, Russia is really long country and I think the difference between it's leftmost city and rightmost city is something about 9 hours! Russians correct me please).

Russian timezones: from +3 UTC to +12 UTC exclude +5 UTC

In Morocco, we are 7 hours away from Iftar x) That luck though

what is that iftar thing?

http://lmgtfy.com/?q=iftar

I wanted to know a Muslim CF contestant's answer

why is Codeforces Round "#FF" ? 0xFF = 255, maybe the Round #FF is the next of Round #254 ?

That sounds Great! I hope it can be successful.

Kime gerek sen

orz Mao Zhuli

Who has a formulation for the third problem(buuble sort) for the TCO srm 627... Just the dp formulation and the recurrence relation pls?

I can't participate to this contest because of the flight to IOI place.

What does fuking FF mean?

FF is 255 in hex (base 16)

fast finish

it's a recursive acronym. It means Fucking Ff

I think the next contest will be "Codeforces Round #100" as: FF + 1 = 100 (base 16)

hmm, really odd email i received from Codeforces.

firstly, there's no

`#`

beforeFF, which is usually always seen in allCFrounds.secondly, "Codeforces Round

#254"? seriously?PS: take this as

constructive criticismso that next time these mistakes can be avoided.That means I'm not the only one. At least not the only one to notice :D

Maybe an automatic mailing system got confused: "Which name is round FF supposed to have? Oh well, I'll just use the latest one."

The round number is greater than 254. Codeforces rounds always have had number not greater than 254!

Oh my god... this is last round...

Next contest don't will... overflow byte..

No problem. Contests will start again from Round #0!

Hello from Taiwan.

thanks for our last chance to practice before IOI. Good luck and have fun everyone.

be careful! you will be demotivated if you failed a round just several days before competition. It may bring negative effect to the competition.. haha (at least I experienced this once.)

I already succeeded last topcoder round :D , I hope that I also succeed in this CF round.

Ah OK then, at least you already motivated by something :)

Anyway goodluck for IOI! :) It's very sad that I can't participate in IOI anymore :'(

Please prepare a readable and thorough editorial. Thank you :)

I hate when it says 'The solution is obvious' Waiiiiiiiit Nooo that is why I am here x)

For me, entering this round means not watching the World Cup Final. it's difficult trade-off...

No conflict between this Round and WCF ??!!! maybe you have no time for both

yes, I have at most 4 hours to sleep, if I do both.

Who cares about sleeping if World Cup final is just once in 4 years?

Soccer Maniacs wouldn't attend this round :v

Score distribution is a bit strange for me. 500 from Div1 used to be equal to 1500 from Div2, I guess, 1000-to2000, and so on. Today task C from div2 costs 2000, but task A in div1 (which used to be the same with Cdiv2) costs only 500. But, according to the logic of previous rounds score distribution, it must be 1000.

I understand, that authors know better, which one is correct, but isn't it a mistake?

UPD: Changed to 1500

I think This time task A Div1 Equal task B Div2

My Guess is

Div1 Div2

A = B

B = C

C = D

D = E

so the difference between two rounds will be A Div2 & E Div1

maybe I'm wrong let us see

After do contest I will watch FIFA World Cup between Argentina and Germany

div2 B shows 1000 in the contest.

I...don't understand why Div 2 Problem A begins with "DZY has a hash table..." Do the problem writers actually expect Div 2 contestants know what a hash table is? (Div 2 contestants that can solve Problem D/E are okay, but how about beginning contestants that can barely solve Problem A?)

Personally, this is approximately how I'd phrase it:

DZY has

pbuckets, one of which is colored red. Each bucket can hold one ball. For thei-th ball, DZY starts with facing the red bucket and turns clockwise forx_{i}buckets before putting the ball into the bucket in front of him. However, sometimes DZY cannot put a ball because the bucket he's facing already holds a ball. Output the number of the first ball that DZY cannot put.There are alternative solutions for this problem without hashtable,We can do Vector Add numbers and Vector Add module for every number and every time , you must check , Are this number contains in this vector or not :) Hope it help

I know there is a solution without hash table. (When I finished reading, I already got the solution using simple arrays.) However, the problem here lies on the wording. It feels like you need to know what hash table is (even if you eventually don't use it) just to understand the problem. My view is that problem wording should be as simple as possible, even if the solution can be terribly complicated.

Here's a hopefully comparable analogy:

You are given points on the plane, forming a polygon. It is guaranteed that the polygon has a dihedral group of order 8. (Test case has no picture of the polygon whatsoever.)

You will most likely say "WTF" on the last sentence. Compare:

You are given points on the plane, forming a polygon. It is guaranteed that the polygon will be symmetric like a square: when you rotate the figure by 90, 180, or 270 degrees, the polygon remains the same, and when you reflect the figure along some line, the polygon also remains the same. (Test case has a picture of the polygon, explaining the symmetries.)

that's just a bluff :P

we can see high number of accepted submission for that :)

In hash table, if you put more time one number than it is not collision, but in this problem it was colision :(

In problem A (Div1), are we allowed to change the numbers to zero? E.g. what is the answer for sequence (1 1 2 3) — 3 or 4?

4 — why shouldn't 0 be an integer?

Then I can't find an error in my solution 7083807 which got hacked =\

I think n=1

Oh no(

i asked this http://codeforces.com/contest/447, see below "Questions about problems"

The answer is 4.

and you also can change to negative number ...

Yes, even you can change it to negative integers.

According to the statement, you may change an integer to any other integer. Meaning that 1 may be changed for 0, -1000000000000, +1000000000000, 20 and -30 (even though some of this numbers are out of the the 10^9 value for array values given in the statement).

I tried hacking vatsalyarathod123 div2 C which should have given garbage value for N=1 but it returned correct answer I don't know why .

If n==1 , The result should be 1 , because there are not any elements again in array,,Every number implies to length

Hi, Can anyone please explain your approach of Div1 B / Div2 D ?

Thanks.

The mathematical proofs are maybe a little bit long but pretty intuitive. Obs.: 1) It doesn't matter in which order you do the operations. 2) You can let 0<=l<=k be the number of line operations (and take the best variant at the end). 3) For a fixed l, use 2 priority queues to calculate the results for l and k-l elements picked both for rows and columns. 4) Combine the result for l (on rows) with the result for k-l (on columns) with a little bit of maths. 5) Don't forget about long long.

Is this equivalent to the greed solution? In my solution, at each step, I would select the best row or column (the one with greatest sum) using two PQ. I don't know if greedy works (couldn't prove it), but it really feels like it should work. No idea why WA. :(

I got WA on pretest 4 doing the same thing!

It doesn't work.

2 3 6 1 1 1 1 1 1 1

Sometimes you don't want to select the best row in order not to start getting negative sums.

It doesn't work. Consider 1 3 10 1 1 1 1

i'm just guessing here, but did u consider that every

row's sum reduces bypduring everycolumnoperation (and vice-versa)?Yes JuanMata. It looks like Greedy is a bad idea. (Greedy is almost always a bad idea. I will try to remember that next time) :(

Actually there is a huge greedy part in the solution. You just have to be sure when you are using greedy algorithm, you should have proof or something (maybe not very rigorous).

The greedy part here is that if you look at choosing rows and columns separately, when it's about rows, it's always right to choose the largest row. Same hold for columns. Than it's easy to solve this 2 problems separately and merge them. You're gonna need to brute force how many rows you choose.

Forgot proof of a greedy strategy. Choosing largest row is optimal, because: (1) The order of rows chosen doesn't affect the final score; (2) Assume in the optimal solution the largest row was not chosen. Then, swap the largest row with any other chosen row. Obviously the score will increase, hence contradicting the optimality of a solution.

You can also prove that you can choose just rows at first and then choose only columns. I guess the details are already posted (at least in the editorial), so I won't go further into details.

No, its not equivalent. You solve the problem for only rows and only columns separately, and then choose how many rows and how many columns to use based on these results. The key observation is that each row operation reduces the results of each following column operation by p, and vice versa, so the total score is ScoreRows+ScoreColumns-NumRowOperations*NumColumnOperations*p, regardless of the order in which you do the row and column operations — this is because for each pair of RowOperation and ColumnOperation whichever comes first reduces the result of the other one by p, and there is a total of NumRowOperations*NumColumnOperations pairs.

Can someone help me to understand why my solution for div 2 problem E is too slow to pass test 9?

I use segment tree + lazy updates.

Thanks.

In Problem C,

DZY Loves Sequences, I made a minor mistake of initialising a variable to 0 instead of 1. So naturally, it gave WA. But after correcting the mistake and trying to re-submit, it says that`The exact code has already been submitted`

, and I could not submit it. How is it possible?P.S. I had saved the file.

I am being hacked at 17:57:37, The Codeforces send me the Announcement at 18:59:25, and I am very surprised about this (so bad)

Sorry if this is a stupid question, but how long does it usually take before the ratings are updated?

It's not stupid! I've been asking this question from myself since i've been taking contests! It never has a fixed time. It usually takes half an hour before the system testing part and half an hour (or even more) after that for rating updates :)

my idea for C div 2 is split the sequence if it's not an increasing subsequence, and join with the neighbour if possible (change 1 number from sequence left or right, and made strictly increasing seq)

here is my submission http://codeforces.com/contest/447/submission/7087449

any other ideas or my idea wrong ?

You can merge three consecutive segments(increasing sequences) also if the middle segment contains only one element and the first element of the right segment > last element of first segment + 1 .

hmm, cant think of test case for something like that while contest

anyway, thx for the answer

edit : my solution just lack +1 to the output if the max sequence isn't obtained from 2 sequence :)

can anybody explain me how to solve div-2 D . thnx

I encounter a strange issue during the contest. my ID became duplicate and every time I refresh my submission page its contents were different !

and when I locked my problem C ! (notice to contest time running!)

and some seconds later :

I deleted all my codeforces' cookies during the contest but still nothing were changed!

what was the problem MikeMirzayanov?

I'll investigate it. Thank you. I'll exclude you from the rating. It seems somehow you were registered twice (race condition?).

Yes, You're right. I have registered twice because I didn't see myself in registered users. Interesting racing condition!

why is system testing unusually slow today?

I will never believe in Chinese authors' word about easiness of the contest, specially of dzy493941464 :(

Who's idea to make C and B same points. Oh, well done really, Solvers of B is 6 times more then C :

64 * 6 ~ 343

why most of div2 C submissions failed system tests ?

can anyone give me the tricky test case which most contestants couldn't pass ?

I'm not exactly sure whether this is covered by pretests or not, but does your program work for

`10 1 2 3 10 4 5 6 10`

? (Answer is 5; take indices 5 to 9 and change the middle 10 to something low. (Or indices 1 to 5.) You cannot change the middle 10 to 3.5 to take indices 2 to 8.)I'll guess just some cases:

n=1

the optimal subsequence takes 0 changes to make

the changed element is the leftmost/rightmost

I missed the second point. :(

Just added : if(!ans)ans=n;

Became AC

some forgot to check whether two segments of strictly increasing order are able to be merged or not, for example:

6 1 2 3 3 4 5

the two segments are [1, 2, 3] and [3, 4, 5]

these cannot be combined to form one strictly increasing sequence.

Try: 2 1 1 Answer should be 2

thanks all , I found the test case that my code didn't solve correctly

5

1 2 10 4 5

the correct answer is 5

DZY definitely starts to please me.

three people scored 1134 points, and they took the (joint) 254th position.

this unfortunately means that nobody could take the 255th position in the 255th

CFround. :(What a very sad thing, you made me cry -_-

I hope you can recover from this horrible shock soon.

Let's see the good part of things — in the div2 contest we have: 255, 256 and 4 x 2048 placers.

I got tle on test case 9 in div2-Q5. I used segment tree. was that too tight for the time bounds?

this is my code, possibly someone could suggest an alternative -> direct link

I have not tried the problem but maybe you could get the fibbonacci number using matrix exponentiation !

i precomputed and stored the Fibonacci in O(n), and used it as a hash to get a direct access in O(1) while updating. I don't think that is the issue or m not sure.

Maybe problem with tree array size or recursion? When i downloaded your code and run it on simply test like this: http://morse.swirski.name/pastes/l6hriqm93kn5wx5gvxckznn0ibd5zvh program crashed in build_tree() function.

When i change tree[] size i don't have this problem. But i'm not sure, cause it was on Windows 7 x64.

P.S. Sorry for my english.

if the solution did crash in build tree function, then it would had not run in that case. I checked the log and it seems that the tree was built perfectly but the program ran out of time while processing the M queries.

Wait... your update is logarithmic? You stop recursion only when low==high (in leaf). So update is too slow in my opinion (You must visit every leaf in (l, r) ).

Why DIV2 problem C's test 41: 6 7 2 3 1 4 5 answer is 4?

change 3 to 0

thank you.

Oh, I see.

Correct segment for ex.: [3->0 1 4 5]

After change, it can be "7 2 0 1 4 5". So the answer is 4.

Nice contest :D

Excuse me. But why my rating hasn't updated? I found that everyone's rating has been calculated but mine hasn't done.

Oh, sorry. Only Div.2 competitor's rating has been updated.

You can view country wise standings here. Send your hugs or bugs here.

Div1C http://www.spoj.com/problems/ANIL_PRO/ or http://www.hackerearth.com/problem/algorithm/fibonacci-updates/

Yes, I really appreciate an opportunity to test my solution for WA/TL on spoj during CF round, but I don't think it is a good idea to give such problems on CF rounds.

I am sure it wasn't on purpose. It's impossible to know all problems from all contests/online judges. And it seems that it is not so easy to google the statement of this problem.

I am not sure that it is easy — did not tried to google this one, already seen it on SPOJ before)

But now I tried to search for

fibonacci updates array query problemand some other similar requests and both of these problems are at first page)I wouldn't be so sure. Just keywords from the problem statement, plus where to look (I always add "online judge" when I'm looking for a problem without specific source competition).

Yes, you are right. I tried another search queries and failed to find this problem, but it is definitely not so hard to do this and authors should have do that.

Did anyone try to solve Div2 C using two pointers?

Is the contest unrated for Div.1??? The rating of Div.2 was updated, but Div.1 not.

It went well and there was no announcement, of course it's rated. It just takes a long time for some mysterious reason.

LOL, it's like this was a

Div-2 onlycontest. :Dseriously, i guess it's just a small system issue. i'm sure ratings will get updated soon. :)

What asymptotics should be in Div2-D? I had O(pk) (I hope) and got TL. Now I wonder is it too bad or just Python?

Should be O(k logn + k logm)

Solution from editorial works in

O(k*log(n) +k*log(m)); however, it is possible to do it inO(k* (n+m)) and fit into TL easily (7093794).Upd. This solution is wrong (i described problem here). But you still can pass system tests with it)) Changing long into long long to fix overflow issues will make it correct, but with long long it does not fit into TL.Is long long that much slower than int? Is Codeforces on 32bit machines?

Yes, it is ~2 times slower.

You may change

long si[12000],sj[120000];intolong long si[12000],sj[120000];in my solution and it will work >2s.i'm hoping that the ratings of

Div-1will be updated before the World Cup final starts.i'm hoping that the ratings of Div-1 will not be updated

Why DIV2 C test 27 1 1 2 3 4 answer is 5 (not 4)?

change first 1 to a 0.

answer is (

01 2 3 4) (i.e. make the changea_{1}= 0).Can someone tell me why this submission is giving Runtime Error?

Something isn't right here...

Aah..OK.I failed to notice this during contest :(

its very bad contest

Round Stats

In question C. DZY Loves Sequences

Shouldn't the answer of (testcase #27) 5 1 1 2 3 4 be 4? Value of ai can never be less than 1.

Read the problem statement carefully ... It says change one number to

any integeryou want.I don't see why we need all the complicated logic in the editorial for Fibonacci problem. We can simply precompute the first 300000 values linearly and store them in an array.