Hi, Codeforces Round #221 will take place on December 24th at 18:00 MSK for both divisions.

Problem setters are whd, oGhost and boleyn.su. This is our first Codeforces Round, and we hope it will be a good one.

We'd like to thank Gerald and alpc104 for helping us prepare this round, and MikeMirzayanov for bringing all of us a place to compete and communicate with others.

The score distribution will be announced before the contest starts.

**UPD1**: The score distribution is 500-1000-1500-2000-2500 for both divisions.

**UPD2**:

Congratulations to winnners and Merry Christmas to ones who celebrate it today!

Div 1:

2.al13n

3.rng_58

5.uwi

Div 2:

1.bohuss

2.Tyg3R

3.xhsong

4.adamant

5.Kira96

Good luck

And Merry Christmas (note the date)

Hope the contest won't be like the last contest( Hard && Unrated ). Good luck to eveyone!!!

Good luck ... :)

Maybe people can already assume that every round announcement has some kind of grateful acknowledge to MikeMirzayanov, since it's becoming a bit boring to read that part every single time.

then don't read that part! :D

+1!

It is more like fetishism. We really have to eradicate this practice.

UPD: no disrespect was meant to Mike at all.

If this is the last round this year...

HAPPY NEW YEAR TO ALL :D

The last round 's Good Bye 2013. It will take place on the last day of this year :-)

Why this blog isn't on the home page !?

Contest in Christmas Eve? And on top of that — at 18:00? Weird idea. I'm not familiar with Russian traditions, but in Poland at that time we usually gather with family around table and celebrate Christmas Eve :P. Other days will be better or at least earlier hours. Even though I will try to compete :P. In Poland it's not that bad hour, because it will be 15 :P.

Pay attention to where the three round makers come from.

They come from Renmin University of China

The round will take place at 18:00 MSK means 22:00 CST.

BTW, as a freshman,it's always hard for me to make a decision whether I should take part in a round start at 19:30 MSK or not , because if I do, I have to coding from 23:30 CST to 01:30 CST while my roommates are sleeping, which may bothers them.(In my school, a student should never stay outside domitory after 23:00)

Wouldn't the round writers have it better if the round was earlier?

Are you sure that your roomates are sleeping at 23:30 CST? hehe

Christmas is not celebrated on 25th of December in Russia, see this wikipedia link. And even on 7th of January Christmas is not celebrated that widely comparing to how they celebrate it in Europe for example. In Russia people mostly celebrate New Year.

Your snow bear looks so cute! cute cute cute!!!

The Orthodox calendar isn't affected by the Gregorian correction (not everywhere, though), so Christmas in Russia should be shifted to 13 days later. Still, 24th this late is not the best choice.

You really are in no position to comment about "no-lifes" on my youtube videos if you plan on participating in a contest on 3pm-5pm Christmas Eve. ;)

OK, you convinced me. Tomorrow at 3pm I'm going to watch your whole screencast :P.

Yay, I participated and took in my opinion really good place — 38th :D!

Wow, three problem setters Chinese from RU! Look forward to it!

In fact, RUC is short for Renmin University of China, while RU is not.

By the way, I was born in Chongqing. It is good to see students from my hometown attending our contest. Good luck and have fun!

That's so sweet. Thanks!

king base!time is good for chinese,thx for setter

Good time for chinese..

Люблю задачи от новых авторов)

Но решать их ты, видимо, не любишь.

:)

Looking forward to it ! When the contest ends, it will be Christmas in China and we will have to go to school as usual ...

I love this contest!

Hope a better Contest than the previous one... That was not a Contest...

hope every contestant can have fun with the problem set :D

Have you changed the contest time or i need some sleep :) ?

Up-vote this comment if you can :P

It is very hard. We can't. Sorry.

Let me guess. After seeing some people in the last two contests, asking for downvote and getting them, you thought this would work!? If only it was that easy :p

I did this only for other guys like you to get up-voteed.

Good time for Chinese contestant! Thanks!

pingshi maozi tai qifu ren le, banyesangengde naozi dou bu zhuan le.

I hope this contest be creative.

Good Rate on Codeforces and Happy New Year))))

10 minutes before the contest and no score distribution published!

