Hi all.

Today there is a school regional team competition in programming in Saratov. We've decided to make a round using tasks from this competition. The problems were prepared by Gerald (Gerald Agapov), Fefer_Ivan (Ivan Fefer), HolkinPV (Pavel Kholkin), Igor_Kudryashov (Igor Kudryashov), IlyaLos (Ilya Los) and Nerevar (Dmitry Matov). The problems' statements were translated into english by Mary Belova (Delinur).

The round starts today, on 15th of October, at 16:00 MSK. Parcipants from both divisions are welcome to take part in it.

The scoring is standard: 500-1000-1500-2000-2500.

Congratulations to the winners!

Division I:

Division II:

**UPD:** The tutorial is published.

today is "Eid al-Adha"

Happy feast to all muslims :D

Happy feast :) عيد سعيد عليك ان شاء الله :)

Хорошо-хорошо, только не взрывай.

A special day for a special round. Happy feast to you too :)

Kurban bayram mubarek olsun!

Happy "Eid Al- Adha" to you. :)

Happy Eid al-Adha!

Just want to remember that you CAN NOT fast in the next 3 days (4 if you count the Eid al-Adha), for you who fast routinely.

Happy feast to all of you :D

happy feast to you too :D

Really funny...

This is now 30 minutes after contest but still : "The scoring will be published later."...

4 hours for system testing...

30 second for ratings!!

thanks!

You should respect this rule:

You may edit your comment only for fixing grammar mistakes or small changes. Do not change the main idea of your comment.Sometimes you made a mistake and after making the mistake you understand it... What should you do that times?

Just curious, why the scoring is published just before starting?

maybe It is different to "Scoring will be dynamic. Problems are sorted by increasing order of difficulty."

4 mins to go, yet no scoring!

what means 'school regional team competition'?

ACM regional competition ???

In Russia, we have team programming contests for schoolchildren: one All-Russia contest and several regional contests. Our region includes southern part of Russia.

middle school student, or college student ?

I'm not sure what do you mean, but I would say middle school.

yalishanda, thanks.

O~ thank you

it's very early!!!

[user:wo...]is little bit mysterious, can anybody see his personal information?

this is the one of the earlist contests in CF(at 8:00pm in China) the timetable shows that students have to finish this contest at school, dont they i dont know about contests in Russia, perhaps it's an important one. do they feel excited? all in all, wish them good luck

If each round were arranged like the timetable of this round, it would be perfect for us Chinese participants.

you know it's an international website, so jet lag is a serious problem:) that's okey, for we can cherish each chance

How i can know the problems for the last school regional team competition ?

I think you can search for them in Timus :)

I hope everyone fails :D

That's very unkind of you!

I lost a bet and I had to post it :D

Finally, a contest that's not too late.

this round was previously arranged ahead of schedule maybe because of the TC.

" The scoring will be published later " . 4 minutes before the contest , yet not published . Well later does include after the contest :P

Score distribution is standard. The author of the post are involved into our Olympiad. So, he wasn't in time with announcing.

No hacks available?

The queue is really long!

I think some time should be added because of all this "In queue"..

And the site was down too for few minutes... :(

How solve problem D?

It's very very hard to understand today's problem description!!!

I guess, I spent almost one hour trying to understand problems, this it's my second contest where I could say it have very poor description.

yeah i agree with u....

My Decision on opening a new problem depends on current problem result i can't start in another problem until i know the result of current problem (pretests) and Queue is toooooooooo Long :( :( and take long time to know if it pass pretests or not

Definitely it effects on a coder's coding... He has to keep an eye on his recent submission to know if it is passed or not... :/

Forget about last round's C (div1), this round's C is much more deadly! Well, at least there are abundant hacks :D

A funny thing happened to me now: I sent a hack on a solution 1 minute before the end of the contest, and waited for the queue to settle (around 1-2 minutes after the end). But I found out it was ignored, because there was a successful hack around a minute before mine, but that hack was still in the queue when I sent mine :D

Well, C div1 is not very much hard , but you just need to be very careful to handle all cases

But being careful is hard! (for me, at least...)

That's exactly the point. With problems that rely on you finding a general algorithm, passing pretests usually equals passing the systemtest (as with Adiv1 this time). But it's easy to miss a special case (I hacked one guy on "5 1 1 1 1 1", for example).

So THAT was the case I missed! I was dying here trying to figure it out... :)

The scoring will be published later. later = never ever ? looooooooooooooooong Queue ! :|

today's div-2 contest was slightly harder than usual contests, but the problems were very interesting to solve! next time, try to increase the possibility of hacks! :)

I think the system testing can't be completed before TC start ...

Even before TC's end

That's why they began the contest so early.

