Hi everyone!

Codeforces Round #267 will take place on September 18th at 19:30 MSK My name is Yura and this is my first Codefocres round and I hope not the last.

I'd like to thank Fedor Korobeinikov (fk2012) and Alex Vistyazh (netman) for helping me to test all the tasks and prepare this round. Also, special thanks Gerald for helping me to prepare the tasks, Delinur for translation of all problem statements into English and MikeMirzayanov for Codefocres and Polygon.

I hope that everyone will find the problem for himself, and plunge into the student's life.

Good luck! =)

Third Belarusian contest for last 2 months:)

And I hope not the last:D

I think this time it's better to not hope for math! If you remember problem B of last contest (round #266), most of the passed solutions, failed in system testing! Also right now it has less accepts than problem C of that contest!

Good Luck!

I liked question B even though my solution got hacked. It did not seem tough(probably because it was level B and I was expecting it to be easy) at first look but required careful observation.

First time participating out of competition!

All the best for your round, Yura!

Thanks a lot

netman From grey to red , your graph is awesome it gives hope =D

Thank you!

thanks Too ^_^

And netman's graph will be much more interesting if his rating goes from

redtogreyagain and becomes lower than worse :Ddon't u mean

netman's graph will be much more interesting if his rating goes fromredtogreyagain and becomesthan worse :D~~lower~~worseThe time link on this blog is broken, but according to the contest schedule, the contest will be held on Sep 18th 2014 at 19:30 MSK. So it will start while the CF Training Episode 2 will be running. Therefore, I think the schedule should be changed so that people can take part in both contest and training.

I'll think about it. It seems I'll move 2014-2015 CT S02E02: Codeforces Trainings Season 2 Episode 2 (CTU Open 2011 + misc).

Why my 1st question is skipped?

Does "the student" also have too much biology homework?? -_-

never heard about

Codefocresbefore :)I know. Focre.

Following standard procedures, I have to communicate that:

This is my first round out of competition!!! :-)

I really don't feel prepared for Div 1 right now, seems like I got lucky last round...

Hope today I do a good job and build up some confidence for my first Div 1 round!!

Yeah, same, my solution for E last time was apparently flawed but worked because of weak testdata.

I hope that the contest can be earlier so that I needn't stay up late. (I'm from China)

Nope, I love this time, in China, I always get up at 11:00am and go to bed at 3:00am, now I'm in very good health!

lol, you should see the sunrise with more frequency. It is good for your brain!

wow , over 4000 registered . Hope CF doesnt crash & can fully function. Good luck & high rating to all :)

Elo rating system can't provide high ratings to all ! therefore good luck to all !

i know that , but that doesnt mean i cant hope for high rating to all ^_^

unfortunately it crashes at the beginning of the contest, when most of the participants are submitting for problem A.. Hope that future contests will run smoothly :)

Hope to enjoy it!

Nice to meet you~

Seems to be a good contest :D Good luck everyone ...

don't miss to surprise us with scoring system just before the start of the contest :D

10 minutes left. What about score distribution? Good Luck.

wow final number of registration users is x4777

Lucky Number

Actually, x4776.

Actually it's my fault I didn't make a screenshot :D it was x4777 but I don't know what happened

And now it's 4775 :D

2 minutes before the contest. Still unknown score distributions.

what about scores?

long queue!

Worse is on a comeback! He solved the first 2 problems in 9 minutes!

Whoops.. nothing can change him :D

http://i.imgur.com/B6sMIkH.png

See now, Seems like he is back on usual track :)

don't let that fool u. he solves problems just so that he can get

Pretests passedand thenhackothers (unsuccessfully, ofcourse).There should be an online issue redressal system. Commenting on the problem to get clarifications from the problem setter depending upon the language of the problem. Or is there already existing?

What a shitty contest indeed.

A-C easy.

D-E obvious.

New superstar!

http://i.imgur.com/igG6Qzz.png

P.S. Nothing can change worse :D

apparently, fiterr can. :D

In problem B, if x[i] could be zero, i'm sure there would be many hacks! Because i saw many users in my room which said while (num>0) and if num was zero, their code wouldn't work!

Damn!! What was the tricky test case for C? My solution got hacked.

4000 60 60 0 0 ... 0

or

5000 1 5000 1000000000 1000000000 ... 1000000000

I got two hacks with these

This is just great. I got hacked because Python has failed me yet again. Maximum recursion depth exceeded. So cruel

How to solve C?

dp[i][j] = max(dp[i-1][j], dp[i-m][j-1])

Can you be more elaborate, please? What does the dp state (i, j) signify?

Would you please elaborate

It should be dp[i][j] = max(dp[i-1][j], dp[i-m][j-1] + sum[i] — sum[i-m])

sum[i] = a[1] + a[2] + ... + a[i];

