Good day to everybody!

The next round for the participants of the second division will be held at September 22, 2015 at 19:30 MSK. Traditionally, the members of the first division may take part in the contest out of competition.

I (Vladislav Vishnevski) and igdor99(Igor Doroshev) are the authors of the round. We would like to please Zlobober (Maxim Akhmedov) for the assistance in the preparation of tasks, Delinur(Maria Belova) for translating statements into English, MikeMirzayanov(Mike Mirzayanov) for remarkable systems Codeforces and Polygon, as well as our friends Dmitry_Aksenik(Dmitry Aksenik) and RevtIvan(Ivan Revt) for their assistance in the round preparation. This is our first round, and, we hope, it won't be the last one!

You will be proposed 5 tasks and 2 hours for their solution.

The protagonist of the round is the parrot Kefa, who likes money and restaurants.

Good luck and high rating!

**UPD:** The scores — 750-1250-1500-2000-2500.

**UPD:** Editorial!

3..2..1..Go!

Summary: Vladik and igdor99 would like to please Zlobober, Delinur, Mike and RevtIvan. It looks like they will have their hands full for a while.

I'm sure they will all be pleased if the round goes well :)

I assume gamamal tried to go for an obvious innuendo. I learn more about CF community every day.

In part I wanted to point out they made an English mistake, swapping "Thank" for "Please".

Why no div1 :/

And in the hope ... that i shall get some hacks :D GL & HF :)

Oh it will be a magical round.

P.S : Please see the tags.

And it's also a magical number of the round (321).

Tagsesh chie baz!!!

thanks for magical contest about parrot KEFA)

Do you mean Kefa ?

i just want raising rating .......

And also joy and benefit my dear ;)

Unfortunately, the probability of all users get raising rating is zero :(

hope to see hard math problems :)

Maths problems is sometimes interesting(brainstorm). But too many maths problems will make my brain feel tired.

It's just two hours :)

Занимаешся футболом и любишь матиматические задачки????

Страный ты однака...

i agree

i too

Div. 1 guys do not make new accounts please. :)

Toooo_Simple

Why did you make a new account then ?

You're unrated and you know that some of div1 contestants make new accounts and you know the whole story, Then definitely you're not new to Codeforces and I can say that you already have another account!

Why did you?

The one who is doing that is a retarded person!

I hope that it does't be dynamic. How about you? Do you agree with me?

we want div.1 contests .

:|

My last contest in summer! I'm going to school on Wednesday! Hope a good contest! Good Luck!

but from your profile it looks like this will be your first contest.

this will be My first contest but My last Summer contest , ok ?

Oh My God :) , are You sure this contest your first contest? But I think this contest is your first contest by fake Account

I am no longer scared of fake contestants. If my rating goes down, its because I suck, and not because of anyone else.

Yes the sucker man!!!

Lol

Get better than their main accounts and take their real rating as revenge!

Hello my friends ;)

Check the 1st version of his comment . He called everyone b*****s >_<

It was just a typo my friend ;)

Ugh!!! Don't you just hate it when you write "friends" and codeforces autocorrect changes it to "b*****s" ? :p

Scoring will be 500-1000-1500-2000-2500?

no

In my whole country adsl is down. I'll be solving this contest on mobile net :)