Surely we should unregister and not participate in the contest if we don't know the score distribution.

just solve problems and have fun :)

Just for Remember you said

The score distribution will be announced before the contest starts.

Chill. 2 more minutes left. That's like 120 seconds. Plenty of time to update the score distribution.

Now it's 30 second only do you still think that ?

I posted it 16sec before contest started.

Power belt, I have late for contest and registration. WHY registration starts at late evening? Should it be possible to open registration 1,5 day before contest?

Merry Christmas and Happy Halloween (Note : OCT 31 = DEC 25 :D )

Maybe I have a chance to go to div1...thx...

nice contest!,but what is the algorithm to solve problem C DIV 2 or problem A DIV 1?

C is pretty simple actually if you think of the reason why the setter used the digits 1,6,8,9. You can get all remainders when divided by 7 for some permutation of the digits 1,6,8,9. That is for every number x in {0,1,..6}, there exist a permutation of 1,6,8,9 such that when that permutation is divided by 7, it leaves a remainder of x. I think with this hint you might be able to complete the solution.

Will there be a tutorial published?

Yeah.. Div1 is too hard to me.. I'd better back to div2...

Saw few people use sort in problem B div 1. O(n*nlogn) should get TLE right? I went out of my way to use bucket sort to keep it O(n^2).

Sorting? I'm kinda scared now. I didn't use sorting. At all.

I didn't use sorting too, I think n^2*logn should TLE.

5506448

Sorting, no TLE =)

Okay this is weird. I generally assume, 10^8 calculations take 1 second. So O(n*nlogn) is (5000*5000*12)/10^8 = 3 seconds. Time limit is 2 seconds. Since it didnt get TLE, I guess CF is a lot faster than I assumed. So how fast is it? I did the bucket sort for nothing :(

It seems like the compile-time optimizations by GNU C++ are able to make up for it somehow.. Even though that some solutions that used sorting were either hacked or didn't pass the systest, so it's kind of tricky to guess whether a solution will pass or not just by looking at the source code.

mine was O(n*nlogn) and it passed... :)

Is cin very fast on codeforces? I was surprised that cin solutions worked in B.

At least it is fast enough with this:

`ios :: sync_with_stdio(false);`

I always use cin in CF and until now I haven't get a TLE by it.

according to my testing, on GNU c++ 4.4 and above cin/cout work very fast and compareable to scanf/printf :p

I think the reason is codeforces judges is really fast.

At beginning, we do not want n^2logn solution pass, but failed to generate a testcase. I am really surprised by the speed of judge computers.

my n*m got TLE.

My O(N.M.logN) get TLE ! be happy :)

Yes, I saw a solution that uses cin without sync_with_stdio, sortings of

nelementsntimes, and push_backsn^{2}times — still worked under 2s :)My solution with cin get TLE. 5505467

It seems it was quite close to the boundary.

my solution 5506320 O(N^2) using

`scanf("%c",&x);`

got TLE, change it to`x = getchar()`

got AC 5511177 under 0.5 s, i wonder why is`scanf("%c")`

so slow ?Cause it parses format string "%c" on each query, at least.

My

`O(n^2log(n))`

solution 5515627 and`O(n^2)`

solution 5515601 actually got the same running time. But during the contest I use`scanf("%1d", &a[i][j])`

to read the digit one by one, and it turns out the this is the bottleneck in my TLE code 5510016 ..how to solve problem c?

Problem Maximum Submatrix 2 is essentially

exactlythe same problem as http://www.ceoi2009.ro/tasks/logs.pdf :(And problem B in DIV 2 is almost the same as http://www.spoj.com/problems/ANARC08G/

Div1 A is almost the same as http://acm.timus.ru/problem.aspx?space=1&num=1095

We got the idea of this problem from one of our algorithm class homework.

Need hints for problems C div 2 :(

Need hints for problems C div 2 :( soon :D

That problem looks very artificial to me, these numbers must have some magic.

So I submit a crazy solution 5502926: until find a solution, do some random swaps, and if time out then output 0. And it passed system test.

Seems it can't be no solution, but I don't know why. :)

For every 0 ≤

r< 7 there is a permutation of {1,6,8,9} that (being read as a 4-digit number) yields remainderrwhen divided by 7. Choose the right one and append all the other digits to it.Even more than that, for every integer

`a`

, there exists a permutation of {1, 6, 8, 9} that is appended to`a`

and makes the result number divisible by 7. :)You can rearrange 1,6,8,9 to form all mods from 0 to 6 -- so just order the rest of the numbers in any order, then output the correct permutation: http://codeforces.com/contest/375/submission/5507138