dunno why, but i think this is the record for the slowest testing ever on Codeforces!

Hi I wanna ask about my A submission [LINK] Why my submission didn't passed time limit ? I saw that my idea is same with other submission that got accepted. Is that using (*it) many times make my submission slower or there's any other factor ? thanks

what is the purpose of the

`hold;`

statement at the end?It just same as getchar(); twice. I'm sure it's not the problem because I got TLE on preetest 11

Probably because of the

`lower_bound(s.begin(), s.end(), l)`

call. From the docs:On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

If you want log complexity, you have to call

`s.lower_bound(l)`

instead.I think that this line:

while ((*it) <= r)

should be

while (it!=s.end() && (*it) <= r)

I think it's because you are erasing while you increment the iterator. IMO you should erase the whole range after you assigned the winner.

ffao gave the correct answer.

I got TLE for using

lower_bound(s.begin(),s.end(),l)later i replaced it withs.lower_bound(l), i got accepted! so its really something to keep in mind.25% system test = 30 min

100% system test = ???

Supposing linear behavior you can simply calculate it by a proportion xD

430 min?

50% system test = 115 minutes!

25% system test = 30 min 50% system test = 115 minutes what's about 100% system test ??? :P

400 mins

Whats that? quadratic interpolation?

I hope when I wake up tomorrow to find the system test has finished

LOL at least 140 testcases for div1 C well, at most 140 seconds (=more than 2min) are spent on each user.

Why today's judgement such slowly?

Because there are many test case to run (20-150 cases) for each submission, and each case is about 1-3s time limit.. and there are many submission too.

EDIT: here is a picture

