Hi everyone!

We invite you to participate in Codeforces Round #260(Div. 1 and Div. 2), wich will take place on August 8th, 19:30MSK.

The round was prepared by me, netman and Randrew. It's our first round and we hope that tasks will be intresting for you). Special thanks to Gerald, Cherrytree, vlad107 and dimad for helping to prepare the round. Also MikeMirzayanov for creating such a good platform.

Good luck everyone!

**UPD.** In Div. 2 and Div. 1, scores for each problem will be **500-1000-1500-2000-2500**.

**UPD.** We are sorry for the large queue in the end of round.

**UPD.** Congratulations to the winners.

Div. 1

Div. 2

It's good to see new problem setters coming up with DIV1 rounds at their first appearance :)

Thanks to fk2012,netman & Randrew. We expect more DIV1 rounds from you :) :)

The first time so early I am.

Hope Strong Pretests :D

Hope Strong Pretests :D

Hahaha so much hate for you

Why there is so difference two people with exactly same comments but one has 65 upvotes while other -16 downvotes !

Sorry for personal question, but I was always curious are you really Chinese girl or you're a boy who just puts girl face (as well as pictures from anime, cartoons, whatever) instead of their real profile picture? I think, that's pretty big disadvantage of English that you cannot understand the sex of the person when he tells something.

xiaodao is really a Chinese girl.

How do you know that? Are you real Juan Mata too?

I don't think so. He posted comments and participated Codeforces Rounds while FIFA World Cup 2014 was running.

no, i am

not.but how is that related to my earlier answer?

How you can claim that she's girl if you don't know him/her in person? I just proved that one cannot judge people by their nickname/profile picture because you neither Juan Mata nor Chelsea player (but you have Chelsea FC on your profile picture).

One does not simply ask gender on the Internet!

There is no need — see rule 16.

But they're trying to break it...

netman,(one of the authors of today's contest) you profile is very inspiring. starting from CF 105 div2, minimum rating 1105 at 143 div2 and then a story to tell everyone the secret of reaching 2192 at round 259 div1 ! its really amazing to see rising someone from the very beginning with his passion and practice that reminds me my lack of effort to attain that level. Wish you more and more success:)

he is just 8 rating away from becoming

Grandmaster. let's hope that he can achieve this in the next round. :)seriously, downvotes for wishing a participant good luck? seriously??!

Rating graph of Randrew is also inspiring... :)

minimum rating is

`1306`

and maximum is`1889`

... just 11 rating away from beingMaster...Welcome to Belarus & two years later you will be a

Grandmaster!or sometimes (like when you are tourist), just

eight monthslater! ;)Chinese Div1 rounds chain is finally broken :D

I hope that means we get a holiday from maths problems

Says the kingofnumbers? o.O

LOL, Numbers doesn't means maths , there's a lot of algorithmic and data structure problems which have numeric input :)

king means for everything involves number :P

Hope for math problems :)

i do too! [for geometry especially :D]

this is CF, not IMO

Codeforces Round #232 (Div. 1) was a terrible memory... All extreme math problem P This is not Mathforces :(

You don't do Codeforces Round #232 (Div. 1). Why "was a terrible memory" ?

Round 232 was one of the rounds lost in the 22-day Codeforces blackout so if you look at standings no one is there. He may well have participated.

.

What did you say?

Thanks for taking the time to prepare the problems. Feeling excited! Good luck contestants. (◕ܫ◕)

My first time in a Div 1 round, I hope I can make a submission.

Good luck! :))

Weak pretests please ;D

The first ever

non-Chinese Div.1 roundin40+days(excluding tournaments)!!!Hoping to get back to yellow :D

Wish you good luck :D I'm just hoping to get a positive rating this round.

Well I don't hope I can get back to yellow only by one contest, I mean, there are more chance of positive rating change in non-chinese rounds

UPDWow. I become master again. And you too XDWOW! That's wicked! I've never thought of being yellow in one regular round. Congratulations to you too!

Hope for good problem. Hope for more hack.hf & gl

the shortest contest post ever

Hope short problem statements too.

and short solution too !

But not short editorial :P

Still no editorial post... bad :(

maybe because nobody wished for "short time taken to publish editorial" ;)

actually there's a shorter announcement here it was only first 4 lines when the author first posted it.

Seems that the post you talked about is the only contest forecast post that doesn't mention MikeMirzayanov :p

Жалко, что без пони, но зато и без спойлеров.

