Howdy Codeforces!

Come join us for a trip to Bovinia with everyone’s favorite munchkin Kevin Sun (ksun48) and his sidekick Nicky Sun (nsun48)! Codeforces Round #334 (for both divisions) will be taking place on December 1st, at 6:35pm MSK. The problems were written by Alex Wei (yummy), Michael Kural (pi37), and myself, Yang Liu. As proud Americans, we’ve themed all of our statements around the most glorious cow (and its many uses in life).

We are immensely grateful to GlebsHP for his guidance and suggestions, without whom we would not have a balanced problem set. In addition, we would like to thank MikeMirzayanov for creating Codeforces and Polygon, as well as Delinur for translating our problem statements to Russian. Finally, we would like to give a huge shoutout to Daniel Chiu (waterfalls), Kevin Sun (ksun48), Nicky Sun (nsun48), Weihang (Frank) Fan (pobelter), Ray Li (abacadaea), and Girishvar Venkat (numbertheorist17) for testing our problems and providing feedback.

We wish you good luck and hope you enjoy our problems and cow jokes. (We’ve milked our brains quite thoroughly for puns.) Come hop on the next cattlebruiser for Bovinia!

(Per Codeforces tradition, we will announce the score distribution just before the contest.)

UPD 1: Some added thanks to AlexFetisov and winger for also testing our problems.

UPD 2: The scoring will be standard (500-1000-1500-2000-2500) for Div 2 and 500-1000-1500-2000-3000 for Div 1. Good luck and have fun!

UPD 3: System testing is done! Congrats to the winners.

Division 1:

Division 2:

UPD 4: The editorial is posted here.

Hope everyone enjoyed the contest! Comments about problem quality, etc. are also appreciated.

moo

mooo?

mooo

Please don't be rude! Speak in english :(

MoOOooOoMooOOoOo MooOOOooMooOooooMoooOooo, MooOoooOMooOoooo MoooOOooMoooOOOOMooOOoOoMooOOOOoMooOoOoo MoOOOoOoMooOoooOMooOOoooMooOooOOMooOoOOoMoooOOooMooOoOOO.

Oh, I'm wondering...

Will the problem statements be like this?

Moo?

MooooOOMOoOOOOMOoOOOoMOOoOooMOooOoOMOOooOOMOOoOoo 1 — MooOOoOMOoOOOOMOoOOOO

http://www-personal.umich.edu//moo.txt

:)

MoOOOOOoMooOoOOoMooOoooOMoooOoOO MooOOOooMooOooooMoooOoooMoooOOooMoooOOOOMooOOoOoMooOOOOoMooOoOoo MooOOOOoMoooOoooMooOOoOoMoooOOooMooOooooMooOooOoMooOOoOo MooOOoOoMooOoOOO?

MoOOooOoMooOooooMooOooooMooOOooOMooOOoOoMoooOOooMoooOoOO?

who is interested in putting MINUS, go ahead.....

https://www.youtube.com/watch?v=mFfIIdK2cgM

findtheinvisiblecow.com

Looking forward to it!

Codeforces is getting colorful these days~

It will be continued... Because the competition authors are competing with each other:D

Good Luck & Have Fun :)

"Farmer John and Cows" are having a good day!

codeforces round starting times are going to confuse me...

If you are not into puns, this round may tear you up. :P

Even those corralled minds who don't bullieve in excellent puns veal surely be mooved by our impeccowble wordplay.

MoOOooOoMooOooooMooOooooMooOooooMooOooooMooOooooMooOooooMooOooooMooOooooMooOooooMooOooooMooOooooMooOooooMooOooooMooOoooo

is it a beef burger next to the cow?

Yes :)

Now this blog is what I call nice and precise announcement and I bet the statements will be really funny unlike the previous one.

Very amusing blog :D Hope for some delicious problem set and saturating solutions and hacks :D

`MMM... juicy beefs`

MoOOOOoOMooOOoOoMooOOoOoMooOOooO MooOOoOoMooOOOOoMoooOoOOMooOOoOoMoooOOoOMooooOoO MooOOoooMooOoooo MooOoOOOMooOooooMooOooOoMooOOoOo!

I'm sorry if it's a little bit racist but your skin color option on that drawing is pretty interesting.

I don't think it means what you think it means.

I wonder what

~~skin~~fur colour you think bears have.Could you add Cow++ compiler to Codeforces please?!

