Greetings to the Codeforces community!

Regular Codeforces round #316 for participants from the second division will take place on August 13, 19:30 MSK. Participants from the first division are able to participate out of the contest.

It is my first round on Codeforces. Hope you will enjoy this round.

I want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve these problems.

**UPD:** The score distribution is standard, **500-1000-1500-2000-2500**

**Good luck!**

**UPD:** **Contest is finished. Thank you everyone!**

**Congratulations to the winners!**

**UPD** Editorial

great contest :))

same here... :)

I'd prefer 11:30 pm than 9:30 am (my local time), when I need to be in the office working.

No reason to complain, guys — this is Internet (i.e. INTERnational NETwork) and international site. Get used to it.

I almost thought Internet stands for International Network :)

In my city is 00:30 pm QAQ

Me,too.And I had to wake up at night to join the contest.

In my city is 00:30 am :)

Is it rated?

please answer me for this important problem :))

why ???

why why?

why why why ????!!!:D

Yes

seriously?????

You change my life by this answer

You are My hero :))

i just don't want to see unrated paticipants as first & second & so on ...

*don't want to see

tnx updated :D

get it

in my city is too late,it start at 00:30

wo zai zhe li yong pingyin ying gai zhi you ni neng kand de dong le~

What about the point distribution???

Distribution be declared a later

Is it depends on your result in contest?

Lets hope this round features a variety of problems with less math :P unlike the previous round

Why? Math is love, Math is live!:D

You won't gain anything Erilyth if all the problems are a piece of cake (except high rating).. It's better to learn something new and this doesn't mean necessarily a low rating by the way :)

Are you saying that all non-math problems are a piece of cake?

I'm alright with math. I just hope the problem statements are a little bit easier to understand.

I think the good round should include problems from different topics ... because if you are not good at a topic you can find another problem with a topic you are good at .. and this will be fair:)... but also math is very important and any programmer should be good at it.

RIGHT, but in this way it is important that for example problem A is dp or problem E !!!

Very good that we have a lot of contests. ;)

Wonderful

I haven't solved a single good question this week. How do you guys stay motivated? Please give me tips. I love coding, but sometimes, I just don't feel like it, but that won't do. Please help :)

The key is to upsolve once the competition is finished. In other words — read the editorial and solve everything you weren't able to solve during the competition. This way you learn from your mistakes and get better.

My main motivation is that I'm getting better with each competition. When I started Codeforces I struggled to solve A and B, now I'm consistently solving C and pushing towards Div1.

2 hours is a very small amount of time to think about all the 5 problems. Then editorial comes within the next hour, so, 3 hours in all. Shouldn't you spend at least a day before jumping to editorials? Besides, looking at editorials suck out the joy of solving a difficult problem! I like to give the problem a fair shot before I open editorial. Why is your method more effective than mine, can you explain?

I might have expressed myself wrong. I don't look at the editorial immediately after the competition, and if I manage to get some kind of an idea (or anything to work around) within an hour or two, I try to solve it without an editorial.

That makes sense now

Let's look at it in a different way: don't you think that wasting whole day on a problem is bad, because you might spend that day on learning much more things instead of reinventing the wheel?

If I can re-invent wheel, who knows what else I can invent! In terms of ratings and contest performance, I can see my method is hardly efficient......but it is so much fun! I learned DP(whatever much I know about it) almost on my own... I learned LIS in n log n on my own.... and just a few others.....

I heard similar ideas from people who are performing much better than me, so the fact that your method doesn't work for you

(at least so far)doesn't mean that it is bad method in general. Maybe you need more time, maybe you simply aren't trying hard enough.From my point of view — it may make sense when you already know all basics and you are currently working on improving some

"thinking skills"or stuff like that — but at the very beginning, when you simply need to learn a lot of different stuff, it doesn't make much sense for me.I know I lose motivation easily(I don't practice hard) .....that's what my first comment was..... :/

congrats you finally got into div1 !! Happy for you ! and i m experiencing the same too !

You have to put the following tips into consideration:

- If it took you more than 2-3 hours and you still can't solve the problem, don't hesitate to view the solutions of other people and the tutorial as well.. this will learn you how good programmers think.

- Of course start with the problems that are solved by many people:)