Special translation for xiaodao: It's pity without pony. But it's good there are no spoilers this time.

Big thanks to vas.and.tor for help with the special translation for xiaodao.

Thank to Google (not a user Codeforces (and it is not a user)) for help with translation helpful to vas.and.tor.

I start now FOR first time .

Welcome

Good luck & it's my first time to be purple to take part in Div 1 !

a good news for me, a Chinese coder who don' t do well in math... most of last Chinese Rounds are also nightmares for me :p(anyway, learning is always a goos idea, through perhaps you can' t adapt it well

Is it the first Belarusian round or any other Belarusian rounds that have happened before ?

No. For example, aropan was the author of Codeforces Beta Round #92 (Div. 1 Only) and Codeforces Beta Round #92 (Div. 2 Only) before, and tourist was one of the authors of Codeforces Round #127 (Div. 1) and Codeforces Round #127 (Div. 2). So it's at least the third Belarusian contest :)

So a Belarusian contest is happening after a long time Thanks for the info greencis.

Coders like netman inspire us a lot for continuous practise.

The start time is confusing.

mine is correct. F5?

I think the registrations close 5 minutes before contest :)

I got it.

It's simple: the time shown corresponds to what's written above it. If it's "Registration's running", then the time shown is how long the registration will be running. If it's "Before start", then the time shown is how long until the contest starts.

Thank you for the clear explanation.

Look carefully! Bottom right one says

`Registration is running`

Good luck :)

In queue

Such CE, Much slow!!!

Haha :)

What a pity , I submitted a code in last 5 seconds and I got " Codeforces is temporary unavailable "

Problem C reminds me of the first day of IOI 2013, doesn't it? It is also clear now why you didn't thank Delinur for translations.

I like problem D a lot. Seems to be a good example, where rope sucks and sqrt-heuristics rule :) I didn't solve it during the contest, so I may be completely wrong.

Thanks for the contest, I've enjoyed it!

Good problems, but contest was ruined by slow testing.

I saw 20 pretests in some problems. Which means no hacks and maybe 500 tests in final tests. This could take some time to finish.

I am not sure that pretests for A are really strong. I hacked a guy with overflow and using

Ninstead ofMAX_{VALUE}.Fun fact: you can check if there are at least

xpretests in the Status tab with settings "any verdict" and "tests =x" — based on AC solutions shown.This way, we get: 12 for A, 10 for B, 15 for C, 9 for D, 21 for E.

At least A-C have nice time limits and D,E didn't have too many attempts.

My solution for C has a terrible misprint, but it gets AC on the pretests. It makes me think, that they are not so strong.

Thanks. We don't thank Delinur because when I write the announce we didn't know who was the translator.

Seems rope doesn't suck 7400437, but how does it work?

How to solve Div2 Prob C? I summed effective values obtained by all odd entries first and then checked even entries that outweighed the neighbouring odd entries, and then vice-versa. WA on pretest 11.

I guess it was linear DP. dp[i] = max(dp[i-2]+(freq[i]*i),dp[i-1])

My solution:

I used this dp after 4 WA. I hope it could be the correct answer.

dp[i] = max(dp[i-2] + m[i] * i, dp[i-1])

How did you come up with this recurrence? Can you explain it please. Thanks in advance.

dp[i] = the maximum score you can get using numbers with values 1~i. It is obvious that if you take one number i, then it is optimal to take all numbers i. Therefore we have two choices — take all numbers i or take none. If we take all we have dp[i-2]+freq[i]*i, we use dp[i-2] since we can't use values i-1 and we get score freq[i]*i from taking all numbers i. If we don't take i then the answer is the same as dp[i-1]. So we get the formula dp[i]=max(dp[i-2]+freq[i]*i,dp[i-1])

Hope I helped! :)