is anybody else facing a problem opening the TopCoder arena? the SRM registration closes in 2 minutes, but i am unable to launch the arena! :(

Yes, me too

just when registration closed, the arena opened! how unlucky we are! :(

Did you update your Java version? I faced that problem some days ago.

i redownloaded the .jnlp file from the website just before trying to launch the arena, but still it wasn't opening!

I did the same but it was a problem with a jar file (logging.jar) So, I updated from Java 6 to Java 7 and it worked.

Same here.

always delete your cache by typing javaws -viewer in terminal and then restart the arena .. Even then if it doesn't work , restart your OS and then open the arena .. It has happened a lot of times with me .

Ahh... Why the system testing is so slow? I really don't like when I have to wait few minutes for my solution being checked on pretests, especially when I have a stupid bug and have to resubmit it many times. Today I got RE because I've written ios_base::sync_with_stdio(0); and later used scanf. I submitted it 6 times and had to wait few minutes for each of them. Is it really necessary to put so many big pretests?

And now 40 minutes already passed and system testing is in 20% of its progress...

Hi, i wanna ask about my submission 4791878 , why i got WA on pretest 1 ? Thank you very much

Your check function doesn't return true.

Thankkk youu !

May somebody explain C, D, E (div. 2), please? C requires a segment tree, yep?

There's no need to implement a segment tree for C in Div 2, a disjoint set or simply a linked list would suffice.

Or a regular STL set. 4789501

Oh God, really. Thanks. And may you give some little tips for D & E, please? Don't know how to solve them :\

D: let

gcd(length(x),length(y)) =d;i-th character inxwill be paired -times with every character in stringyon position . Count how many chars equal tocinxand inyare , and then the answer isN·length(x) minus the number of all pairs of chars equal tocat every remainder modulod(those are zeroes in the Hamming sum).E is ugly, I don't want to write anything about it...

There is non-ugly solution for d2 E — d1 C

Could you explain your Div1 C solution? I think it's better than handling different cases.

Basically there is not that many ways to ditribute that many people between n compatments of 4, 3 and 0 in each. For each such variant we can use simple greedy

For E(Cdiv1), let iterate number of final happy compartments from 1 to n and check if it's possible to be our answer (and how many swap). Final number of compartments

xis possible if and only ifx<= number of students <= 4*xx<= number of compartments that already has some student sit on it (imagine that answer has more number of happy compartments, this mean we do some waste)Now, we will find minimum number of swap if we want to got x happy compartments in totals, we do as follows

cnt[i] be number of compartments with i students on itSbe number of studentsCbe number of compartments with students on itfinal[i] be number of compartments with i students on it at the endfinal[4] =S- 3*xfinal[3] =x-final[4]ans= 0D=C-xbe number of compartments we want to get rid ofans+=max(0,cnt[4]-final[4])ans+=min(cnt[1],D)+ 2*min(0,D-cnt[1])our answer will be minimum

ansover all suitablexYou can look at my submission 4801911

Could you explain why final[4] = S-3*x for a valid x?

We have x compartments, in these x there are final[4] compartments with 4 students. 3*x + final[4] = S (total number of students should be same), so final[4] = S — 3*x.

For E, first you should combine 1s and 2s to 3s, then some 1s OR 2s left. If 1s left , brute force how many 1s will not move while other 1s must move. That's easy to think. If 2s left , just do the same thing as 1s.

Hope my code easy to read and understand.4801885

A nice intuition the STL set indeed. How can we deduce if the set is enough in this problem or even in general, what is the border between set or list being enough compared to segment tree. I know the question is not so specific but I think also some advises (not necessarily related to this specific problem) from more experienced coders will be well appreciated from biggest part of the audience.

Thank you. PS: Congratulations for becoming a red coder for first time! :)

It's hard to say when sets could be "enough", all these data structures have their own usage. STL sets can do element existance queries in time, and supports insertion and deletion with the same complexity, also it can find the element before or after another element. Linked lists can do insertion, deletion, and moving to next element in

O(1) time, but takesO(n) to find an element. And as for segment trees, it has a totally different usage. For more information maybe you can check out wikipedia.*Takes O(LogN) to find an element

... Sorry, my mistake

Does anybody have some idea of div1 B and C?

B (D in DIV II) , as far as I got it from others solutions, revolves around taking note of the fact that strings x and y are cycles — i.e. each letter in x or y spans a specific set of letters in the other string.

For example with A="abcd", and B="abcdef" (2 strings of sizes 4 and 6), A[0]='a' spans only the letters {a, c, e} in B even if the two strings are repeated infinitely (try it yourself). Simple observation shows that we could partition each string into n partitions = gcd of their sizes. In the previous A and B example, there exist gcd(6,4) = 2 partitions for each string; {a,c} and {b, d} in A, and {a, c, e} and {b, d, f} in B, and all elements in one partition in A are matched only with corresponding partition in B.

Hashing corresponding partitions in each string and comparing them against each other yields the result — check top submissions like this for code.

Slowest system testing I've ever seen.......

Most probably, fastest update of rating ... :D

what a system test!!! why Codeforces don't make system test faster permanently?

Eid mubarak to all muslims ..

system testing too slow !!!

I think system testing went to participate in TC srm and will come back.

Topcoder's contest and system testing will complete before CF's today :P

I think TC and this system testing finished together :D :D

tc finished and cf still running.

the TopCoder SRM

started at 2300 ISTand has finished system testing and rating updates, but the Codeforces round thatfinished at 2000 ISThas only finished 90% system testing, and has probably broken the record for slowest system testing ever! i know this doesn't always happen, but Codeforces should really improve the speed of judging on both pretests and system tests!lol nice pic

It would be so better if codeforces people could use extra servers for load distribution .. Cummon professionals , help mike with the funds .. after all we all benefit from the platform ..

TC srm finished and codeforces still has not finished system testing

I haven't seen system testing like that...! thanks!

First, happy feast to all muslims !

Second, I'd like all this problems. But can you tell me the reason why the result come late ??

Time limit exceeded on test 61 [final tests] → 4793492.

whats problem with BFS?

I have seen some other bfs solutions to be failed. I don't know the exact reason. My dfs solution passed but I have seen some other bfs solutions to be failed.The reason could be (not sure) same nodes are being queued multiple times.if a node is pushed into the que and marked as visited then it could be a little bit faster. You can try that.But TLE on CF server with bfs where other solution passes with dfs!!! well i am surprised ! Thank God I dont know bfs :p

It could be because you use memset everytime you expand a node.

I do no DFS/BFS .. Its AC ..

http://codeforces.com/contest/357/submission/4798719

I just leave it here : Yeputons comment about codeforces down

Actually, right now I don't know why judging is so slow. The possible reasons are:

Sorry for really slow testing.

Current submits are all 'in queue', any mistake?

seems it continues to work, ok

hey, if its not too much to ask, can u implement a way (if it doesn't already exist) by which we can sort the users in the standings by score in a particular problem, or by score on hacks? thanks in advance!

Happy feast! Could someone explain me solution of problem C in Div2 or A in Div1?

You can do operations using Map, Linked list, disjoint set or Segment tree .. All will suffice ..

Could you explain one of them?

At first put all knights to the TreeSet, then sequentially for each fight take corresponding subset (for TreeSet it takes R*logN, where R is number of items in subset) and remove all elements of subset except winner. The total complexity will be N*logN

I got it. Thanks.

See maintain a map/set of all those who aren't defeated .. initially it will consist of all the knights as none is killed . now as you get the queries .. find the lower bound for l and delete elements from map/set except the one index which won .. and go on updating the loose array for those who have lost .. searching requires logn for set/map since map/set are a balanced rb tree and you will go to n-1 elements exactly once .. hence your complexity O(nlogn)== 5*10^5 which is within limits for 1 sec .. Apart from that you could have used Disjoint set DS as it is also ammotized O(Nlogn) or in the same way a segment tree ..

System testing was too slow...but ratings has been updated very fast instead!

Wow ratings got updated so quickly.. great!!

Hi everyone. I don't understand why my code for Div2-C gets TLE. Here is my solution --> 4796407 I kept all the elements in a vector and when time came, erased it. I think it has complexity

`MlogN + M + N`

. Please tell me where am I going wrong so that I can be careful not to make such mistakes in the future.Erasing an element from a vector takes

O(vectorsize) time, imagine that it's because you need to re-number all elements after it. So you complexity isO(N^{2}).Hi! Your solution would have worked perfect with another container like set. Unfortunately the erase function from vector is ( almost ) linear in the size of the vector. So your complexity is not MlogN so that's why you are getting TLE. Try with set and you will get AC!

I don't usually use set. But I realize it's a pretty handy structure to use at times. I'll try what you said and get back to you. Thanks mate.

Yay! Coded with set and got AC. Runtime less than 1 sec. :)

Thanks a lot!

I have a confusion with you bsearch function. specially with this line hi = v.size()-1; Your M times bsearch will cost MlogN if and only if hi = v.size()-1 is an O(1) operation. But I am not sure that it is O(1). Also in the case of erasing vector elements. Erase operation is O(n) and M times O(n) is bad.

Thanks. I must have counted the complexity wrong. I'll try fixing the solution.

del

Nice joke.

I love this problemset, especially for problem 1D ;)