NOOOoooo

(Would add a picture of cow saying this if I had time :P)

^^Challenge: Change position of at most 2 matches so that cow is looking in oppposite direction :) (it's possible ;) )

Opposite direction relative to cow?

If you're looking for answer/spoiler it's here, find puzzle 3.

:D

MoOOOOoOMooOOoOoMoooOOooMoooOOooMooOoOOoMooOOoOo MooOOOOoMoooOOOOMoooOOOOMoooOOoOMooOooooMoooOooOMooOOoOoMoooOOoo MooOooooMooOOooO MoooOoOOMooOoOOOMooOoOOoMoooOOoo MooOooOoMooOOoOoMoooOOooMoooOOooMooOOOOoMooOOoooMooOOoOo.

MoOOooooMoooOOoO MooOooOoMooOOOOoMooooOOoMooOOOoOMooOOoOo MoOOooOoMooOoOOoMooOoOooMooOOoOo MoooOoooMooOOOOoMoooOOoo MooOooooMooOoooOMooOOoOo MooOooooMooOOooO MoooOoOoMoooOOoo MoooOoOOMooOoOOOMooOoOOoMoooOOoo MoooOoooMooOoOOOMooOooooMooOooOOMooOOoOo MoooOoOOMooOoOOoMooOooOoMooOOoOo.

MoOoOoooMooOoOOOMooOoOOoMooOOOooMooOoOOO MooOOOooMooOooooMoooOOoOMooOoooOMooOOoOoMoooOOoO MooOooooMooOOooO MoooOoOOMooOoOOOMooOOoOo MoooOoooMooOooooMoooOOoOMooOooOOMooOOoOO MooOOoOOMooOooooMooOOoOoMooOoooOMoooOOoo'MoooOoOO MooOoOOOMooOOOOoMoooOooOMooOOoOo MooOOOooMooOooooMoooOoooMoooOOoo?

MoOOOoooMooOooOOMooOooooMoooOOoOMooooOOo MoooOoOOMooOoooo MoOOOOoOMooOooooMoooOooOMooOoOOoMooOoooOMooOoOOoMooOOOOo!

Feels like I came to zoo!

MoOOoOOoMooOoooO MoOoOoOoMoOoOOooMoOOOOOoMoOOOOooMoOOoooo / MoOOOOoOMooOooooMoooOooOMooOoOOoMooOoooOMooOoOOoMooOOOOo, MooooOoOMooOooooMooOoooo MooOOOooMooOooooMooOooOoMooOOoOo MoooOoOOMooOoooo MooooOOoMooOooooMoooOoOo!

?

Auto comment: topic has been updated by desert97 (previous revision, new revision, compare).Sadly, bad time zone for this one. Moo.

ommoommoommommooommoooomommoommmommmmommomoomoomomommmmmommommoo

ommommmmommmommoommoomomomommmmmommooommommommmmommoomooommoomom

ommoommoommommmmommmoomoommooommommoomomommmoommommmmmom

I challenge anyone who thinks themselves good at cryptography to decode this message :)). I split apart the message into multiple lines so that it fits into the screen, but everything should be in one line.

flag{I_love_codeforces}Split into blocks of 8 characters. o = 0 m = 1

ASCII COWDEMoOoOOOOMoooOoOoMoooOoOO MoooOoOOMooOoOOOMooOoOOoMoooOOoo MooOooooMooOoooOMooOOoOo MooOooooMooOoooO MoooOoOOMooOoOOOMooOOoOo MoooOoooMooOOOOoMoooOoOOMooOOOooMooOoOOO MooOooOOMooOoOOoMoooOOooMoooOoOOMoOoOOOOMoooOoOoMoooOoOO MoooOoOOMooOoOOOMooOoOOoMoooOOoo MooOooooMooOoooOMooOOoOo MooOooooMooOoooO MoooOoOOMooOoOOOMooOOoOo MoooOoooMooOOOOoMoooOoOOMooOOOooMooOoOOO MooOooOOMooOoOOoMoooOOooMoooOoOO...

are you ok?

It's almost obvious. rpeng has developed some kind of encoding using only 4 symbols: "M", "O", "o" and " " (space). He's trying to communicate with us using that system, hoping, someone is smart enough to figure it out.

May be just replaced A,C,T,G of DNA with Moo and space and just posting genome of cow ?