lets say you have stored number of frequency in array f. (Note ai<=100000). Now for each of the number i, if you take i you can't take the next number i+1.so you have to recurse over the next's next number i+2. and if you don't take it , you can take the next number. And see if you don't take the number i , you have two possibility , either you took i-1 , or you will take i+1 , both case is considered in the previous steps. and if you take(which you only can if you didn't take i-1) you can't take i+1.

I too faced the same problem. :(

It should be dynamic programming, you should consider two circumstances of the number. Reserve it or throw it away. Suppose that c is the count of a precise number, we have:

f_{i, 0}=f_{i - 1, 1}+c[i] *i,f_{i, 1}=max(f_{i, 0},f_{i, 1}). Note that you should use long long in c++ or int64 in pascal.Ok, but what is the mistake with my approach? http://ideone.com/MVT6SI

`1 2 2 3 4 4 5 6 7 7 8 9 9 10`

. Best answer is taking all the doubled numbers; your approach, starting with taking the odd numbers, will not replace`1 3 5`

with`2 2 4 4`

because`2 2`

is not strictly better than`1 3`

and`4 4`

is not strictly better than`3 5`

, but combined`2 2 4 4`

is better than`1 3 5`

(because`3`

only appears once).Thanks a lot!!

now not

invalid input after 10 minutes :(

Problems are all interesting! Thanks! What a pity that can' t correct my buggy codes at last:(

It is unbelievable that there are many people still use long long in Div2/B although the N is 10^(10^5)..

Who ?

7381800 7387856

(many people >= 2). It is true !

What? And IT passed pretests??? 0_0

If you take a look at code of participants, you will probably be surprised how many people somehow have used overflow of "long long int" or even "int" in their submissions

__233333333

Nice round. A and B were the way div2 first 2 problems should be. C was a little nice DP. D was a real show-off of Trie + 2 x DP + Game Theory. Also heared that E was pretty hard for Div (1+2), because Div1 coders should implement C and also meybe D or E.

The chain in the problem C could be maintained just by using a set. After merging two vertexes (

a,b), the answer will be .Only note each "division by 2" should be rounded up.

But firstly you have two compute the largest path for if each set representative right? DFS from any vertex then find the most deep vertex. Then dfs from that vertex. Isn't it the approach for finding longest path?

Yes, we should firstly initialize this, just simply DFS and merged them up in the set.

For the ones who have studied problem 1A — Dreaming in IOI 2013 the solution will be quite clear. Fortunately I have read that problem and solved it before :D

How to solve problem D? Maybe I'm stupid, but I tried to solve it for quite a while, and the only solution I came up with is the straight-forward square-root optimization (store one single Treap for permutation + individual Treaps for all numbers which occur often enough). This takes per query and works literally forever (30 seconds on my machine for the worst case). But looking at the amount of people who solved it, probably there is a much simpler and much faster solution. I wonder what is it?..

We have solution and it's much easier then yours.

One can divide an array into sqrt(n) blocks and maintain a deque for each block. Shift operation is rather simple: for fully covered blocks, it is just one push_front and one pop_back. Partially covered blocks can be handled naively.

To answer the second type of queries, one can maintain a count array for each block(count[i] — the number of occurrences of i within a block). For fully covered blocks the answer is just count[x]. Partially covered blocks can be handled naively again. Shift operation changes the count array in at most 2 positions per block, so it is possible to update it quickly.

The complexity is O((m + n) * sqrt(n)).

Beautiful, thanks for the explanation!

From what I could read in kutengine's solution: keep linked lists containing elements each, and remember the count of each integer for each list. Then you can do the rotating query by removing from the end of one list and prepending to the start of the next.

That's quite beautiful, actually. I'm always surprised by sqrt-decomposition brilliance :P

Can someone explain this compilation error to me?

7393631

it worked after I've resubmited it (no changes were made)

You try not use

#include <bits/stdc++.h>Any particular reason for it?

1 — "it makes the code completely non-portable across compilers, and as I doubt the header is documented, being in the bits folder, the behaviour of the header is probably free to change in any future update." chris

ref: http://stackoverflow.com/questions/23644633/cannot-read-bitmapfileheader-of-a-bitmap-file-using-c

2 — "You should never be including this.

`#include<bits/stdc++.h>`

Its an implementation file. Stick to the header files defined by the standard (they don't have .h on the end)." Loki Astari

ref: http://codereview.stackexchange.com/a/48813

It is obvious that this will only work on GCC. But if you only use GCC, then you are free to use any of its features.

Also this file

isdocumented, and will not change without notice: https://gcc.gnu.org/onlinedocs/libstdc++/manual/using_headers.html#manual.intro.using.headers.preTry a different compiler (e.g. C++0x) -- it works fine on my computer.

the problem is that the compilation error that was issued was this one:

Can't compile file: collect2.exe: fatal error: CreateProcess: No such file or directory

compilation terminated.

thats very weird...

PS: it works fine on my computer as well, it's codeforce's judge that's issuing this error ):

How to solve div2-D ? I tried to use suffix automaton but couldn't get an idea. Hope a nice tutorial for this problem.

I guess, D is based on game theory..

waiting for the editorial :)

I think we can use bor and then for each vertex set: 1) can we Win from this position 2) can we loose from this position After it see on root vertex and print answer. http://codeforces.com/contest/455/submission/7387998

It's trie, not bor :)

trie + 2 tree traversals to check if it's always possible for first player to win and if it's always possible for first player to loose. then just check for each case:

first player can choose if he wins or looses a single game -> "First"

first player always wins a single game AND k%2 == 0 -> "Second"

first player always wins a single game AND k%2 == 1 -> "First"

first player always looses a single game-> "Second"

There's a case when first player can neither win nor lose for sure. Then second player wins and 71st testcase covers it.

I'll take a look, bit i think it's always possible to be sure (at least my code got AC)

There are 5 different cases(but we can reduce that to 3):

The first player can decide the result of the game. Then he will lose

n-1games and win the last one.The result is deterministic (first player always win or lose), in such case, if first player always wins, result depends on parity of

k; otherwise first player loses.The first player can ensure a lose but cannot win, then opponent force him always lose.

The first player can ensure a win but not a lose(this is more complicated and I took some time to evaluate that): assume

k=1, then first player choose to win; then assumek=2, we will see that the second player can let him win, and get a first play in next game and wins; evaluating similar cases askgrows we will see that first move will always win if optimally play. So the result depends on parity ofkagain.The opponent can decide the result. Obviously the first player loses.

And finally the conclusion is: If first to play can decide the result then first play wins; Then if first to play can only ensure a win, result depends on

k; Otherwise first player loses.After waiting for a long queue, my submission have failed on pretest after 15 minutes after the contest. I should have tested more with handwritten cases.

again power of

`#define int long long`

.....2 unsuccessful hacking attempts on my code because of this...:Pyes ,but one of them give me 100 pionts. others even passed,very angry...

How do you write int main?

GNU C++ still accepts "main()" which means "int main()" but with a warning.

Like this..7232343

signed main()

Nah, that's way too conspicuous ;)

You can write void main() in Visual Studio

But GCC gives

`compilation error`

if you write`void main()`

, and that's not supported in standard.Codeforces supports MS compiler

16. Solution code obfuscation and creation of obstacles to reading and understanding the solution is prohibited. It is forbidden to use any special techniques designed to complicate the reading of the code, to understand its workflow./blog/entry/456

Yes, but this is actually useful if you want to avoid overflow. It can lead to fails, but it does have use.

Oh ... take it easy man...! It's just a technique to avoid integer overflow and using

`int`

safely...it also has some good side effects!It stopped being "just a technique to avoid integer overflow" when you boasted how you tricked other people with it. I agree with dalex, it is a poor practice.

Yes, I guess it's time to enforce the rule. I've seen countless solutions with super-obfuscated code, "#define int long long" is one of the most innocent tricks. E.g., once I've got unsuccessful challenge attempt because someone submitted file with 2 solutions — correct one was at the top, and then incorrect one (with bug) was at the bottom, protected from compiling by some hacks (but not commented out — it would be too obvious).

Introducing unused code rule (similar to topcoder) would also be nice. Yes it slows some people down if they have to clean up their horrible mess before submitting, but making other people read this mess is much more cruel.

Which solution? Unlike TC, at CF contestants can gain from making solutions readable -- because it's possible to resubmit solution if it haven't been locked.

They benefit only from a certain kind of readability; there is no reason to fix hacks like "#define int long long" (and more tricky obfuscations).

Regarding to your first question — I'm not sure I understand, what are you referring to?

so using "small L" should be prohibited because it's exactly the same as "one" in codes! I lost an attempt to learn it ...

LOL, i tried to hack you once, and it returned unsuccessful for the same reason. luckily it was only a

testing round. :DPS: due to Black Day of

CF, this submission is no longer visible. :(so many people even use long long to cin>>n in DIV2 B. and a lots of them passed.... what could i say

Or they used int :) 7389513. And my attempt to hack was unsuccessfull.

I couldn't watch your hack attempt. What were you input?

string: "1" x 100000 + "\n"

In this case, maybe what he got is "1111111111".(The ouput as well as answer is 0) The better way to hack is input "1" x 999999 + "2". (The answer is 4 while the output is 0) :)

