Tomorrow, in 4 and half hours before the end of the summer (check your zone), **Codeforces Round #136** will take place. I am the author of this round, it's my 6th contest on CF.

Gerlad Agapov (Gerald) is helping me in preparing the problems. Translations will be done by Maria Belova (Delinur). Thanks to them.

I hope you will like this round. **The points distribution will be standart.**

Thanks!

7 user in the first division solved all 5 problems, here they are:

Meanwhile, in second division, Top-4 looks like this:

You can find the editorial of the contest here.

And again your contest at the very end of august(round #84, 29 aug 2011).

47 to all.

what is 47?

Lucky number.

Most likely, you'll find this out during contest.

Will the problems be sorted by difficulty or not?

What a pity that I cannot attend this match because it is 1st,Sep in my timezone and I must back to school. But I wish everybody will enjoy this match and do your best!

We should back to school the day after tomorrow, so we can do.

I must back to school too.For I haven't finished my homework,I have to stay up to finish them.So I can sttend this match.How happy!

My teacher told me that we'll have an exam on 3rd and it realy shocked me...I wish my test scores will be as many as my rating on CF...700 is enough in fact...

Back to school on Saturday, poor you guy. Anyway, virtual participation is still available for you later :)

It's the last year for me in middle school,so no matter Monday or Saturday is busy for me...

Gui.....

I hope you won’t regret your decision to participate in ABBYY Cup :)

Wow! Mr. witua always your problemset is great! ;) Thanks for preparing another contest!

If it is not dynamic then it is classic, there are no so possibilities, are there ? :)

The cute faces are nice!

Let's hope for a * lucky * round to all :)

Unfortunately, it can't be lucky for all of us — someone has to be a looser..:)

It depends on what you expect for the match.

If I solve 3 or 4 problems, I learn something new (a good idea, algorithm, etc) from one of the problems I solve and I feel happy with my solutions, but many people are lucky so I lose rating, I consider myself lucky in the contest.

Besides rating is not everything, you can lose rating and then increase your rating in another match, but a good idea or solution that makes you learn something interesting, is never lost.

I was expecting it to be on the 29th. Was you

nth birthday too great to find a time for contest this year?Unfortunately, it was scheduled before I was setted as an author. Sorry for disappointing you.

I 've Been Missing Normal Score Distribution ! Thank You ! I Wish Luck for Everyone :)

Hope all the best from this contest!!!! ........Good luck and Have fun everyone ......:)

Can somebody explain the solution for Div2-D ? It drove me nuts.

I used sqrt — decomposition.

let's find all possible values of x for interval [1..n]. there will be no more than 2 * sqrt(n) such values. iterate over values of constructed set, and solve problem for all intervals. O((n + m) * sqrt(n))

I use segment tree :d

Me too, a offline 2d segment tree's painful code :-|

Actually he used 1d segment tree

can somebody tell me how to solve problem D in div 2?it drives me crazy...

In my opinion, Div2C is the easiest problem.

No. The easiest problem is A, of course :)

A is easy too :) but I had to implement 'f(x)' to solve it :D

Agree,but I made a little mistake and spent all time in it.

Lot of TLE's in div2 problem B :)

In div2_B I hacked 4 contestant with one test — max test.

I hacked 5 contestants with max test.

how i can hack solution?

First, you need to block your solution (you can do it on tab "Problems" by clicking on lock icon). Then you'll be able to view and hack solutions of blocked problem by double-clicking into cells in your room.

I failed DIV I — C 4 times. Two of them were because the examples were symetric so I misunderstood the way of rotating (I was shifting to the right instead of shifting to the left), and in all the submissions I failed pretest 5. I cannot find where to get the pretests, but it seems a lot of people failed that test case. Can anyone who failed that case, and then fixed it, tell me what was the mistake on your code? Does anyone know where can I find the test case?

Also for problem B the problem statement was wrong. Even if the examples clarified it, you can choose x = 0 and it also works (it doesn't say x > 0 or x is a positive integer, it just says "number x" and 0 is a number.

I misunderstood the way of rotating too!

Yes, that was a mistake causing WA on test 5.

I tried with both ways of rotating and still got WA.

I looked at the test case I failed and my bug was considering the permutations as cyclical. I can't believe I looked for the bug for almost an hour and couldn't find it!

Same with me. Fortunately, I decided to skip it after a bunch of submissions and had enough time to solve another problem.

So I WA for 6 times!

where can I find the test case?-> It looks like pretest #5 during the contest is called test #5 afterwards.Seems like there is a test case in problem A that is designed to stuck java's Arrays.sort

Java can't sort the array with 100 000 integers. How unfortunate.

That's why my solution failed. Is it the problem of java library or the server problem?

It's a problem of java library

This is not happened the first time here :(

Thats why I intentionally used merge sort and got passed :) Soln

winger's solution passed it with Arrays.sort — 1980 ms :|

http://codeforces.ru/contest/221/submission/2169999 1984 ms.

I think it's not much fair, is it?

Maybe, was it because he used PrintWriter instead of System.out directly?

my submission for Div2 — C got TL using Arrays.sort , Is Arrays.sort poorly implemented?

Remember , Arrays.sort in java is implemented using quick sort which has a worst case complexity of O(n^2) .Read this

So you can do

- shuffle the array randomly before using Arrays.sort()

- use mergesort, heap sort ;)

No, it's because someone is design the data intended to let java solution TLE