MoOoOOOOMoooOoOoMoooOoOO MoooOoOOMooOoOOOMooOoOOoMoooOOooMoooOOoOOoooOOOoOoOoOoOoOoOoOOoOO MooOooooMooOoooOMooOOoOo MooOooooMooOoooO MoooOoOOMooOoOOOMooOOoOo MoooOoooMooOOOOoMoooOoOOMooOOOooMooOoOOO MooOooOOMooOoOOoMoooOOooMoooOoOOMoOoOOOOMoooOoOoMoooOoOO MoooOoOOMooOoOOOMooOoOOoMoooOOooMoooOOoOOoooOOOoOoOoOoOoOoOoOOoOO MooOooooMooOoooOMooOOoOo MooOooooMooOoooO MoooOoOOMooOoOOOMooOOoOoMoOoOOOOMoooOoOoMoooOoOO MoooOoOOMooOoOOOMooOoOOoMoooOOooMoooOOoOOoooOOOoOoOoOoOoOoOoOOoOO MooOooooMooOoooOMooOOoOo MooOooooMooOoooO MoooOoOOMooOoOOOMooOOoOoMoOoOOOOMoooOoOoMoooOoOO MoooOoOOMooOoOOOMooOoOOoMoooOOooMoooOOoOOoooOOOoOoOoOoOoOoOoOOoOO MooOooooMooOoooOMooOOoOo MooOooooMooOoooO MoooOoOOMooOoOOOMooOOoOo

I am sure if rpeng was bellow than a yellow, he would get lots of downvotes. But it was funny

So many colourist on Codeforces spreading colourism!

what happen if rpeng was

red? it is not ayellowtoo :DHe's from USACO. That explains the mooing a lot.

cowforces !! =D

CowdeMoorces :p

wanna be blooooooooooooooooooo

After removing all the fur on the cow, will we get a black one or a white one?

Me after reading

allthe comments to this post.You could have formed an M on the left from the boundary between black and white above the legs!

Nice idea, I wasn't creative enough at that moment :P

I think it has been a long time since Delinur translates English problem statements to Russian.

moo! :))

it reminds me Ben (in Barnyard).

This is actually a picture of Otis, Ben was his dad.

lol :D

An attractive post.. It's really tempting to register.

The comment is hidden because of too many cows, click here to view it

https://www.youtube.com/watch?v=mFfIIdK2cgM

MoOOooOoMooOooooMoOOooooMoOOooooMooOooooMooOooooMooOooooMoOOooooMoOOooOoMooOooooMooOooooMoOOooooMoOOooooMooOooooMoOOooooMooOooooMoOOooOoMooOooooMooOooooMooOooooMoOOooooMoOOooooMooOooooMooOooooMoOOooOoMooOooooMooOooooMooOooooMoOOooooMooOooooMoOOooooMoOOooooMoOOooOoMooOooooMooOooooMoOOooooMoOOooooMooOooooMoOOooooMooOooooMoOOooOoMooOooooMooOooooMoOOooooMoOOooooMooOooooMoOOooooMoOOoooo MoOOooOoMooOooooMooOooooMoOOooooMoOOooooMoOOooooMooOooooMooOooooMoOOooOoMooOooooMooOooooMoOOooooMooOooooMooOooooMooOooooMooOooooMoOOooOoMooOooooMooOooooMooOooooMoOOooooMooOooooMooOooooMooOooooMoOOooOoMooOooooMooOooooMooOooooMoOOooooMoOOooooMooOooooMooOoooo!

Happy

AnniversaryCodeforces Round!!Why

"Anniversary"? Because 334 is a very famous number in Japan!!Kinda strange to see a comment here that doesn't mention cows :)

Wheream I?!Damn it. Came 4 min before the start. Forgot about registration.