Your text to link here...

People used biginteger and modular exponentiation in div2bB!

Hacked a Java code but python code passed time limit! :(

See this code!

7383987

also see this 7378490 :P

I don't understand, How can they pass the time limit :o

Why not ? Modular exponentiation is O (log N). 7383699

In hacking box, font size is too small. When I was attempting to hack, I couldn't distinguish letter

`1`

from letter`l`

. So I sent an hacking request and got Unsuccessful. This will be better if font (in hacking box) is not Courier New or at least not too small like this.`1`

and`l`

almost look the same in hacking box, I agree. I've got same problem before.why system testing is not started yet ?

hope all accepted solutions!

slowest ever system test :(((

Because "Pretest testing" hadn't been done.

Oh la. What a large queue. :X

problem div1 A, at beginning I thought we remove all element equal to

A_{k + 1}notA_{k}+ 1 , who is the same?Although my eyes are not good but I am not as you !!!

Me too :/

@Nero

I have a question. How did this "7385674" solution passed the pretest..?? i tried to hack this with a large input. i thought it will fail to take the input. but it still passed.. and gave correct answer, how is it possible...???

Your test you hack ?

Because (x^4 — 1) % 5 == 0 (according to little Fermat theorem). So there are only 4 cases:

n == 0, n == 1,n==2,n==3 (mod 4). Easy to see, that if n==0 (mod 4) -> ans=4,else 0

sorry bother if i am not clear... the problem says the input can be very large... but the solver use long long.. I tried hacking with a input consist of almost 300 digit. how did it take the input a 300 digit long number in long long and still can calculate the correct answer...?????????

passed pretest but it will fail system test.

and your hack failed because when this code reads large number it will overflow so an overflowed variable will have random number so it will still enter either "if" or "else" and in your hack it entered by luck the same as the correct answer for your test so it gave correct answer.

Understood... thnx....

that's incorrect. there is another discussion: http://codeforces.com/blog/entry/13326

simply put: in codeforces, scanf takes overflowed inputs modulo 2^64 and, as 2^64 is divided by 4, it doesn't change the final result

5464456456456456456456465465456456456456456456456465

At my computer it gives wa

It looks like this solution relies on particular implementation of cin. Actually, what really matters is a residue modulo 4, so it's not so strange that solution works, because when overflow happens "divisibility by 4" is not changed.

counter example : 111111111111111111111111111111132.May be you didn't huck, because for your test answer is 0.

And some submissions have got accepted, even though there has been overflow

If somebody uses

cinfor taking input, and if your input is too large , it will take maximum value of that data type(I found when I did unsuccessful hacking). If you usescanf(), in case of long long it will just move between 2^-63 to 2^63 — 1(Data type range). In Java it will throw exception, I thought same in c++. His submission accepted because he used scanf.For Div2, problem c, I used the DP : dp[i] = max(freq[i]*i + dp[i-2], freq[i-1]*(i-1) + dp[i-3]), can someone please tell me why it is wrong and why dp[i] = max(freq[i]*i + dp[i-2], dp[i-1]) is correct?,

What are hackings on problem A div1? At first I think some people doesn't use

`long long`

but it seems that pretests include that case.Got successful hack on a guy that used int so I don't think pretests cover it.

Mine: image

And System testing starts finally

around 50 minuets after the contest.

Started finally! 45 mins later.

I remember I had even read the full editorial by this time in previous round.

... And system testing is completed!! nearly an hour only for systest!

Registered: 83 minute(s) agohaveContribution: +13!!!. LinkIt's frequent phenomenon happens in codeforces when someone wants to post a joke but he/she is afraid from negative votes so he/she makes a new account and post the joke with that account

You are right ! Maybe he is not excited about that

And when you see that the comment got lots of positive votes, you regret not using your real account

umm, u didn't even take part in the contest! o.O

7377218

This shouldn't have happened...

Could you please repair it ASAP? :P

OK, fixed. Thanks!

Many programs which already passed pretests get "Compilation Error", I think there must be some problems with the judge system.

Is there any problem in system tests? I submitted 2 codes for A, 1 for B and 1 for C. Instead of skipping my 1st A code, the submission page shows my B code as skipped.

Can anybody explain me this: 7377299 ?

UPD.This solution passed pretests; verdict became "Compilation Error" during the testing .After resubmission, it was "In queue" until the end of testing.

1H after coding phase and system test still not complete :(

codingphaseBad influence of topcoder(

Nope. When a Codeforces round ends a message box pops up and says "the coding phase of round xxx has ended"

nope. if i'm not mistaken, the box says

In Div2 "A" — I checked if numbers in each pair are equal...

7383032 Seriously -_-...? Why?? Because of what? Is O(n log n) too slow for 3e5 -_-?

7391661 Even worse :(

Uhm, by what magic doesn't it crash? Your function "Find()" doesn't return results for non-trivial cases...

LOL XD Good point :P

I guess that works because assingnment returns the assigned value (eg. a=b=7; assigns 7 to both a and b).

Anyway I commented the cerr and got AC xD 7396190

Yes, I did the same few minutes ago : /. I ignored it, because it outputs the same amount of text as cout, but it was a mistake ; d. Is cerr slower than cout?

I know perfectly well how assignment works. However, "int f { a = b; }" isn't the same as "int f { return a = b; }" ;) In this case it can be smth with how return value is stored on the stack and how exactly the code is compiled. However, missing return is Undefined Behavior, so compiler has full right to compile it to "while (1);" or to "exit(42);".

That's magic in C. You can program a one-liner gcd or disjoint set XD

This isn't accepted code:

BigInteger n = new BigInteger(next()); BigInteger a = new BigInteger("2").modPow(n, new BigInteger("5")); BigInteger b = new BigInteger("3").modPow(n, new BigInteger("5")); BigInteger c = new BigInteger("4").modPow(n, new BigInteger("5")); System.out.println(a.add(b).add(c).add(BigInteger.ONE) .mod(new BigInteger("5")));

But this is accepted code:

Why? Are these codes twin?

My Ac solution was on python if int(input())%4==0: print(4) else: print(0) solution

Check out room 23: Slovak domination!

what do you mean?

Me and Bobik are both from Slovakia and take top 2 places. It's rare to see 2 people from a small country in a room together, and taking the best places is much more rare.

two coder in one room means these two coder registered nearly at the same time.

According to the registrants' page for that contest: Bobik is 27., I'm 1102.

nope.avi

I have thought the room is according the order I register... Oh, it is wrong... I want to find out the algorithm for the place of room.

I don't know what it is, but if I was the one coding it, I'd make sure it's randomized and sufficiently complex so that nobody could register 2 accounts in the same room to get hacks — and, of course, people just registering in the same room for the lulz.

Omg, that's unbelievable! How did you manage?

It's magic :D

I have no other idea how to explain it.

http://codeforces.com/contest/455/submission/7392292 TLE just because I used vector ?

ignore me. I made a silly mistake

can anyone explain div1-B . I was trying something with trie ....but coludnt get it ...

Here it goes, hope I explain my solution well enough:

Firstly we build a trie. The root of the trie is the empty string. Now the game proceeds as the first player starts in the root and then chooses a child to go to. Then the next player chooses a child to go to and so on until you are in a leaf, when the current person loses. Now to efficiently solve the problem you must compute two values for the root position.

1) Can you win if you try to? (is it a Winning or Losing position)

2) Can you purposefuly lose if you try to?

Both are equally simple to compute. Simply start from the leaves and go up the tree computing each vertex through its children. The computation of both values is simple and is as follows:

1) If you can move to any lost position, then the current position is won. Otherwise it's lost.

2) If you can move to any position that CAN'T be purposefuly lost, then the current position can be purposefully lost. Otherwise it can't be.

Now how do we compute our answer? Well let's look at a few cases.

1) One simple case is if the root position is lost, that is you can't win if the second player plays optimally. Well then the answer is "Second" as he could easily win all games and the loser would always play first again and lose

2) If the root position is won, and it CAN be purposefuly lost then the winner is "First". This is due to the fact that he can purposefuly lose until the very last game where he can win, no matter what k is.

3) The last case is if the root position can be won, however it CAN'T be purposefuly lost. Well then it is obvious to see that if some of the two players wants, the game can be played in such way so that the first guy always wins. Therefore it is easy to see that if k is odd the first player will win, and if k is even the second player will win.

