Hi all! :)

I'm glad to invite you to participate in Codeforces Round #148 today. I (Hamed Valizadeh) am the author of this round.

I'd like to thank Gerald (Gerald Agapov) MikeMirzayanov (Mike Mirzayanov) Delinur (Maria Belova) and Saeed_Reza (SaeedReza Seddighin) who helped me in preparing the round.

Score distribution will be the standard 500-1000-1500-2000-2500 in both divisions.

Hope you find the problems interesting to solve.

Good luck and have fun ;)

**Update.** Contest is over. Congratulations to the winners of both divisions! :)

**Div1:**

**Div2:**

And congrats to Endagorion who was the only one solving 238D - Tape Programming correctly during the contest.

BTW, I hope you didn't get sick of that *boring* problem! :-"

**Update 2.** The editorial is ready now, sorry for the delay. http://codeforces.com/blog/entry/5765

Two consecutive contests with Iranian authors, very good :-)

also problems with Iraninan characters and stories :)

questions are going to be VERY hard :|

Why do you think so ?

fahmidan sualasham sakhte che berese be hale suala

may be the only reason why he's taken this low rate is that he's written it in phinglish(in farsi means writing persian in english).it's the translatoin: even understanding the questions is hard so how U wanna solve it??!

Thankyou -- Good luck and have fun — -

Codeforces Round #148 will lucky for div 2, :)

148 div 2 =

74and you mean that will not lucky for div 1?

if this Round will be lucky for div 2 this is not mean that will not for div 1,

For div 1 also: 148 div 1=148

be Sure that Question will be So hard ! :) Do not Put your Rating in Danger !!! =))) GL everyone !

why are they going to be hard?

Because it has had a Three month Preparing Process and its Tasks Have been prepared in This Months :D and its Authors Are Havaliza + Saeed_reza

Please, do not scare me!!! I hope get DIV1 today :(

Good and Hards Tasks... Now I am DIV 1 contestant!!!

I think there's going to be a lot of math in this contest.

When the lags will be fixed?

When the first contestants will give up ;) (seriously, I hope that the lag will not alter too much the contest :/ )

Again it is — the crash!

This is not the first contest which gives me "**Bad gateway**" errors (502 — 504) instead of a contest start. I understand that is not supposed to be so, however, I would want to hear what exactly goes wrong with the server. Moreover, I believe there are plenty of nice guys over here who could probably be very experienced and helpful in configuring network/servers. Why don't we post some CodeForces issues as a public discussion? This kind of a solution would allow CF users to help the platform somehow.

Pressing the F5 Key all the time...

Hope this is getting fixed soon!

Maybe the servers work has worsened because of you and some other users pressing F5 all the time?)

Isn't it better to start on the 5 PM than 4.55 PM ?

It would be better if they would do it like that!!!

http://www.quickmeme.com/meme/3rmsct/

Will it start soon !?!

nooooooooooooooooooooooooooooooooooo

I think Codeforces should use safe mode during contest time as they did few times in past. Server down before contest is ok but this may happen in contest time too. Topcoder also closes practise rooms during contest.

Friends, nothing is perfect!!!!

nemishe hala ke khodet irani hasti ye noskhe farsi sualam bedi nashinim mani konim?

The server needs to be upgraded.

Div 2 — B is not well defined. When we erase a character at position n and cp points to the character at position n+1, does it still point to that character (now at n) or does it remain at n+1?

Why the negative votes and no replies? Is there any place where we can ask questions to the organizers?

Yes, we can ask questions about the problems during contest. There is a big button 'Ask a question' which can be found here: http://codeforces.com/contest/239

What does the number 239 in the link? 239 is cool number=)

Contest ID...

Very easy problems. Thx!

Easy for you?

I never felt as stupid as I did on this contest =D even in div2

Teach me, master, I want them to be easy for me too.

WTB editorial!

I think, you cannot make the conclusions becouse of first and second tasks.

Looks like its going to take a while to reach division one :s

Carry On~

In problem D, div 2: I think just care the case n==3, another case the anwser is "2 2 2 2 2 ...". Is it right?

no but there are only two options: two smallest in one subsequence or each in a different one. there is no way to decrease the maximum value of F so we have to increase the minimum of F.

No, the answer is without doubt "2 2 2 2 2 ..." only when n==2. In other cases we should check more conditions.

it looks problem E,DIV 2 was easier than D...:D

and it was the opposite in div 1 !!!!

I recall a similar problem, at least on the surface, which also asked the minimum number of edges which direction you had to change. Maybe some people solved that problem and chose this instead of D, since it looked very familiar.