Auto comment: topic has been updated by desert97 (previous revision, new revision, compare).I want to participate but the light will be switched off in 1.5 hours because of Ukraine’s blockade of Crimea :(

Won't it be fair to cancel all Ukrainians registrations to CF rounds until Crimea gets the light? CF admins should be more patriotic, I think.

I'm sure that if you take any arbitrary moment of time, there will be at least one town without light in our homeland. Any way, the contest is prepared by Americans.

I suggested only to temporary ban Ukrainians because they are to blame for the blackout. CF admins live in Russia and CF is hosted in Russia. As one American said: "By uniting we stand, by dividing we fall!".

Ukrainian CF users are not "to blame for the blackout".

As far as I know Ukraine is a democratic country, so Ukrainians should share the responsibility for the actions of their state. Am I wrong?

I can't speak on the part of the whole Codeforces community, but I think we should stay as far from politics as possible.

I thought it start at half a hour later.LoL

I thought it was going to start an hour later... I guess I'll check the time more carefully next week =/

Today is the ****ing #WA6 day!

Fuck! Didn't wade through Div2B again...

How to solve Div2E,if for odd k?

Grundy function. if k is odd it's same as k=1. If 2n is even, {2n} -> {n, n, ... ,n} (odd k times), so f(n) xor f(n) xor f(n) xor ... xor f(n) = f(n)

Very nice problemset!

Thanks rng_58! Glad you enjoyed it! :)

Same for Div2! A very nice distribution of number of rank/number of solved problems. And extremely well-written indeed. Kudos to problem setters

First 2 problems are OK. 3rd problem too easy. 4th problem too hard.

care to give an explanation for 3rd problem Div2?

Maximum sequence is greedily calculated -> number of alternations between 0 and 1.

There are 3 possibilities -> you can't increase it, you can increase it by 1, you can increase it by 2.

If you have more than 2 same chars in a row -> you can increase sequence by 2. For example 01110 -> can increase to 01010. Or 101000010 -> 101011010.

If you have 2 same chars in a row in more than 1 place -> can increase by 2. Example: 001010110 -> 101010101

If only 1 sequence of 2 same chars -> can increase only by 1. Example: 010101011010

No duplicates found? Can't increase

solution with your idea 14606578 solution own idea 14592698

In other words take min(n, len + 2) where len — is the maximum sequence calculated for original string.

hacked 3 submissions of problem B div2 with the same testcase. looks like the pretests are weak and lots of people are gonna fail system test.

What's the idea for Div2b? Tried to solve it during all the contest

Binary search?

How to check the ability to feet size less then for n^2?

It's not binary search, you can solve at O(n) this is my solution for div#2 B: 14607361

i think in binary search but i dont know apply here, please some help me!!

Suppose with K boxes of size S you can pack all your cowbells, using the optimal way of packing. Then, you can binary search on size S to find the first S such that you can pack all your bells.

Now, the optimal way of packing given K boxes of size S is pack as many pairs of biggest and smallest bells together if that fits within size S. otherwise you need to pack the bigger ones individually.

Greedy solution seems to work. Try to put the smallest bell with a big bell so that you minimize the number of boxes, as well as minimize total size.

The idea is that first we put the first

`k`

cowbells ofNON-INCREASINGsize into different boxes, then if the boxes are over and there are still leftover cowbells, then we combine the leftover cowbells with the ones already present in the boxes by taking the leftover cowbell with the maximum size and adding it to the box having the cowbell of minimum size(box has just 1 cowbell), and continue this until all the cowbells get a box.Then, the maximum size can be found easily from all the boxes.

Update : 14604784

Coding in cow style :P

14591309 14595399

div2 D was a pure math :)

hacked a solution for the very first time today!! :D

and actually 4 of them(Div 2 B)! :P and then realised even I'm gonna fail system tests because of a very silly mistake :/

lol I wish I could hack my own solution and get at least +100 :P

Maybe someone can help me to find mistake in my solution of Div2 B

604B - More Cowbell?Submission (on C++):

14597269Try this case?

5 3 2 9 9 9 11

Thanks a lot! As usual very simple... My bad.

'5 3 2 9 9 9 11' case is not valid. Because '5 3 2' is descending.

Auto comment: topic has been updated by desert97 (previous revision, new revision, compare).Respect to ko_osaga's Div1A solution http://codeforces.com/contest/603/submission/14586174

yes it's good, it same with this solution 14606578

Could anyone please explain, why this solution of Div2B fails on test 10?

try this test case:

you'll understand what's wrong with your program.

4 2

1 2 3 4

the answer for this test should be 5 but your program outputs 7.

Thanks!

Eh, at least now I have a cool color :D

Pupil forever. ._.

We'll get through it ;)

Hope so! :D

Petr : bye bye top 2 :|

Чему радуешся сам сначала дотянись до такого уровня а потом говори

mooooooooooooo

Petr the Great !!! Petr the Great !!! Petr the Great !!!