Hope I helped you :)

Nice ans .. thanks!!!!

thanks..well explained

if possible please provide the code as well...

You could easily retrieve it from my submissions : 7384830

Array W is true if the position is won and array LI is true if the position can be Lost Intentionally.

Thanks a lot ....it really helped

Why no editorial still?

I dont think editorials cannot be shown during systest (when it takes 100+ minutes)

Oh please show the editorials now.

(Its 2 hours since end of the 2-hr contest)

My submission was judged as WA on test 20 but when I use custom invocation, everything is OK. Please check! 7377515

7377531 WA with no reason? I submitted the same thing in practice and got AC...

Same to my situation, I have just resubmitted my in-contest code.

Same problem with mine 7395010

i want your advice i want to learn something to make an app i can feel after finishing it like "i did something in my life" so any advice ? note that i started to learn android but i don't know if there is anything better

plz reply :(

i'm still student 20 years old

Thanks for minus!

I can't stand that Imagine my excitement when 1,5 min before the end of contest I finally debugged my D. Imagine my anger when few seconds later it turned out that Internet crashed in a place I was coding and I can't submit it. Imagine my anger when I got to know that my C got very weird TLE which resulted in 39->262 change of my place. Imagine my anger when I submitted D on practice and it got AC!!!! And now my C got accepted after deleting one cerr (without endl's, so it is really fast)!!! Words won't describe my irritation at that moment ^&*(%^%^*!!!!! I should have took ~10th place and I got 262th! ARGH!

imagine my anger when I submitted a code for D in last 5 seconds and I got "codeforces is temporary unavailable"

I see that your code doesn't pass 1st pretest, so it is not that bad feeling afterwards xd. Btw I once managed to load my code, but haven't managed to click "submit", I was late about ~1 sec and it passed after the contest. Moreover it was E (I never got E accepted!) and I spent 15 mins of that contest doing nothing on facebook xd.

I fixed my mistakes in that submission then submitted again in last 5 seconds so why it's not a bad feeling ?

Hm. sometimes I also get angry, because of some unlucky circumstances, but when I submit my code after contest and it's not passing I'm getting calm. So far, I don't see your solution among accepted, so I guess that it's the case. But when it gets accepted xd...

Still you gotta admit, getting "codeforces is temporary unavailable" while trying to submit or open a problem is quite irritating.

Yes, I have to. I'm really a professional in category of whining about everything and if it had occured to me I will surely get annoyed :P.

Bredor has never participated in div 1 at all. Hey bro are you going to compete?

I have some problem with my div 1/B submission

this is the code I submitted during the contest, and got queued until the end of the contest. The verdict said WA on pretest 1. But it appears that there is no output in the submission above.

Then I submit this code after contest, the very same code but with assertion commented, and it got accepted (I tried to post the exactly same code but the verdict is exactly the same with my first solution; no output at all).

Does anyone knows what's happened?

Can we continue to solve problems?

I see the most of the solution of DIV 2 Problem LAPTOPS solved using sorting in O(nlogn) complexity. But it can be solved in O(n) . Suppose for "Happy Alex"

price[i] < price[j] ....................equation_1 quality[i] > quality[j] ====> -quality[i] < -quality[j] .................equation_2

let's add equation_1 and equation_2

price[i]-quality[i] < price[j]-quality[j]

Difference[i]<Difference[j]

so compute all the difference , get max difference and min difference if max_diff!=min_diff

then "Happy Case" else "Poor Case"

There is much easier solution using piegon's hole principle.

hussieneloy would you like to explain ?

But does Difference[i]<Difference[j] imply price[i] < price[j] and quality[i] > quality[j]?

@Vintarel yes

Both the price and quality numbers are limited from 1 to N. Since they are unique, the only way the prices are valid if they look like this:

(for example, if N = 3)

So you can just parse it as you read it, and if price != quality for any pair, you just print "Happy Alex" and break. Otherwise, print "Poor Alex".

It’s my first time in CF and feel 2exicited. But I got TLE for cin ,which depress me.

Why is my submission skipped? 7380034

prost))0)