For each 0<=r<7, there exists a permutation of {1,6,8,9} as (r*10 000 + permutation) % 7 = 0

So, you choose a random order for the initial number (just conserve one 1, one 6, one 8, one 9 and count number of zeros), then you calculate the rest of this number, and you choose the valid permutation of {1,6,8,9}.

You can then add as many 0 as you want lastly.

sample: 123456789 -> (23457 * 10 000 + permutation) % 7 == 0 -> permutation = 1869

(and with zeros:) 1230000456789 -> (23457 * 10 000 + permutation) % 7 == 0 -> permutation = 1869 -> result = 2345718690000

Please explain why this approach can be true ? I don't understand :(

Very interesting problems, and no complex algorithm. LIKE it:) [Although i have solved a little tests] Hope u can papare more contests in the future!!

Need hints for problems C div 2 :( soon :D Sooooooooooooooon

Are u kidding? N log^2 N solutions in D that use dat slow c++ map pass with a great handicap. Well, maybe I'm unfair cause I spent alot of time doing N log N solution, but I bet on weak tests.

100000 * 18 * 18 < 100*10^6

That's too rude, u don't assume that map is a redblack tree and we keep pairs in it.

One of logs, which going from merge is very small. Also maps are not very big mostly. Probably this two compensate.

There are even O(n * sqrt n * lg n) AC solutions, I really believe that the nature of the queries, at most n different ranges, (without partial overlaps) really improves O(n sqrt n) bound.

I used a hash map (unordered_map) instead of a normal map, and the fenwick tree is tremendously fast, so the additional log n factor is quite reasonable, I was skeptic during the contest (and even tried to find an O(n lg n)), it also seems that Codeforces got some speedy machines.

I think you did something wrong, O(N log N) solution isn't very hard. See 5512577.

Well done, but that wasn't actually a topic of my message =)

Indeed, but it was tricky to realize that is actually O(n lg n) during the contest, those who saw that all the updates are O(n) amortized mostly implemented an O(n sqrt n), the rest just used a Fenwick tree. BTW it would be interesting to find the worst case input for the O(n sqrt n) approach, here the tree structure makes the query ranges quite singular (no partial overlapping), maybe in this case is even better, O(n lg n) or even O(n)?

And for second time in a row a purple coder takes down the

Div 1. Congratulations, Touma_Kazusa :).In fact, she is red for a very long time.

In fact, she is one of the top rated users.

Can you tell us who is that?

YuukaKazami

:(

Are you sure?

The rules: "Don't create more than one account, if you have forgotten the password, use the password reminding system."

Even if the rules should be applied more or less to everybody, I don't think it was an attempt to cheat, or because the password was forgotten, but an other reason (which one, I don't really know).

The only thing that seems unfair it's that will affect rating changes of all others contestants.

I mean, I suppose that being beaten by a purple when you are red/orange make your final rating lower than if you're beaten by a top 10 user...

in problem D,why my O(n*m) solution get tle? 5509804

Try to use getch() or smth other, not cin.

Getch()? Pff.

`ios::sync_with_stdio(0);`

is enough to use cin and get AC =)5511181

Just as I said.

can you explain me why it is so improtant? and what this doing?ios::sync_with_stdio(0);

It is turns off synchronization with stdio (scanf/printf), so cin/cout can work faster. More information here.

Well, I guess because of this line

ans=max(ans,(j-i+1)*num[j][i]);

This line causes many memory hits, you need to access the array in row major order

swap j, i in the loops or in the array dimensions (make it num[i][j])

i think problem is with your input.

Try this.

'getch' was not declared in this scope,what can i do?

"#include <conio.h>"

thanks pretest #11, for problem A (div-2).

Could someone explain the solution of Problem D? Thanks in advance

you mean in Div2?

Yes

How to solve E div 2 / C div 1?