You got TL, because used scanner for reading.

I submitted the same solution in practice, in the contest it failed test case 80 with TLE, in practice it passed test case 80 in 90 ms. (it failed with TLE on test case 91 anyway) what's the reason behind this? thanks

System tests are still testing submissions for the first 10 minutes of contest (in DIV I) and it already tested 26% of the submissions. That means that the goal of this match was being very fast to solve problem A, that's not very nice. In my opinion the difference of dificulty between problems A and B was very big.

Am I the only one to have solved div2 A recursively as in the description? :D

Nope, I have seen another solves like yours in my room :)

:D

I didn't do well,but I still like this round very much.It is my first time to do Div1.Thank you!

Somebody used an anti-quicksort challenge again. So stupid of me!

This problemset is interesting~~ enjoy a lot... Although I have made a silly mistake in Problem B >_<. One of my friends' Java solution fail because of Arrays.sort's issue...Actually I don't think it is good to put such a case >_<...

lose one point in rating and drop to #7 T_T...... Sigh...It seems I'm always making silly mistakes>_<... How can I get rid of it ?

Problems with Arrays.sort and HashSet/HashMap were discussed a lot, but in Russian. These tests should be in system testset because they are used for hacks.

Ok,but I think it's unfair to those who are new to here. Why don't put it in FAQ?

Nobody reads FAQ ;)

which are the problems with HashSet/HashMap, where i can found info? thx

It's this.

It Was a Very Nice problemset and I myself really enjoyed it ! Thank You All for preparing contest (and ofcourse participating The Contest :) ) . But I had a Problem With Task E Div1 in Place where The problem Described the pair l,r many people didn't notice that its a1,,,,al,ar,....,an :D i had 4 WA because of it and Didn't manage to read the rest of the problems (after A I jumbed to E :D)

witua's rounds have always been good for me, and ratings is always increasing..

I'm 256. in final stadings. And I have 2560 points :D. Interesting numbers :)

I did a little mistake in problem C div 2. I counted the number of changes and then, I divided it by two. When I saw that 3 — 2 — 1 gave me only 1, it was late, I was blocked this solution. I got it, it not the same return (cant <= 2) that return (cant / 2 <= 1). Thanks for this great contest.

I was able to solve A-D correctly. After contest... :( But I enjoyed the problems, they are really interesting.

my code is giving correct output(=91) on test case 9 but here it is giving wrong answer on test case 9 2084000

i did submit your solution and it got AC. i just changed, the size of s1,s2,s3 and i submitted it with GNU C++ 4.6, instead of GNU C++0x .

sorry, i forgot the link

@fab But what can be the reason of increasing array size?? on my system it is giving correct answer for test case 9.(=91), for even an array of size 10??

i really don't know. it did give the right answer in my computer too, i just increased the array size to be sure ( it almost never hurts to let it have some air to breath ) i asked some of my friend, one of them, said, it might be the C++0x, and it still might not be completely perfect. but again, i don't know. sorry.

actually 10^9 is 10 digits, so your arrays are too small.

thanx actually i use bloodshed dev c++ compiler which gives correct output even when array size is exceeded by 1 or 2 i think.....

Stop using it, it is old and unmaintained. Try MinGW+Code::Blocks or MS VC++ Express.

Can someone please explain in detail how to solve problem D in Division II?

number x must appear more than x times,add them together,so the numbers that are useful are no more than sqrt(n).You can use the prefix sum and calc all the number'time by brute force.Notice the time limit is 4 seconds.(sorry,my English is poor.)

By the way,who is the person in your photo? It seems to come from Star Wars.

It is Luke Skywalker in his pilot costume. :)

I am a fan of Star Wars,so glad to see him here.:)

Failed test 94 on div 2 C... didn't figure out exactly the rule when i was in contest :(

thanks for preparing the contest and the problemset. i had a little problem with task C ( div.1 ) and i thought it might be someone elses' problem, too: i saw that a lot of people ( including myself ), got wrong answer on test 5 and i think, they made the same mistake that i did, and it could easily be prevented, just by making better thought, sample cases. the problem was that, i ( and i think some other contestants ) did make a little mistake in understanding how the shift works, so, the solution we outputed, was just bacwards. but if the test case 5 ( which is a reasonable case with n = 10 ) was a sample case, we could easily have realized this and get it right.

I WA on test5 too,and I realized the reason after my brute force program get Wa too.I think it is important to understand the problem more carefully.I just hope that we won't make the same mistake in the future contests;

i do think it's important to be careful and try not to make mistakes, like this. but it's not an implementation problem, and in this problems, finding the algorithm is the most important part, not little things like this. and second of all, i think the idea behind sample cases, is to prevent this kind of mistakes ( and/or for understanding the problem, better ) and it seems to be a common mistake, because at least more than half of the contestants ( the ones that i checked ) who got WA in this problem, did get WA at least once on 5. i don't think it's that important.

Maybe you are right.

It was my first CF round where I was to rank up, after 3 contests losing rating...

I found the problemset very interesting and I was able to get accepted for 2 problems, A and C!!!

I wish that we can have more rounds like this in a near future and wish good luck to everyone in the upcoming school year as well!!

Bruno

Hi,

Can anyone help me in knowing what can be done in https://codeforces.com/contest/220/submission/63940597 whose complexity is O(nlogn + m sqrt(n)logn) to get AC.

(Problem:https://codeforces.com/contest/220/problem/B)]

Thanks,