Sorry, but I don't understand what you mean.

simpli))0)

what is up with adding ))0) to the end of every comment of yours?

also, what happened to 7394707? 7395446 is almost the same code (one constant changed, just to make it different from previous code) and it got AC?

do i lose points for 7394707? it says

Only the last submitted solution will be judged. All previous ones will be skipped.

During contest I got TLE 121 on problem C: 7391661

Exactly the same code got AC in practice: 7396418

This might be caused by server load during the contest, and I request that my in-contest submission is rejudged and considered correct.

Your code in practice runs 951ms. IIRC, variation of execution time on codeforces is ~40-80ms, so nothing surprising that it failed during the contest.

If it was WA then yes — it should be considered wrong. But IMHO if a solution once once fails time limit due to overload, and then passes, it should be considered correct.

I can't find how such cases are considered according to Codeforces rules though. I think it's up to problem setters and administration to decide.

That's not due to overload. Try submitting your solution again to practice several times (adding whitespaces to make it re-run the submission). I've just tried, and it gets TLE ~50% of the times.

I think usually on CF they don't change their verdicts. E.g., ~3 years ago one of my problems failed getting TLE and passed in practice with 100ms margin. Back then they probably had slightly different machines, and now it's not that bad.

7396999 Here it passed again, so the fail during contest is definitely due to system load.