The "Custom test" feature here limits testcase input to 256KB, but the maximal testcase for "Maximum Submatrix 2" (Div 1 B, Div 2 D) has a 5000x5000 matrix (25M elements), so it seems impossible to properly test the maximal case for TLE against Codeforces servers (even if you hardcode the testcase in the source, you're circumventing the time taken reading input). Is there any good strategy for handling this, or any way around this restriction?

Use a genarator code.

That works for hacking, but not for testing your own solution in

custom test.Oh yeah. My bad. I misread. Maybe the custom Test is not meant for stress testing.

F@uk...Pro D,,my time is n*m*logn.....TLE.= =

What does I.O.U (name of problem B of Div 2) stands for?

I owe you

I don't understand why in B/D n<=5000. Many people submitted correct solution, but because of using (in my case cin) got TLE. I think n<=1000 would be enough for solutions with bad asymptotics to not pass.

I got n*m solution but because using "cin" got TLE.if n <=1000 than it can be solved also n*m log m and it did not want to author,I think author is strict in this issue.

Am I missing an easy solution to Div1 D or so many people have managed to code solution that resembles mine? I've done it by an algorithm which resembles heavy-light decomposition. I've done DFS, computed some data for every subtree and in one vertex I copied the data from smaller subtrees to the biggest one, which results in O(n log n) solution. I was really satisfied to get this problem accepted :).

Can you explain more detailed your solution? In Russian comments here we discussed accepted solutions in

O(Nlog^{2}N) with the same "copy data from smaller subtree to the greater one" idea, but the data was stored in log-time containers, such as Cartesian trees and Fenwick trees, so asymptotic wasO(NlogN·logN) =O(Nlog^{2}N).There is also a solution with complexity O(N * log^2(N) + (Q + N) * sqrt(N)) without advanced data structures, by splitting the set of colors into heavy and light sets such that light set contains colors that have < sqrt(N) elements and heavy set contains colors that have >= sqrt(N), then the light sets could be processed with simple dp on tree, and heavy sets could be computed using the "copy data from smaller subtree to the greater one" idea because there is at most sqrt(N) heavy colors.

Here is my code that got accepted: http://codeforces.com/contest/375/submission/5508056

For every vertex v I call DFS(v, log) where log is some number between 1 and log n. If vertex v has children v1, ..., vk and vertex v1 has the biggest subtree, I call DFS(v1, log) and DFS(v2, log + 1), ..., DFS(vk, log + 1). If I call DFS for vertex v with corresponding argument log, after calling DFSes for its children I want to have some data in col_num[log], at_least[log] and ver[log]. For fixed color c, col_num[log][c] means how many there are vertices in this subtree with color c, for a number k, col_num[log][k] means how many there are colors c such that col_num[log][c]>=k and ver[log] is simpy vector of all colors of vertices in this subtree. Those data allow us to simply answer all queries in each vertex and update corresponding data in our parent in time O(size of our subtree) (if we aren't the biggest subtree's of our parent's children's subtrees) which results in O(n log n) complexity of whole algorithm. If our subtree is the biggest subtree of our parent's children's subtrees, our parent just treats our complete data like its initial data and update it by other children subtrees.

Power of

MS C++!!! I think if lots of TLE codes submit their codes with MS C++ compiler,they will get accepted!

Accepted Solution: 5511246 and 5511362 and 5511553

TLE Solution : 5511075 and 5507435 and 5505552

I submitted these TLE solutions with compiler MS C++ and got AC!

What is the real reason?

problem B sux

you can't strongly say that

MS C++is better thanGNU C++. The difference is that cin and cout have been defined differently in these two compilers. The time of cin in MS without ios_base::sync_with_stdio(false) and with it is really close, however there is a massive difference in GNU with ios_base::sync_with_stdio(false) and without it. But GNU is faster with syncing than MS with it. I can show u a lot of codes which got acceptance with GNU with syncing that same code in MS didn't.Div.2 Problem D I add

`ios::sync_with_stdio(false);`

and pass.........Can anyone help to explain?!

What a pity...

cin works faster with

`ios::sync_with_stdio(false);`

Explanation here.

Also some statistics here.

I think it is almost always better to use scanf instead of cin.