dp[i][j]: In first i numbers, you choose j pairs. you can get the max ans.

Actually his algorithm is also correct !

Whose?

DP : dp[i][j] denotes optimal answer when we choose i m-length sub-arrays before index j+1. Also b[j] is sum of first j elements of array. Then : dp[i][j] = max(dp[i][j-1],b[j]-b[j-m]+dp[i-1][j-m]); //You either choose j-m+1...j as a sub-array or not.

what is the hack case for D? is it about cycles?

I guess it is about overflow.

Answer could not fit in 32-bits type.

How come? The total input length could not exceed 5*10^5 =>

~~Answer <= Total input size.~~UPD: Thanks for explaining the test case. While the number of r's will be <= total input size, the total length of final words <= 5*10^10.

Example:

let referat = "r" 100000 times

let "a"*100000 and "r" be synonyms.

sample

100000

r r r r r ... r

1

r eeee...eee(100000)

Oh oh oh ... you mean in case of minimizing the R ... we pick a long string each time that the total len will be larger than 32-bits?!

Challenge Accepted :D Nice Hacks !!

I've changed int to long long but unfortunately the new verdict was TL :(

First find the R's and Len of each string store it somewhere by an ID and work with these numbers.

That should work!

How to do C?

DP : dp[i][j] denotes optimal answer when we choose i m-length sub-arrays before index j+1. Also b[j] is sum of first j elements of array. Then : dp[i][j] = max(dp[i][j-1],b[j]-b[j-m]+dp[i-1][j-m]); //You either choose j-m+1...j as a sub-array or not.

Nice solution. I definitely need to learn DP.

What is the approach to solve D ? I tried to solve it by dp with state st(index , no. of r , cur_len ). Will this represent a unique state or not ?

i did it by simple dfs. Will see is wrong or not after systests

Simple DFS+DP won't work. You'll need SCC+DP.

aha. WA25.

what's SCC? got WA 25 dunno why.

Strongly connected components

You don't need to keep all of the edges. If you just keep the edges like

st1 ->st2 witch no. of r inst2 is strictly smaller thanst1, your graph will be DAG and you don't need SCC! :)(You also have to keep the edges between states with same no. of r if endpoint of the edge have smaller length)

I don't think I quite understand your approach. Could you please elaborate for this case:

i don't think this is right.

if we can change r to rrrrrrrr, and rrrrrrrr to e, it will be best answer.

maybe just didn't understand u

Yes you are right.

Sorry!

simple dfs + dfs + dp work.

first, we need to answer d[v] = min(d[v], d[to]) before dfs.

now, answer of cycle in 1 element of the cycle.

next dfs, we share answer to all parts of cycle, so here u can not use SCC

here is the code http://codeforces.ru/contest/467/submission/7850107

Nice technique, thanks :)

I love DP .... :)

Nice Problem C ... :)

Why my 1st is skipped despite doing only 1 submission http://codeforces.com/contest/467/my :(

Consider this case:

1

rrr

2

rrr rrrr

rrrr e

or even this one:

1

eee

2

eee efef

efef a

Why my 1st is skipped???

Submissions are skipped when exactly the same code is submitted before and judged.

I have submitted the code for problem A only once

It has also happened to one of my friend. Only submitted a single code to a problem but it was skipped with "JUDGEMENT CALL".

Why my 1st question is skipped?

How in problem C two same solution one got Accepted by c++ and other got memory limit by java?

Moreover, some solutions get ML on Java7, but AC on Java8.

Yes my solution on java 7 when I changed it to java 8 got Accepted . Very bad judging :(

I think, redjudge with ml 512 is a good idea.

We have to make revolution to rejudge all ml in problem C.

Why my 1st question is skipped?

if two person submit the same code it will be skipped ;)

How to solve D and E, could someone can teach me ? thanks.

How to solve D ?

realy HARD approch :|||| just sort the nodes and make dfs from sorted nodes :| look at my solution for better undrestanding

I'll Try to explain my solution.

Let's forget about the words we have for now and focus on the synonyms. Let's model the problem as a directed graph problem with vertices as the words we have in the dictionary and there is and edge from word

`a`

to word`b`

if word`a`

can replace word`b`

. Each word has a cost of <Number of Rs,Length>, If the cost of some word`a`

is smaller than the cost of some word`b`

, then it's always better to substitute word`a`

with word`b`

. But Notice that word`b`

can also be replaced by another word`c`

for example if`c`

has a smaller cost.So the first solution that comes to your mind is a simple dfs from each word to find the word with the smallest cost to be replaced with. The problem with this idea is cycles. If you started at some word and through the dfs you went back to that node again then words of this cycle can replace each other and the optimal solution is that they are replaced with the word with the smallest cost.