You can't erase your comment, prepare to receive minus by the non-contestants who will not get it now that the system test phase is ended ;)

cool!!!

for E,DIV2 my submission passed in pretests but failed in system test 7...can anyone help here..

could have gained 200 more ratings(Expert!!) insted of gaining just 42, if final tests would have been passed for E!!!

Are the pretests of С (div1) strong enough? I wrote solution 5 minutes before the end and realized that sometimes it can't find solution. So I just put line: if (best == INF) cout << 2. And it passed pretests! I'm 99% sure my solution is wrong but maybe someone can prove it? :)

It depends on your algorithm ... Maybe you can always find a solution?

I think it doesn't work on bamboo graphs (e.g. O-O-O-O). Idea is the following: Choose one vertex i = 1..n and run DFS on tree to mark for every vertex: is the parent edge forward or backward. If this edge (to vertex j) is backward, we claim pair (i, j) to be good. If both pair (i, j) and pair (j, i) is good, we can relax answer with number of backward edges on the way from the root minus one.

P.S.: Ouch, looks like I deleted some lines and now it relaxes just if pair (i, j) is good :)

Aw .. I'm a little confused .. Hope you pass it!

I liked the contest. At the beginning problems confused me a lot, especially problem A. But when I thought a bit about them, they turned out to be solvable.

Unfortunately my Div 1 C failed...

I can't agree more ~ The problems are all interesting and skillful.

ahhh... at last system test started. hope it won't take long time to finish.

Judging in not working!

Edit: Now working

I missed a hack on problem B :( Someone in my room outputs "1 1" if n == 2...

Without 0 in first line?

Yes

I found same bug in first solution which I saw :P

i guess that's me what's the problem with that?

So am I :(((

B Div 2 много у кого упала ...

I did not spend much time on the problem E because of the following test:

7 8

1 2

2 4

1 3

3 4

2 5

5 7

3 6

6 7

3

1 4

2 7

3 7

The answer is 2 but if we consider only stops reachable in any case for each bus route we don't find a solution. I am wondering how many of those who submitted this problem know about this test?

Very nice problems...But I'm lack in experience and my solution of B got FST...TAT

I'm unluky :( ;(

Pleeeease, don't make us wait, update the rating.

Can smb explain to me how to solve problem C(Div2) or A(Div1)? Thanks in advance

hey, count how many number you can put in the place of a1, then how many number you can put in the place of a2 and so on .

2^m — 1 ways for the first number, 2^m — 2 for the second etc.

f(n) = f(n-1) * (2^m — (n-1) — 1), f(1)=2^m-1. Here 2^m — (n-1) -1 means you have this number of ways to append a number to the valid sequence with length n-1. "-1" since you cannot use 0.

I don't understand.

Why can you simply add unused numbers (apart 0) to a sequence of length n-1?

Look at this sequence (n=3,m=3): 5 (101), 2(010), 7(111)

All numbers are different, but 5^2^7 = 0.

So it is a wool sequence: l=1,r=3

Why am i wrong?

At begining you have only "0" as foribbden element.

After first addition, you have one more foribbden element (the added one).

After second addition, you have next foribbden element (first ^ second). And so on.

So, you must look at "accumulate xor" not (simply) values.

Thanks for your explanation.

I had misunderstood the meaning of "n-1".

And you can also be sure that all of the "n-1" accumulated XORed values will be different, so that there are exactly n-1 distinct numbers to be excluded:

Else, it implies the previous n-1 elements would be a wool sequence:

If XOR (1 -> x) = XOR (1 -> y), y>x would imply that XOR(x+1->y) = 0, implying it was a Wool sequence.

Impressive how some people solved it within minutes =|

I wish this contest were the Elimination Round for BAYAN ... Thank you for the good contest :)

I think so...:)

Finally "Expert"! :)

Multi account is bad. There is a lot of "Ashvili" account on Kutaisi, with one or two contests on the history, like if they create a new account when they are too low to gain a lot of rating. The codes present the same style (same freopen (why not, its common), but reduced indentation too), and you said "Finally Expert" like if it wasn't your first contest, but in your profile, you are a new contestant. Suspicion...

More: the header "cmath" is often more present than "math.h" for C++, but here, for all the bukhnikashvili, there is "math.h".

Psst: You should answer "But I have brothers/sisters who program too, and we share the same code style. And I have said Finally expert because I have trained a lot, and was waiting the first contest impatiently" ;)

There is a lot of "Bukhnikashvili" account on KutaisiI do not need lies,I had only one accaunt lasha-buxo(which password I forgot with noactivated mail) and there is no more "Bukhnikashvili",Do you have any problem?