- Believe that you will not be able to continue if you are impatient.

- Codeforces enables you to ask questions and send messages.. so, why not asking for help?

This will be the best contest of this week

On this site at this time.

I think this is the last contest of August.

Why do you think that?

591 unrated users and counting.. ok.

Don't submit code. Solve in silence. That's how I'm going to do it

Hi guys! This is my first contest and I hope not the last. I hope that one day we will take part in CF-International:D GL && HF!

Woke up in the middle of the night, and find out that I didn't register after finishing problem A...

Cheers!

How to solve D?

http://codeforces.com/blog/entry/19753?#comment-245874

E was almost exactly http://www.usaco.org/index.php?page=viewproblem2&cpid=553

Only difference was it was a rectangle, not a square...same constraints, modulo, and all.

I noticed that and still managed to screw it up... damn rectangles.

Same XD

too many hacks on problem B

Only tricky case was 1 1, right?

No , I hacked 2 or 3 codes with "3 2"

No I also hacked one problem on 5 3

My hacks were :

1 1

5 3

The contest was really nice, especially C and E.

Congratulations radoslav11 you made a perfect contest.

Thank you :)

Hacking Contest!! it's very nice :D

Thank you josdas. Nice problem statements, and not strong pretests -> posibility to hack :)

This round was very interesting thanks to the 'Hacks'. I've never seen Div. 2 this passionate about hacking.

Did anyone solve E with hashes??

How would you do it? There is too many possible paths = too many strings to hash.

I tried hashing, but my solution exceeded the memory limit. In hindsight, it obviously wasn't going to work as there could be (500 * 500 / 2) ^ 2 pairs of positions, which is well over 256MB when hashed into longs.

Did your solution work?

Isn't it something like 2^500? How could you achieve (500*500/2)^2?

My submission

I kept track of two positions while running a DFS, with one starting at (0, 0) and the other at (N — 1, M — 1) and continuing until either the two positions met up in the middle or passed each other. To take care of overlapping paths, I hashed each pair of locations. There are (500 * 500 / 2) possible locations for each the first and second positions, giving a total of (500 * 500 / 2) ^ 2 possible pairs.

ok, it makes sense. Though I don't see a way to improve this solution (cutting memore consumption for example).

Wasn't E too basic/known? At least, I have thought of the same problem a few times when I don't have what to do :D However, it was a nice contest, I liked D :)

Same here.

For D, how to make projection of arbitrary point to arbitrary depth?

Ok, found in comments: DFS with timer (sample submission by FatalEagle)

D has offline solution, right?

great contest ! thanks ":))

This contest had a really good difficulty curve.

A,B,C easy, D,E very tough (if you never solved something similar)

It's a lot better than the usual CF contests, which have ~3000, ~2000, and then ~500 solutions, because it let's beginners solve more problems than usual. Although I do agree that D and E were very tough relative to A,B, and C, moreso than usual.

Room topper for the first time :D

problem D strict time limit :/

No. For D there is a O(N + Q*logN) algo. Your code is O(Q*26*logN) which should be TLE.

Can you describe the basic idea of the solution? Thanks

Key steps:

FatalEagle got AC with Q*26*logn complexity. See 12502770

My code with same complexity got TLE'ed. :(

My solution is the same U_U , but i got TLE.

Submission

I figured that the constant is low enough so fast input should make it work (input can be very huge).

Your solution with fast input works too: 12517730

I have seen that using the upper and lower bound of C++STL directly in the main , is faster than make a function calling upper and lower bound.

TLE

AC

I got AC by defining my array as 5*10^5 * 26 rather than 26 * 5*10^5. But for similar situation on Codechef defining like the latter one had less overhead than first one. My AC'ed submission after making these changes. 12517583

This was the codechef ques where we had to do the opposite to get 100 points. Codechef Ques

Not sure what is happening here. o.O

You get more cache hits in the first way, since you want each letter of each level instead of each level of each letter (in which case 26 * 5*10^5 would be the better way of declaring the array).

Thanks. That makes sense. :)

is using lower_bound/upper_bound STL faster than implementing binary search? because with the same complexity as yours, mine get TLE.. my submission

mine O(Q*26*logN) solution got TLE What is correct approach though?