Wikipedia : "A graph is said to be strongly connected if every vertex is reachable from every other vertex". So words of a certain strongly connected component here can replace each other so let's find all strongly connected components and treat them as one node with cost equal to the minimum of the costs of the node of this component.

In our new graph there is an edge from node

`a`

to node`b`

, if there is any edge in the old graph starting from any node in component`a`

and ending in any node in component`b`

. Now we are sure that in our new graph there isn't any cycles and we can run the dfs we mentioned before to get the cost of the representative node of each strongly connected component.Finally back to our words, The cost of a certain word is the cost of the representative node of the SCC in which this node lies.

NoteA common hack in this problem was that the answer may not fit into a 32-bit integer.Here is my solution 7840587, I hope you understood my explanation :)

Easy to understand.Thanks! :)

Can you check if there is some issue with "Memory Limit Exceeded"?

http://codeforces.com/contest/467/submission/7840542 — This failed on 14th test case with Memory Limit Exceeded

http://codeforces.com/contest/467/submission/7842953 — This failed on 3rd test case with same error. This is supposed to use less memory (I halved a array size) than above solution. That passed 3rd case and this failed. (I checked that both are same test case)

-Anudeep

Couldn't one solve C with segment tree? I've almost implemented it, hadn't enough time, but don't know if such a solution would pass tests.

I submitted 7840896 and 7841275. The only difference between these two codes is \n character at the top of printf. Although, they give different verdicts (wrong answer on pretest 2 and wrong answer on pretest 4). How is that possible?

I tried to hack this problem with m=1000, as the coder stored the value in 1001 th index. But he/she declared array like a[1000]. My hacking was unsuccessful ... How did it happen ??? :(

submission link... 7839186

your submission link is wrong it will be 7839186

Unlike java, which directly gives out of bounds exception, C++ silently tries to access the memory index.

Two cases can occur:

1. the memory access is not allocated to the current program: in this case it is SIGSEGV(e.g. allocating a[1000] and accessing 10^7th element.

2. The memory access is allocated to current program: like allocating a[1000] and b[1000] and then accessing a[1005] could give some element of b since such small arrays are allocated mostly contiguous. So, if the memory access does not cause SIGSEGV and is not altered by an intermediate code logic, it will behave as normal (extended) part of array, and hence the program gives correct answer.

Why is my code giving Garbage on Pretest 1? Works fine on ideone and codeblocks.

http://codeforces.com/contest/467/submission/7841331

It is contest too???

Codeforces temporary is unvialable...

You are accessing i-l index in ans[i-l] . When i=1,l=m then you are accessing negative indices, which gives unpredictable behavior.

Why did my solution time out on test 22..? I used top down approach with memoization.. I think my complexity is O(nk) which is the complexity of most accepted solutions..

http://codeforces.com/contest/467/submission/7840201

you have n*k nodes ans each node use O(n) to update so O(n^2 * k ) in total ;)

Ohh thanks a lot.. Can you please give a hint on how to modify my solution to make it O(nk).. ?

From every position there is effectively only one possible transition. Either start an interval from that point, hence you need not consider the next m-1 points and skip directly to the i + m point with number of intervals formed increased by 1. Otherwise do not start an interval and hence move to next index with number of intervals remaining the same. P.S. Have a look at my solution for better understanding. :)

I think that you did not check the exit condition when y == n+1 you should return

Your complexity is actually O(kn^2). Number of states is kn and from each state you are doing n transitions.

Why there isn't any UPD in the blog? Editorial publishment time, Score distribution, Top 5, ...??

My great congratulations to Bredor! ^_^

it would have been fitting if Bredor had become

Candidate MasterinRound #228. ;)467C - George and Job was a very nice problem. :)

I solved a b c and d but because of the contest stress I didnt realize that c was actually n^3. If I realized that the code I have written in the contest was n^3 I could easily delete the for loop from the dp function. By problem d because of not using long long I couldnt become div 1 again :(

Can the Java 7 solutions for problem C please be rejudged? Many C++ and Java 8 solutions with similar algos passed without a hitch while Java solutions using long[5002][5002] solutions failed with Memory Limit Exceed. Shouldn't the judging be impartial?

Can you explain, why Java 8 is passing and Java 6/7 not? Thanks

I don't know why its happening. But the submission with java 6/7 (link) fails while Java 8 passes (link)

Waiting for Editorial?

Can someone explain to me why I'm getting TLE on 467C - George and Job with this submission 7843970.

Try Implementing Bottom Up :)

reduce the problem to knapsack 0-1 would work with top down

Please someone help me find the bug in D. Submission — 7845185

your program doesn't handle cycles. consider this case:

Thanks.

Editorial ?!!

The Editorial will be ready tomorrow.

Soryy, can you help me?? I'm a new one, and i don't know how to give or send my answer to codeforces What should i do??