you're a cow Sajil

How long does he need to NOT participate in order to get to

div2back again? ;)He won't unless CF changes its criteria of participating in Div 1 to something more then 2964. His rating will be stuck at 2964 if he doesn't participate which is way more then the current limit/cap for Div 1 contests (1700??)

damn! I made such a silly mistake in B. instead of 2k-n, I did k-n/2. -_-

Can someone please articulate why

`2k-n`

is correct while`k-n/2`

is wrong?Test these cases:

You see,

`k - n`

alwayshas to be equal to`- n / 2`

. Now let's invert the sign and we get the equation`n - k = n / 2`

(read this as: subtracting`k`

from`n`

is the same as halving`n`

). In order for these two computations to be equal we should demand`k`

to be always the half of`n`

.Sometimes you get lucky, when

`n / 2`

rounds to`n - k`

, e.g. when`n = 5`

and`k = 3`

, but only sometimes ;)SC

Why my submission div2 D had verdict Accepted, but now has verdict Skipped? 14603287

Hi everyone,

I'm currently developing a new Elo-based rating algorithm for large ranked matches such as programming contests, hopefully with a firmer statistical basis. Some goals are: faster convergence, no inflation, reduced sensitivity to unusual performances, and simplicity. The paper writeup is incomplete, but I've made the code available at https://github.com/EbTech/EloR

CFratings.txt contains everyone's Codeforces rating as computed by the algorithm, as well as the performance and delta of your most recent match. I assumed all events except the Educational rounds are rated, since I don't know where to find that information.

It says I'm barely yellow, with a rating and position which I haven't held for 15 months. Srsly?

The scales are not directly comparable. My list has fewer reds, and you are still more than half-way from orange to red.

But actually now that I look more closely, the data shows a significant rating drop on your last contest, whereas real CF data says your last contest went great. The most likely explanation is that my program unfairly penalized you for an unrated contest. Do you remember if that was the case? If I could have the list of all rated events, the issue would be fixed.

Btw this algorithm also does a decent job of outlier reduction. For instance, Swistakk was understandably upset that he lost 140 points last round. My program gave him -57 instead. On the other hand, if you do very poorly (or very well) several times within a short span, the rating change accelerates as these data points cease to be treated as outliers.

I did the round 330 (which was unrated due to a fail in div1A) and yes, it went pretty bad for me. Seems like unrated rounds can't be neglected — but they can be added manually.

I removed round 330 and a few others, but I'll need help to get a complete list of unrated and team events. CFratings.txt now shows 3 alternative sets of title bounds; my preference is the middle one.

For some reason, my automatically mined list has almost 2000 more users than http://codeforces.com/ratings/all/true. If a user changes their handle, do old scoreboards continue to show the old handle?

I checked, apparently not.

In order to avoid uncertainty about colours, focus on ranks instead. (Colours should just be set so that at least a fixed number of people has at least a certain colour.)

For now the assumption is we keep the same mappings between colour and title. So the division boundary is 1750, and 2300+ (currently 150 users) are red. Although my system has less inflation, the number of GMs still more than doubled compared to CFratings2013.txt and will continue to increase as site activity grows.

Edit: oh I see what you mean. Yes my focus is on the rating algorithm; titles and colours just help to frame the picture.

Hm my top 10 list right now differs considerably from the official one...

Great job! I have several several users to compare and your numbers make more sense to me.

Can anyone tell what's wrong with this submission (problem 3 div2)

submission

It gives a wrong answer on pretest 2:

Input:2 01Output:4But on multiple local machines is outputs 2 (the correct answer).

I have a nice solution for C

lets define a block a maximal interval [L , R] such that for each L <= i < j <= R : a[i] = a[j]

for example 112 has 2 blocks .

now just print min(n , number of blocks + 2)

I don't understand how solution 14586181 of FreeMoneyCity can be solved and implemented in 3 minutes. It is very strange.

Yeah, that also amazed me :). However I wouldn't be dubious about that, for an experienced competitor problem is straightforward and all of those pows etc. were in his template. 3 mins is a really great time, however not an impossible one.

However, I looked at other his codes, and templates were different, even were solutions on different languages. It's like that this account is used by different people, or it's big trolling made by one man.

Maybe. but his solutions are really simple and elegant.

See this magic.

Have all mod operations in 1 snippet. Then type few key strokes and everything is there.