750 points for div2 A :| from where that it cant be very nice i think it will be a long boring brute force :(

This can also mean difficulty of A,B,C is not necessarily in that order.

Why doesn't codeforces allow a little bigger hack files? There are solutions that will get time limit exceeded when the constraints are used but the files are bigger than 256 KB.

You must write a test generator

There's only field for writing the test case, right?

In such case, you should write test-case generator.

my best contest eve :D I_love_321_&_taylor_&_hiro_hamda

MLE on pretest 1 in D :(

What for the sake of God is wrong with pretest 9 Div 2 C?

Isn't it finding the longest non zero subsequence from an arbitrary vertex

`I`

with no childs?i believe there was situation when parent has larger index than a child

Damn, should have thought about this. I shall try after the system testing.

I don't know maybe my approach is wrong but I run DFS to see if we can reach at leaf without consecutive vertices's containing cat or not and add it to the result! But my code was failing on test case 8 and 9

My code was failing on test case 8 This code http://paste.ubuntu.com/12523672/ and after swapping the index of the x and y when x > y My code failed on test case 9 http://paste.ubuntu.com/12523669/

just add an extra line:

to:

and I don't know what the

`if statment`

while reading really does!!My wrong assumption — If 1 is leaf, don't count it in answer. I kept counting it and kept getting failed submissions.

How can 1 be leaf when 1 is root and n>2

1-2 2-3 3-4 3-5

1 is root and a leaf(in a way)

How is 1 a lead in a way? I has 2 for a child

Draw it on a paper, ad see for yourself. Clearly, assuming 1 to be leaf was wrong n this problem, but not in general, when the tree is unrooted. That's why it was failing.

Leaf is a node with no child. 1 has a child 2. Seems like you got bit confused about leaf.

I suppose yes. I used the condition 'only 1 adjacent node' to identify leaf.

How can 1 be leaf when 1 is root and n>=2

I had WA on pretest 8.

A lot of pretests, yet smooth system testing and no issues. Really nice contest.

How to solve E problem?

It was so interesting.

I passed pretests with hashes + segment tree for updating hash value in a range.

Segment + Hash

I pass the pretests by compressing all values to bits.

I thought about this and hashing also, but I couldn't figure out a way to check the query correctness except by iterating on each block and check if the hashes/bits equal.

How to do this part quickly?

String s[l, r] has period d if s[l, r-d] = s[l+d, r]. You can get the hash of a substring with a segment tree.

I feel so stupid right now ._.

That's brilliant, I've never seen this trick before.

Except when d = r — l + 1. Nice observation though :)

I get TLE after system test. XD

In my room, MrDindows successfully solve it by treating all character as long long. You can refer his code: http://codeforces.com/contest/580/submission/13165100

Hey, can you explain his code. He is using memset and that is O(n) if I am not wrong. His solution seems to be O(n) per query.

You can find many information about memset from Internet.

Lets ignore the memset part. His query is still O(n).

He do some thing to speed up the constant part of his algorithm such as treat character as long long and expand the while loop.

I guess these changes of code will make CPU execute lesser command. (I'm not familiar with the detail, but I know these are common trick to speed up your code.)

How to deal with cyclic dependcy in D ?

Since the constraints are small, it can be solved by dp + bitmasks.

Does anyone have any ideas how to solve Div2E

withoutusing hashing?Ignore... It's wrong.

Why lcm(

next_{ k1}, $next_{k2}Unable to parse markup [type=CF_TEX]

) |d?What do your

k_{ i}means?Sorry, I just figured out it's wrong.

how to solve E ?

Pretest 9th for C ?

Maybe here

I was unable to submit in the last 60 seconds because codeforces was too busy. I hate it when that happens.

And I was unable to hack in the last 60 seconds.

Same here :/ I tried to hack in the last 20 seconds, but the challenge wasn't submitted.

same as your problem :|

solved D but It didn't submited, also in previous contests I have this problem too!!!

same here...

Блин решил последние две задачи а кодфорцез затупил и я не сумел послать(((((((((( уверен, это дело рук красных они бояться конкурентов и поэтому зажимают F5 на последних минутах и кодфорса ломаеца.

предлагаю ограничивать красным доступ на сайт на время контестов.I don't like problem scores!!! u think difference between problem C (or B) and D should be ONLY 500 (or 750).than it's same to solve A+B instead of D. May be my fault coz I solved only A,C,D(coz of not enough time),but anyway I don't think that this correct: man who solved first 3 problem is in front of me in list... D is much harder than A+B+C -_- sorry for my open mind

What's the problem with code generated tests ? I've got this one:

Thanks in advance.

validator wants '\n' in the end of a test.

Check this out.

Your test has extra space

Error: space is in the end of the second line.

It's correct:

Thanks, guys. That's just hilarious ;-(.

Is there anything need to pay attention to in the C problem? I failed to pass the 8th test and i can't find any mistakes.

Me too. :(

I just see the test data and I found it was because I wrongly think xi and yi in input mean xi is yi's father node.

You assumed given graph(tree) to be directed.

Can someone suggest an approach for 2nd? I basically sorted the friends based on their money, and I was then going to group friends based on the condition and sum their friendship factor, and check which group has the most. Is there a better way to do it? or any flaw in my solution.

Even I did the same ... KC3 hacked my solution.

It was a TLE. Used Binary Search but did not store the factor sum values. took the sum linearly everytime.TLE. haha.

you can read about the two pointer technique , and try solving the problem.

Firstly,sort the friends based on their money.Then,enumerate every element in array and use the function "lower_bound" to find the first element which is bigger than the it.And use the sum of factor between the two element to update your answer

1) sort based on money

2) find prefix sums for friendship factors

3) for i=1 to n

a) use any O(log n) mechanism to find index j such that money[j]>=money[i]+d ... I used c++ map for this.

b) ans = max (ans,prefix_sum[j-1]-prefix_sum[i-1])

I had the same solution. Used

`std::lower_bound(a + i, a + n, a[i] + d)`

to find the least index ahead of`i`

which I can not select, if I select`i`

.Index j is also invalid so why are you doing prefix_sum[j-1] and not prefix_sum[j] ?

Am assuming that i > j as we are considering the ith element and the old set if in [0..i-1]

Assume your set starts from i. We have sorted in ascending order of money so j>i because j is the lowest index you need to exclude if the set starts from i such that money[j]>=money[i] + d ... you can set money [n+1] = INF ... Include all elements from i to j-1 in current set and to get the sum of friendship factors of such ranges/sets of in O(1), I pre-calculated prefix sums. To get sum of elements from i to j-1, you need to subtract prefix[i-1] from prefix[j-1].

thank you ..

Sort + Two Pointers O(nlogn)

I used Two Pointers + Partial Sums. O(nlogn) http://codeforces.com/contest/580/submission/13170675

Can someone explain D soln ?

I solved it by DP, take a d[n][2^n] array,where d[i][j] means what is the best answer when last dish is i and j represents which dish I tasted before it,(1 means tasted,0 not tasted)

dp[mask][j] — best answer if we finish eating at j — dish, and ate all dishes in mask. O(n^2 * 2^n)

constrains of n & m are small. I think it can be solved using recursion trying all possible ways.

UPD: it will pass only by using memoization..

That would be about N!-(N-M)!, which is too much.

Aren't all possible cases O( P(n,m) ) ? (Which should be too high for recursion)

I'm sorry for this. I updated it.

and here's my solution: http://codeforces.com/contest/580/submission/13170384

Well, I think it is almost the same as the Traveling Salesman Problem

You have a graph, where the dishes are the nodes and the eating rules are the edges

dp[y][bit_mask]:

y is the last node you visited (dish you ate)

bit_mask is bit mask in which if the Nth bit is set it means that somewhere along the path you visited node N (ate dish N)

so

dp[y][bit_mask] = max (dp[x][bit_mask — (1 << y)] + eating_rule[x][y] + a[y])

if there isn't a eating rule between x and y than eating_rule[x][y] should be zero

so your final answer is the best dp[y][bit_mask] where bit_mask contains exactly M ones

you have N * 2 ^ N states and the you need O(N) for each, so total complexity is O (N^2 * 2^N)

Used same idea, got AC in Practice. Link to Code

Went out and could not fully participate in contest. Too bad!!!.

My thinking of how to solve Div2 B.(not sure if its correct)

Suppose we have <n=k people already to be a company. They are K-1 of them in number.

Consider the Kth person.

Case 1 : He should be in company. This is only possible if this amount is a < S[0].a That is it is smaller than the amount of the smallest person in the group.

Case 2: His amount is bigger.

In this case, we can use binary search to find a range of numbers that conflict with the Kth person, we sum the total factors of this said group.

We have to choose between the whole group and the Kth person. Which ever increases the overall amount.

Please would this have solved the problem???

I got AC using this approach

OMG!!!, I can't believe i just threw away my chance of turning blue today. Oh well, i'm happy i got the approach at least. Lets wait for the next round.

Thanks for the reply Expert Katalonecfly.

Can anyone explain me why this 13153912 got hacked?

Oh got it TLE. :(

Can't wait to see the rating change!!!

good picture

were the test case for 2nd question weak because i used upper_bound instead of lower_bound in hurry and i got AC? :P

I used upper_bound in one failed submission. You're lucky :)

I know why it passed coz i upper_bound on make_pair(curr+d,0). If instead of 0 it would have been a greater value it would not have passed. Yes I was lucky, coz i did not see that through.

PS : the test cases weren't weak then i guess.

The test cases were not weak, but solutions that did not consider test cases similar to yours passed. Overall, the solution is still correct and adding these test cases would've made the problem unnecessarily tricky.

I have this idea for D. Please tell me if you find something wrong in it.

Is it correct to start from leaf nodes?

I don't know if it's correct but it's an overkill.

Ok ;_; . I'll look at the editorial then.

It is dp with masks. State is last eaten and bitmask of eaten so far. To solve a state you try to fix the next to be eaten.

What's the Problem With my Code?? http://codeforces.com/contest/580/submission/13165400

Oh my god, i have disastrous bugs :'( i will cry in the bathroom.

I assumed that input was (parent, child) on C!!! ... silly mistake.

I agree with everything above and

confirm that I will provide my own problemsJust a quote regarding D.

How can we solve problem B if every friend was associated with hia own value of 'd', the value that makes him feel poor.

Sort + fast search algorithm.

Here!

So if you fix a[i] as being the biggest of sums,you need to add all a[j]<a[i] that a[j]+d[j]>a[i].

This can be done with fenwick tree,at position a[j]+d[j] you add factor[j].

And for i the answer is query per range [a[i]+1,limit]

Or linear parsing, with two pointers

http://codeforces.com/contest/580/submission/13150523

Nice problem

( E — Kefa and Watch ). I found a solution using hashing + segment tree, but couldn't solve it in time. BTW is there any solution without using hashing?In problem C, I'm having a bit of a problem determining the leaves of the tree.Assuming the tree is directed, In pretest 9, there are edge connections from 9 vertices to other ones and the answer is 7. So apparently there are 7 leaves. A lot of the people have considered an undirected graph. How do I find the leaves? I keep failing on pretest 9

Leaves can have only one node in their adjacency list. And when you do dfs (starting from the root of the tree, which is always node №1), this only node must be already marked as visited.

Yes I did that and it passed (BFS). Also, in contrast to the above comments, 1 will NOT be taken as a leaf in any case. If you do, you fail on pretest 3 atleast acc to my logic.

(http://codeforces.com/contest/580/submission/13174699)

kuldeepfouzdar nice trick for

Unsuccessful hacking attemptson your solution, in the problem B:`#define int long long`

http://codeforces.com/contest/580/submission/13163755

Hello all,

I have a question about an unsuccessful hack that I did during the contest. I hacked the following submission as I noticed that the numbers of the sequence are stored in indices of an array starting from 1 to n. The array is of size n and hence I expected that the hack will result in run time error due to the index overflow for a large input where the size of the sequence is 10^5.

Can anybody explain to me why did the hack fail? I expect it might have something to do with the unused array f but I am not sure about it.

C++ doesn't have index overflow run time errors, all that happens is that it accesses memory outside the array and as long as said memory is not used for something else it will pass.

How come 300 div2 participants managed to solve D? In my opinion it was a pretty hard dynamic programming problem.

Really ? I think that's the basic form of bitmask dynamic programming though

Basic bitmask would not have arbitrary transition rules, most in div 2 fails at problems like this. I think its strange that it was solved by as many div 2 participants as this problem which is much easier:

http://codeforces.com/contest/574/problem/D

This problem is also easier and was solved by just 100 div 2 participants:

http://codeforces.com/problemset/problem/540/D

So I'm just wondering: what makes this problem easy?

Rather than "easier", I would say it is more well known

IMO, one of the most basic problem for bitmask DP is finding shortest path to travel through all vertices in the graph which is completely the same as 574D, except that the answer lie only in status

`2^n - 1`

P/s : this is the first bitmask DP problem I learned so it can be just me

UPD:I've seen some tutorials about bitmask DP (just google search, you'll find them) use above problem as sample to solve so it should be well knownAh, I see! Thanks! I had just seen it for things like edit distance and knapsack and those are way easier.

Future div1 participiant ;)

Good job, there is no way I could have solved that when I was in div 2!

Stand-up contest)

Really nice contest, can't wait for your next one.

When will the solutions be uploaded?

There are solutions in the editorial=)

so many O(m(n+k)) solutions passed E 13198157

Hello! Has somebody managed to get AC for problem D, using reccursion? I can't. I get tle on test 26 :(.

In Problem B, I think it should be "Print the maximum total friendship

factorthat can be reached." in the Output statement.