You're wrong. If you use cin with

`ios::sync_with_stdio(0);`

on GNU-C++ your solution may be even faster than with scanf as you can see here.Feel quite disappointed about the problems setter (or the translator) of problem D div 2. You can rearrange the row but each col MUST BE ORIGINAL

I am sorry for that.

Div.2 Problem D: priority_queue got TLE (AC in MS C++), push in vector and sort got AC :(

I guess that why we usually prefer quicksort to heapsort :)

I don't know about you guys but I used a physics formula for Div 2 A. Is there any other solution?

Thanks for nice contest! It requires an ability to write fast without bugs not-completely-simple code in each task.

Can someone please tell me where my solution for div2-C is failing? I made use of the mathematical trick of finding %7 for large numbers.

http://codeforces.com/contest/376/submission/5506741

UPD: Found my mistake. Thanks to Zlobober ! :)

Your idea is quite right but you should add your

mp[remmod] to the end of the answer, because it will give the right remainder, but not 10^(len — 4) * right remainder.http://codeforces.com/contest/375/submission/5504410 -- my solution.

Adding mp[remmod] to the end is wrong because that can cause leading zeroes.

In any case, I found my mistake a while back and corrected it. :) Thanks!

Well, you can add all zeroes to the end, as in the author's solution.

Not quite. I'll give you an example.

No zeroes in this case, so according to you I should add mp[remmod] to the end. But it is wrong.

Test Case : 11689 Output : 18961 ( = 5 mod 7 )

It is realy unfair..... algorithm and and implement is correct only because of ios::sync_with_stdio(false); I get TLE....

You should try to study more about the ur programming language sometimes :)

It was really best Christmas present, thank you very much and see you in DIV 1 :)

Congratulations!!!

+100 :D

+174 ;)

-15 :P

It is recommended to test the maximal case locally.

I think that it takes less than two minutes to write a code to generate maximal case.

+198 :)

First of all, thank you for preparing the problems for us. It was a nice Christmas Eve.

However, I would like to point out the problems is not very good (at least for me).

For Problem B, it is

EXACTLY THE SAMEwith CEOI 2010 Day 2 Problem 1 Logs (the only difference may be the problem from CEOI asks rearranging the columns).And for problem C/D, I cannot recall clearly the source of these problems but I have solved tons of problems based on the old idea.

I hope that Codeforces can have more problems with new idea instead of the old one. New idea may be easy, simple, interesting, ... but it is good.

Anyway, problem A/E is really nice (maybe adapted from Chengdu Onsite 2013?). I don't come up the solutions till now.

Thank you again!

Well, if D has a nicer solution, than "move-info-from-smaller-subtree-to-larger" one with using some complicated data structures like maps, hashmaps, cartesian trees, fenwick trees etc (that are discussed above in Russian version of the site) then it would be great to know about them. Maybe when problemsetters publish editorial we will find more interesting solutions to it.

And C seems very nice and interesting for me. Can you give a sample of the problem with the same idea? Moreover, if authors didn't have to explain, what does "inside the closed curve" mean, it would have been really cool problem (but with such explanation in task the idea to store a mask of oddity for each object becomes much clearer and obvious).

The Grove -- USACO 2006 January Silver

As far as I knew, this may be the first time this idea appears. The problem can't become cooler by replacing the definition into something like "reach from the infinite point" since it must allow multiple pass of one cell. It is not that natural.

If someone has read this and not my explanation few posts above — yes, instead of maps, trees and other stuff, you can use arrays :D -> http://codeforces.com/blog/entry/10034#comment-155315

But one one drawback is that this results in also O(n log n) memory, there are other approaches with those more complicated structures which requires O(n) memory only. But if it fits into limits, there's nothing wrong with it :).

"if authors didn't have to explain, what does "inside the closed curve" mean, it would have been really cool problem" — imagine a closed curve with many selfintersections (those are allowed in this problem!). Could you clearly state what's its interior and what's its outerior? These 2 words are losing their meaning and the only thing that can tell them apart is this parity definition.

Yes, that's exactly what I meant by phrase "authors have to explain what does that mean".