Could you explain how to solve D? Thanks

I got TLE #82, but assuming my solution was correct, the problem asks you to make a nesting with the given bags, such that the sum of the values of all top-level bags is s. The key observation is to note that any selection of top-level bags is actually possible, as long as the biggest bag is top-level. The trick is to nest each non-selected bag within the next-highest bag, which is always possible. In other words, you can reduce the problem to a subset sum problem.

Why "any selection of top-level bags is actually possible, as long as the biggest bag is top-level"? Under the condition that the total number of coins is fixed, I cannot understand this property. Could you elaborate on it? Thanks.

Let's sort the bags by decreasing

a_{i}. The necessary condition is: there's a setSof bags such that , and (1st bag is the largest one). We can construct the solution now. Let's just take the bags inSand puta_{i}coins into bag . Then, we have some bags left over, and we want to put those bags so that the constraints would be satisfied.Let's process the remaining bags by decreasing

a_{i}. When addingith bag into the configuration, we know that there's a bagjwhich containsa_{j}≥a_{i}coins and no bags (for the largest one of the remaining bags, it's the largest bag in total; for any later one, it's the bag that was added to the configuration just before it), so we removea_{i}coins from bagj, put them into bagiand put bagiinto bagj. Notice that this doesn't change the total number of coins, and that there were enough coins in bagjfor it to happen (there will bea_{j}-a_{i}left over directly injafter this). In this way, we can construct a solution.The condition is also necessary, because the largest bag (if there are more of them, choose an arbitrary one) can't be nested in any other, and the number of coins (directly or indirectly) in bags of

S(those that aren't nested in any other) must be equal tos.DP and use bit set to make it faster.

why my C problem is MLE in test 19 ?(div 2) can some one help me?

Probably, stack overflow because of the infinite recursion.

problem: Round #207 B. Flag Day

example : 7 3 1 2 3 4 5 6 5 2 7 Who can tell me the answer ? Why many people who is accepted can't pass it ?

This is an illegal case — in the third dance, you have two dancers who already participated in dances before; 5 and 7. Problem statement indicates that in each dance, at most one dancer who have already danced can participate. This makes the problem way easier actually!

Without this constraint it would be a 3-Colorability problem which in fact is NP-Complete :)

Thank you very much, I see.

pls explain the scoring system ,i solved a question(A) in prev round at the same time as this time(in this contest) but last time i had an increase of +28 points but received a -48 this time

In previous contest, you were 1284th from 2158 participants. This contest, you took the same place, but number of participants were less than previous, so you lost rating.

Thank u

Excuse me, may I ask when will the tutorial be published? Thanks

Found the tutorial was updated here http://codeforces.com/blog/entry/9210

Well, nice problem, especially C

I made WA on problem C, on the test 141...

I coded for(int i=0;i<num;i++) but I should code for(int i=0;i<=num;i++)...

I lost my rating by 67 points by the mistake and I failed to yellow. But for this mistake, I would be still red now and had gained rating...

All of us have made a silly mistake in some contest caused losing the ratings

Versatile problem set !! #loved it again <<>> #CF, the best.

0xCF round : ))