Epic fail, didn't know that the suffix "ashvili" was so common for georgie, sorry ;)

Nothing,:) Good luck in the next rounds :)

Thanks, you too :)

All of these are your accounts:

[user:Lasha-buxo,2012-11-05] LashaBukhnikashvili damian create 123321 learn bisoli_karola CodeForces.com

How do you know?

I have seen "//lasha-buxo" on the submission of create, but for the others, don't know how do you deduce this.

No one can compete with Lasha-buxo in negative contribution (< -50) xD

http://codeforces.com/top-contributed/friends/false/page/15 :)

Anyway, he does not hide anything :D

@Lashabuxo I'm hope that you remain blue after a few contests :)

Haha. Better to sit quiet if you're cheating! :P

Nice Contest :D hope to see the Editorial soon..

Can someone explain why in the sample test for div2 b: 7 4 1>3>22< 1 3 4 7 7 7 1 7 the answer for call l = 1 and r = 7 is 2 3 2 1 0 0 0 0 0 0.

1>3>22<

last 6 numbers are ignored for convenience

1-> CP=1 DP=R MAP=0>3>22< X= 0 1 0 0

2-> CP=2 DP=R MAP=0>3>22< X= 0 1 0 0

2-> CP=3 DP=R MAP=0>2>22< X= 0 1 0 1

2-> CP=4 DP=R MAP=0>2>22< X= 0 1 0 1

2-> CP=5 DP=R MAP=0>2>12< X= 0 1 1 1

2-> CP=6 DP=R MAP=0>2>11< X= 0 1 2 1

2-> CP=7 DP=L MAP=0>2>11< X= 0 1 2 1

2-> CP=6 DP=L MAP=0>2>10< X= 0 2 2 1

2-> CP=5 DP=R MAP=0>2>00< X= 0 3 2 1

2-> CP=5 DP=R MAP=0>2>0< X= 1 3 2 1

2-> CP=5 DP=L MAP=0>2>< X= 2 3 2 1

2-> CP=4 DP=R MAP=0>2> X= 2 3 2 1

2-> CP=5 END

Thank you.

If i can solve 3 problems in div2 & 2 problems in div1...Whose 1 will be better???

It may vary between man to man. But according to my opinion, solving 3 in div II is only better confirming that any 2 of these 3 also appear on div I(Like 2 from (C-E))

plz someone tell the algorithm for solving Div 2 problem E ..........

I see some ppls failed Problem B (div1) on test 6, giving the same wrong answer 190 (P.S. correct answer would be 200).

Is that a coincidence?

Many people have the same, good, algorihtm. Similarly, many people have the same, but incorrect algorithm :P Just coincidence :)

;) But when you think carefully, there is no way you can come up with a combination which is even better than the best case, even with an "incorrect" algorithm.

What you can do with an "incorrect" algorithm, is to get a worse answer. Am I right?

Oh no I got WA on #6 and my answer was 190...However,I don't know why it's wrong = =

I would suggest that you might have calculated the minimum value of the maximum value and the maximum of the minimum value separately while they might not be achieved at the same time.

eh..no..I have thought about this — -...It's so kind of you to view my solution 2500928 (cause my poor english I cannot describe it TAT)

int min1=a[0].first+a[1].first+(i==1?h:0);

This give me accepted. thx

oh no I misunderstood the problem,I thought f(i,j)=Ai+Aj+h if at least one of i and j is in the first subsequence!!Ahhh terrible~~~~~

Where else can i find the current contest questions being discussed????????

wait for the editorial

Сложный раунд=(

if this was an answer to my question then sir plzzzzz give link coz i dont understand Russian............plzzzzzzz provide the link.......

You should use translator or simply skip comments in Russian ;)

He wrote something about 'complex round =('

And... here is right place to discuss this round's problems

maybe he meant "Hard round"

where can I find the solutions to the problems in contests?

Try to take a look at others' solutions but don't copy them.

Is there any editorials?

UPDOk it's published nowhey guys can anyone tell me how to solve Div 2 Problem C

try to make a new sequence of n numbers for each valid answer sequence that i'th element of new sequence would be equal to xor of first i elements of answer sequence . each element of new sequence will be different form others and it's between 1 and 2^m -1 ... so for every n and m number of answer sequences would be equal to this :

(2^m -1)*(2^m -2)*...*(2^m -n)

I hope this will help you :)

I can't get the first sentence at all...did you really mean the second word "sequence"? Each element of new sequence will be different from others? Are you sure? I thought (1,2,1,2) is valid since 1^2^1^2 == 0.

But the request is to count the sequences that are

NOTa wool sequence...So (1,2,1,2) is invalid..When the next contest start?