MainDullMoeHand in his comment above showed much nicer task, that deals with that problem another way. For that task there is no need to define what interior exactly is, because it uses only the "walk around the connected figure" conception, which is much simpler to imagine and doesn't require additional clarifications.

Problem A is not new at all — see there http://acm.timus.ru/problem.aspx?space=1&num=1095 There's about 2000 sucessful submissions on it on the most famous Russian online judge.

I did not write this round well,but I liked problems very much,thanks authors for contest.

How did people use sorting to solve Div2 D / Div1 B? O.o

More info

Awesome work, like previous stats.

How do you make such requests on this website to get data? wget parser?

Thanks! :)

If I get your question right, requests are made using

`XMLHttpRequest`

from javascript. After the received html data is processed, graphs are built using Google Charts.Thanks for this fast answer!

Alternative problem for Div 1 A/ Div 2 C:

Is there a simple solution at this problem:

Find a permutation of a number n composed only by 1,6,8,9 digits (666,1689 etc...) divisible by 7

I tried to solve this problem during the thirty first minutes before finding my misunderstanding...

As long as there's at least one occurence of each of numbers 1,6,8,9 in that number, it's the same as Div1 A :D

For arbitrary numbers: if the input is small, you could do DP on (remainder,how many digits of each type you have left); if it's large, there are either few ways to solve it or a permutation should always exist, like numbers "16666666","61666666",...,"66666616" which give different remainders mod 7 — so it's enough to consider a random permutation of other numbers before it and choose the ending few digits that are good.

Ok, so for larges numbers, we can't have perfect polynomial solutions (I mean, without using random) ? Anyway, thanks for this answer.

I think we could get constant time solutions. Well, constant if we had just the occurences of 10 digits (if we don't limit ourselves to 4). Actually, digits with 7 possible remainders.

As long as the number is diverse enough, there should be a small subset of digits such that there's a permutation of them with remainder

xfor all 0 ≤x< 7; if there's such a subset, the length of the number is, in fact, irrelevant — no matter what permutation of the remaining digits we use at the start of the number, we can always pad it with the suitable permutation of our subset.The problem we got just specifies the subset for us: remainders "1,1,2,6". This is quite small, and I don't think any required subset (that doesn't contain any smaller required subset) will be much larger. Notice for example that the subset "many 6-s and 1" that I presented can be replaced by "many x-s and y", and it still holds for

x,ygiving different remainders mod 7 and even any prime modulus (not just 7) with 10 as the primitive root!That leaves us with the task of bruteforcing all suitable subsets, hardwiring them into the code and just choosing the right one for any number :D

Thanks, very nice idea :)

Thanks for the round! The problems were very clever, even though I didn't solve them during the contest!

Timus 1095 is exactly the same with today's A div 1. The only difference is digits used but I suppose that there're many different sets of 4 digits that work in this case — it doesn't mean though that problems will be different as well.

:(((

Anyone get TLE at DIV1-B, try scanf("%s") instead of cin. what a sad story, my O(N^2) solution with very small constant coefficient TLE.

I had the same issue. I think the time constraints for B are too harsh.

Never mind, just remember to use scanf in future. I have been away from ACM for a couple of years and forget this rule :(

I did scanf but I scan character by character.

NEVER use cin without invoking sync_with_stdio first.

Can anyone explain test 4 of Pro.B div 1 (or Pro.D div 2) for me ? In the first row we have 10 ones so we can put ones adjacent so that we have a rectangle with size 1 x 10, or I misunderstood the problem ?

http://codeforces.com/contest/375/submission/5515862

You can swap ROWS not COLUMNS :)

What is the official solution for DIV1-D? When I read other's AC codes, to my surprise the moving-interval solution could pass-_-!!

Its time is N\sqrt(N),so it can pass it.In CN, we call it 'MO DUI'

questions were interesting and little bit tricy...Hats off to problem setters!!!

thanks to authors for this round, problems were interesting,short and simple to understand — I like this round

Who can describe solution for 376C - Divisible by Seven, 376D - Maximum Submatrix 2, 376E - Circling Round Treasures?

Can you post the editorial please.

http://codeforces.com/blog/entry/10084

Thanks

why so many down vote. is it wrong to ask for a help?

Probably because the editorial was there on the "recent actions" list, and you didn't bother to check it before asking about it.