In the problem page there will be a tab

SUBMIT CODEclick on it and paste your code, choose the language then press submit.Can someone help me with my solution... dont know where i am getting wrong. Already tried enough :( http://codeforces.com/contest/467/submission/7845375

so can anyone tell me why generating all possible sums of consecutive m pairs and choosing the top k of them won't work in c ?

Because they may intersect and the problem states that no intersection is allowed

which part of the problem statement stated that ? edit : oh the boundaries part , ok . thanx.

Consider the array:

`0 1 1 1 0 0`

where`m = 3`

and`k = 2`

. You will choose the the pair`(1, 3)`

but then you need one more pair of size`3`

. So this is not going to work.Can somebody explain the other approach for D(without scc).

Many submission seems to be on the line of using priority queue with all starting nodes already pushed in it.

like this here

Though I have solved the problem using SCC and DFS. But I have understood the greedy Solution.

At first give some id to the string. Then if an edge is given like from A to B. Insert a reverse edge to your graph like b->a.

Now use priority queue or just sort the nodes by their 'R' count, and string length as tie breaker.

Then in ascending order run a BFS/DFS to cover all the ancestors of a node (lets say x) with the value of x. If you find a node is already covered ignore it ( so the complexity of running total BFS/DFS will be O(n) ). Why we will cover the ancestors with that value ? Because all of the parents can be converted to that node x and node x does have the lowest cost so far.

And the complexity is O(nlogn + n) = O(nlogn) overall.

Hope you have understood the solution.

Thanks man great idea :)

Hey can anyone explain what "Fedor wants to get an essay which contains as little letters «R» (the case doesn't matter) as possible" this means in problem D? As little letter as possible means what? Can anyone explain with any of the testcase provided? thanks in advance :)

That means that Fedor wants to get an essay which contains minimum number of 'r' or 'R' as a character and case doesn't matter means 'r' and 'R' consider to be same :) In case 2 :

`2`

`RuruRu fedya`

`1`

`ruruRU fedor`

we can replace

`RuruRu`

with`fedor`

where the final essay will be`fedor fedya`

. This essay contains only 1`R`

and the total length of the essay is 10.Hope it helps :)

Thanks very much :D.

I really enjoyed the problems, one of the best Codeforces rounds, but soon after the beginning of the round, Codeforces kept on 'Codeforces in unavailable' for more than 10 minutes. It's sad because hundreds of other coders made submissions for B while I was unable to try. It really should be avoided.

Can someone explain problem E

:) Hello

I have started participating in the contests here, yday I did 2 questions AC but here it shows only 1. Second I did, in three attempts(3rd was AC). But then how in final standings, its showing only one accepted. Even in the last contest, I submitted my sec solution i the last two minutes of the contest. There was a long queue for the judge and my solution was evaluated after the time got over and passed all cases, but wasn't counted in my solutions accepted during the contest.

M i getting wrong somewhere..? Please help!

check your submission history. your code for B failed on test case 15.

OH,.. thanks! When will we get to see the editorials?

Actually any AC during the contest won't mean that your code is right and will pass the test cases.It just means that it have pass the pretests which might be weak.after any contest all of ACs would be rejudged by all of test cases and they might fail at that time. sorry for my poor English.

When will the editorial be up?

I saw someone using the greedy algorithm to solve the problem E. But I don't know how to prove it. Can someone explain it?

I got time limit exceeded with this approach for problem C: dp(start,k2)=max(sum2[start]+dp(start+m,k2-1),sum2[start+1]+dp(start+m+1,k2-1),.......)

where: dp(start,k2) — maximum sum from "start" to "n" when "k2" pairs have to be chosen

sum2[i] — sum of m elements starting from index i

How is the approach given below better than my previous one:

dp(start,k2)=max(dp(start+1,k2),sum2[start]+dp(start+m,k2-1))

Here is a link to the codes:

Previous code: http://codeforces.com/contest/467/submission/7862092

Modified code(after seeing the answer on this page itself): http://codeforces.com/contest/467/submission/7862534

Editorial please.

where is the editorial ??

where is editorial link?

Can somebody please explain what is going on with problem C for me. I keep getting out of memory error. I have resorted to copying Java 8 solution of VArtem here: 7829968, and yet I still receive out of memory error, while for him it passed. See my submission here: 9636506 . Can somebody please explain what is happening, I am going out of my mind here?!? By the way, I typically never copy someone else's solution to submit, however I only try after not being able to solve problem for month, and keep thinking about it and no matter what it is out of memory error for me!

where is the tutorial of this contest ?

link =)

It's available only in Russian.

30166622

I've tried my best to explain the solution of Div2 C here in my own language. Hope it helps.

It is to be noted that the code is in java and fairly generic names are used for understanding purpose

when shall the editorial be published ?