And here it failed: http://codeforces.ru/contest/455/submission/7397092

I'm absolutely sure it's due to the natural variance of execution time; 40ms margin is very tiny.

I agree that it might equally fail and pass. My question is, how are such cases handled on CF? May be some of these points:

or something else. I would appreciate an official comment from problemsetters/administration.

Anyway, this particular solution had the same chance to pass during the contest, and I might be somewhere around 50th place, not 286 :)

I believe it's "submission is correct, if it got AC on the systest", with "submission is systested if it passed all pretests, is the last submission of that user on that particular problem and wasn't skipped for cheating". So it has to pass all pretests on 2 runs and all other tests on 1 run. Of course, with possible reruns.

Maybe you noticed that usually, the authors of the round have solutions that fit in the time limit comfortably. That's because the TL is chosen so that a reasonable constant factor wouldn't pose a problem, usually 2-5 times that original solutions' runtime. And I think it's safe to say that a reserve for cases such as yours is included.

The practice is that the system test results are final in this case.

Check out my submissions in practice — I tried submitting your code several times (the only difference is adding a comment) and got AC 2 times out of 9. Based on this, I don't think a rejudge would make much of a difference, unless the code was rejudged until it got AC (roughly 1-5 times, I'd guess).

where is the rating result ?? ?? ?