Time Limit was weird. My code with the same

O(26QlogN)complexity passes in1980 ms. This seems unfair towards many participants .Link : 12513092

yeah, I had same implementation with vectors and STL lower/upper_bound functions. I got TL when submitted it, and decided that it should work fine if I remove vectors and STL lower/upper_bound functions, but this did not help either. :( I do not really understand why my solution has bigger constant though :( I'd like to understand it.

Very nice idea with bitwise xor's!

Nevertheless, my solution similar to yours gets TL. Could you tell me why?

Unnecessary strict constraint i think , a improve of a 26 constant is not a big improve in my opinion . BTW the problem was very interesting.

I think you misunderstood my comment. It was NOT 26 --> log, it was 26*log --> log, which makes the program 26 time faster.

oh, I think I got it. We have to use bitmasks. thanks for the hint.

I mean a 26 constant improve is not a big improve in

my opinion, i think a nice improve is taking for example improving n^3 to n^2 , and if someone really like improving some kind of things of contasts , there is a lot of problems in SPOJ that you can solve , i know that my algo is 26 n log n and it past pretest , but fail in system test.Well, maybe the 26 constant improve is not a big improvement according to you. But, there's also a O( n + 26 * q) offline solution, which might be a bigger improvement according to your judgment. Link: http://codeforces.com/contest/570/submission/12517417.

It's improvement big enough to distinguish solutions by time. So it is a big improvement.

my O(Q*26*logN) got AC :)

how to optimize it to O(N + Q*logN)?

UPD:sorry my code is O( Q*( 26+ log(n) ) ), but it took about 1800 , strange!Unfortunately mine not.. To take away 26 you make xor sum on BIT,and every character is represented as a bit.

If the answer on interval has more than two 1 bits in its binary configuration the answer is no.

Xor helps you for parity,because 2 bits of the same (two 1's) make each other disappear.

Really strange. I have the same idea. 12517064 — 967 ms.

i upsolved D using this thing: "if there r no letters X in subtree of vertex V -> continue;" passed in 1300 ms

http://codeforces.com/blog/entry/19753?#comment-245981

Changing 26 * N array to N * 26 array gave changed TLE to AC :/

Haven't read B statement to the end. I can't understand what the importance to the player of which number he chooses — bigger or lesser if it gives the same probability to win...

"If there are multiple such values, print the minimum of them."

Are future contests going to be scheduled on weekends? I know many of us have school starting soon.

Agree x100000. These contests are in the middle of school for me at 11:00 or 11:30 AM. Would be really nice to have them on the weekends.

The only thing I've thought about in D was to cache the parity of all descendants of a node on all child layers in that node. This could occupy a single int per node per layer, if encoded as a bit string. However, this wouldn't be enough, since it's obviously an O(n^2) solution in terms of both memory and time, so it is definitely not feasible when n=500 000. How did you solve it?

UPD: The shortest submission 12506489 is also quite clear. I guess using a DFS clock and then binary searching on each layer is a standard technique.

one of my friends :

here

I think i can relate to it.

Not reading whole problem, or reading it incorrectly is a major issue for me. I don't know what happens during a contest, so i got three WA in problem A.

Codeforces Round #Hack (Div. 2)

From CF Round #Hack (Div. 2)

What were the states and transitions for the problem E dp?

dp[x_first][y_first][x_second][y_second], but this will TLE and ML.

So we can convert the state into dp[x_first][x_second][len] witch is

O(N ^ 3)Memory and Time.Can you please explain in a bit more detail, the DP solution for E?

Thank you for such a wonderful contest!

How did someone hack 24 solutions? can we hack people's solution from other rooms ?

You can easily open a room and see that there are more than 24 users in a room

There are 26 contestants (at least submit once) in our room, including myself, and only 23 of them pass at least a problem's pretest :)

But you can hack one person more than once.

Yes, so i am just pointing out that the number of users can be less than the number of hacks.

you can hack a person more than once and you can hack more than one problem .

Also, it's possible to hack someone's solution twice. Submit, hack, resubmit, hack. Of course, the hacks must be distinct cases because resubmitting requires the submission to pass previous hacks.

Why this code http://codeforces.com/contest/570/submission/12498380 passed system test ???

It should be wrong answer. For 11 6 test it will be generate garbage value.

try 5 3 , it should generate garbage but it gives 4 !! can anyone explain why this happens ?

Try custom invocation. Miraculously it gives correct ans for this and all other cases -_-

I think compiler removed "if(l>r)" since "a" wasn't initialized anyway.

http://codeforces.com/contest/570/submission/12515787

Code works fine on my pc as well as [on ideone].

However, same code gives tle on codeforces for same test case of n=5. What is the reason? (http://ideone.com/G1AApF)

I guess you have some bug (like checking array[-1]) and it causes undefined behaviour. Then everything could happen.

I can't find it! :(

E.g. here is checking s[n] — "while(s[i]=='.' && i<s.size())". Use custom invocation to debut 5th test. You can comment part of your solution and check if you still have TLE.

This may be a dumb question but .. is the 'problem set' page temporarily blocked during a contest ?

josdas Thank you for this contest , keep going :)

Got five successful hacks on B using the "1 1" test case.

After system tests: WA on "1 1" case.

Dammit.

At least you have gained more than you have lost :P

Problem C = KISS

Keep It Simple, Stupid!

:( I never learn

KISS for all problems :)

I got TLE on that problem (problem C) :( , but for small cases, my code could run...

Auto comment: topic has been updated by josdas (previous revision, new revision, compare).That moment when you make 3 problems in one hour and you realise that you did the first problem wrong because you did not analised the simple case ..... So disappointing. But still my rating raised. A positive note though.

thank you for contest!:)) we want Editorial fast :((

By the way, the second problem from here is pretty cool: http://codeforces.com/blog/entry/17291?#comment-221267 :D Seems like this was the source of my thoughts about such problem.

How to solve E?

You will start travelling in both directions (from the upper-left to the lower-right and from the lower-right to the upper-left). For making it simpler, we can make a copy of the input matrix and rotate it on 180 degrees so we move in the same direction in both of the matrices. The dp state will be dp[row1][col1][row2] (the number of ways to reach those cells and have the same strings so far) since from this we can get col2=row1+col1-row2. We can notice that if a[row1][col1]!=b[row2][col2], then dp[row1][col1][row2]=0. Otherwise dp[row1][col1][row2]=dp[row1-1][col1][row2]+dp[row1-1][col1][row2-1]+dp[row1][col1-1][row2]+dp[row1][col1-1][row2-1] so we need the information only for row2-1 so we can store only the last two tables. You can take a look at my submission for more details, although it looks really crappy.

http://codeforces.com/contest/570/submission/12505236 Please check above code of problem A(round 316 Div2) It gives wrong answer in online compilation while it worked perfectly on eclipse. It seems that runtime error occurs in nested for loop. Please help

Hi,I guess it's because of array,a,you should write a[m][n] instead of a[n][m].

Okay got it Thanks

Can I resubmit your solution with my changes?? I want to know the reason :)

Your wellcome,It worked?? Was it because of array? After sending the next comment I saw this comment :)

Although this may seem stupid, but can anyone explain how to solve Div2 Problem B?

There are two main cases we can check:

Either there will be more numbers between N and M, or there will be more numbers between 1 and M

Take this set of numbers, for N = 10, M = 3

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

M is 3^

Notice that choosing 2 will mean you win on 1 or 2 Now look at what happens if you choose 4: You will win on any choice from 4 to 10.

In this way, you want to choose either (m+1) or (m-1), based on what would give more winning numbers Some code might look like

if (n — m > m — 1) print m + 1 else print m — 1

.... and don't forget to print 1 when n = 1

Thank you, that was really helpful :)

Don't feel ashamed to ask questions!

Auto comment: topic has been updated by josdas (previous revision, new revision, compare).D had a very simple offline solution too in O ( N + Q * 26 ) !! here is the link to it http://codeforces.com/contest/570/submission/12505776

Hi,

I can't figure out what's wrong with my solution for D... Here it is: http://codeforces.com/contest/570/submission/12521712 Please help!

Hey , I have a doubt in Problem B (http://codeforces.com/contest/570/problem/B).. if value of n is 5 and m is 3 ... what can be value of a ??

such that Andrew wins??