I'd personally wait until all the matters with weird compilation errors and wrong answers are resolved before updating ratings (there were, and still are, a few). In my opinion, it's way more important to carry out the competition correctly rather than immediately update ratings...

v karagande

actually i got A & B accepted so i'm just excited for the result sorry for misunderstanding

Country Wise standings is updated.

And it was a pretty easy bug to catch, too... :(

I used grundy numbers for problem B Div-1. I have no idea where it is failing. Can anyone please help me find the error?

Link: My submission

I'm not 100% sure here, but I think that Grundy numbers work only when both players want to win. In this game, it's sometimes optimal to lose until the final game comes around.

I am using grundy numbers only to evaluate one game. For each possible starting move, I find the grundy number for that move.

Now if I find all starting moves to have grundy number > 0, then if k is odd, output "First" else "Second".

If all starting moves have grundy number == 0, then answer is "Second".

Else, answer is "First" as he can keep losing until the final round and win the last one.

Test:

Your answer is "Second", but right is "First". You should check whether first can lose if

hewants it, not if second wants it. In test first loses 99 games by a-a-c-a and wins last by a-a-b.UPD. BTW, you store "edges" in strange way. Are you sure, that you can't make move from valid string by edge into non-valid string (for example, edge was "generated" by other input string, then string to which current position is prefix)?

OH! I totally missed this, thanks a lot!

I think the edges part is fine. For example, in the test case you have given above, ['a'][1] has edges to ['a'][2], ['b'][2] and ['c'][2].

UPD: I've realized why it is wrong. :-|

consider this test :

aab

bac

according to your code edges[a][1] = {b, c} but this is not correct. for "aa" the next letter is just 'b' and for "ba" is 'c'.

It seems I have gone wrong on multiple levels here then. :-(

Thank you for the clarification.

Quote from your code: "//I'll shit bricks if this happens"

You'll definitely do this because of test 71. I did the same mistake.

Hahaha.. Well, hard luck.

Why the output is unexpectedly 0 in 43rd test case ? Submission id: 7389527

The for statement should go till 100000 instead of n and you should cout max(ans[100000], ans[99999]).

oh..Thanks.. I was hoping to become Expert for the first time but became Pupil! :(

Edit: Did not notice that there is already a post that has answered

Is it just me or was Div1-B really confusing? I thought during the contest that the players will play optimally in each game, and not considering all k games....

No, the result is determined by the following sentence:

"Guys decided that the winner of all games is the player who wins the last (k-th) game."Actually you're right. But for example after contest before system test, I asked my friend who tried to solve Div1B, "Play for win, for each game" is optimal?, he said "I didn't think it". Problem doesn't say "You don't need to play for win, for first

k- 1 game.", it says "You have to play win, for last game." So you have to make a little observation.I don't know if confusing is the right word. It's just a matter of analyzing the problem fully, paying attention to every detail.

I did consider K games, but I forgot about the fact that people can intentionally lose. (I thought of using K mod 2 to determine the output once I analyze a single game).