Hello Codeforces!

I'm glad to announce that on Feb/07/2017 17:05 UTC Codeforces Round #396 for the second division will take place. As usual, First division participants can take part out of competition.

This round was prepared by me and mohammedehab2002.

I'd like to thank moaz123 for helping us prepare the round, zoooma13 for testing some problems, KAN for helping us in contest preparation and for translating the statements into Russian and MikeMirzayanov for the great Codeforces and Polygon platforms.

You will be given 5 problems and 2 hours to solve them.

The scoring distribution will be announced later.

**UPD 500-1000-1500-2000-2500**

**UPD** editorial is ready

**UPD** Congratulations to the winners!

Div1+Div2:

Div2:

A true Codeforces fan can not scroll down without upvoting this comment .

*without downvoting this comment

## Первый выпуск моего стэндапа

Уже доступен

MikeMirzayanov mahmoudbadawy There is a bug with registration. Div1 users cant register unofficially.

Sorry, please try again now.

Hope to be a good round. Good luck to all participants.

you don't need to say "good luck" buddy. coz good luck is not related to contest anywhere

coz luck is not rated)

I don't know man... sometimes when the site doesn't lag at all I feel pretty lucky...

The email says the round will have 6 problems, but the post says 5. Which one is it?

They are 5 problems.

That's FlapJack not Chowder.

is this the 1st Arabic official round on CF ??

No, round #67 was written by ahmed_aly: Codeforces Beta Round #67 (Div. 2)

problems are really good

Amrmahmoud also prepared Codeforces Round #287 (Div. 2) and Codeforces Round #312 (Div. 2)

That's Great , one day we will have a round prepared by us

Actually in Syria we have some great problem seters, they should have prepared a round here long time ago :D

Is it rated??

There's always that one guy who asks this question.

mohammedehab2002 shares a name with an Egyptian weightlifting superstar. Guessing not the same guy but would be cool if so.

short blog :) I love it

Don't have character?

I think it might be president Elsissi :P

Copy Codeforces testcases by clicking on them :O

An extension for chrome only Installation: Download from https://drive.google.com/file/d/0B4HQVLPL4OXRUHJNa0dnQkNYNzA/view

you can see GIF https://media.giphy.com/media/26xBNH5TzjX0z90R2/giphy.gif

Go to "chrome://extensions/" Drag and drop the file into the page

Good Luck And Have Fun <3

Thank you :(

Here's to clever yet easy problems! Hoping to become candidate master finally...

Your new rating is determined by your contest rank.

Fast and accurate wins the race.

Rating != Knowledge

Even newbies can think of a beautiful problem, which can be challenging for masters!

@VoR_ZaKon : All I wanted to say was that rating doesn't defines one's thinking ability.

PS — He deleted his comment. His comment was — "Ok then I am better than tourist".

He is banned (his comments and posts deleted automaticly). LOL :D

Prepare by pupil?

Prepared by a specialist and Candidate Master

I have short.

I think there were a lot of replys 5 minutes ago..

UPD: I think admin deleted them.

the new contetst with specialist builder. this contest will be nice

New authors often surprise CodeForces community (in good way)... Trust on interesting contest, good luck to all!)

New contest, new opportunities to learn and possibly get better. Thank you CodeForces

What a stupid contest

why do you think so?

problem D and E are old problems

how did you solve E ?

Where did you see problem E before? I have seen it in a way that you are given weights for the edges but I have never seen it with weights for the vertices. And the solution for the "edge" version is different than the one for this problem.

Solve the problem considering the weight on the edges and the starting distance is a[centroid]. Now you need to invert the bits that appear on a[centroid] because if the path goes throught it, you will count it twice. Do that and then the rest is identical.

already got these hackers

belive it or not, this was the worst contest I have ever seen

Maybe your worst result ever ;)

Should I say something or you know what I'm thinking about ?

Come on :)

I was just kidding!

Cool :)

E was a genuinely interesting problem IMHO. ABD were around the average, C was way too tedious. This may not be the best contest, but there is no way I could call this the worst contest ever.

C wasn't tedious(if what I did was correct). The second part of C was a simple for loop, and the first and third parts were n^2 DP.

I did the same as you, but honestly I found that writing essentially three solutions was quite annoying. Maybe tedious is an overstatement.

Maybe they intended the problem to look difficult.

I'll just leave this here...

now, may I'll see legendary newbie rate !

Hi! I'm working on rating calculation tool. It's close to be ready! You could find this contest's rating prediction here. I hope chrome extension would be ready till next contest.

Awesome, I love it :)

Good job!

Nice. But I think I will just use the page instead of the extension. Thank you for this.

For me, it doesn't seem to be working? It says I got rank as 291 when I got 99th place, and predicts rating decrease even though seed is 620?

It's because server isn't so powerful to process changes just in time. Your rank and rating will change soon:)

It seems you are going well!

By checking a few random contestants, I found that the predicted rating changes and real rating changes are always differ by 5.

It would be awesome if this difference could be fixed as well :D Maybe it's something related to the unrated contestants? (Not sure)

Can't wait to see the accuracy of your updated hardwork!

Thank you! I will try to fix this)

In B, we can write O(n^2) because maximum value of n for which answer is NO is ~90 ?

You can sort and itertate through in B.

I tried to find a hack test case for O(n ^ 3) and O(n ^ 2) solutions.. :D

For O(n^3) use the first let's say 10 fibonacci numbers and then their multiples For example 100000 1 1 2 3 5 8 13 21 34 55 110 165 220 275 330 385 etc

Hm. I think this test case is wrong because "220 275 330" are valid sides

The guy that I hacked checked if (v[ 1 ],v[ 2 ],v[ 3 ]) from a triangle, then(v[ 1 ],v[ 2 ],v[ 4 ])... then( v[ 2 ],v[ 3 ],v[ 4 ]) and so on, so on this test it gets TLE

Oooh. ok)

Have you proven that the maximum value is 90? Cause I was thinking for half an hour for a test that O(n^2) doesn't work for it but I couldn't come up with anything.

The smallest test case of answer "NO" is the fibonacci sequence. So if N >= 45, it is always possible to make a triangle.

Let's make sorted array with the answer "NO"

1 1 2 3 5 ...

Fibonacci numbers!

ai <= 1e9, so n with an answer "NO" has to be small

Yep, it is easy to prove that maximum value is less than 100.

To build a correct triangle you need 3 values , lets say its a<=b<=c

If a+b>c triangle can be build, then if we want to create maximum sequence of numbers that cant result in triangle we have to create something like fibbonacci sequence. t[i]=t[i-1]+t[i-2]

You can look up at fibbonacci and see that 70th or 80th(i dont know exactly) is already bigger than 10^9.

Then, if n>100 pritf yes, otherwise use O(n^3) algorithm

How to solve problem D? I could think of an approach using 2 dsu's. but did'nt code

I used 1 dsu and an additional array of antonyms (if i-th and j-th sets are antonymical, ant[i]=j and ant[j] = i).

You just have to update the sets_merge operation to handle antonyms: if you merge a and b, ant[a] and ant[b] should also be merged.

how update and handle sets in this case?

you have to think this way:

2 strings are synonims.you do a union operation on them.but what happends if one of them or both have an antonym?

if they both have one,you unite their antonyms.if only one has,you make sure that the root knows who's that antonym. if they are antonyms you update the antonyms array.but,there are again subcases

let's say the words are a and b if a had an antonym,then b and ant[a] are synonyms,so you unite them if b had an antonym,then a and ant[b] are synonims. again,be carefull that the root always knows who is his antonym

Yes it can be solved using dsu, you just need to color the verticles (the words) and find the answer for each query

You can use 2 nodes for a single node. The new graph will have 2*N nodes. For synonyms, add edge between (u,v) and (u', v'). For antonyms, add edge between (u, v') and (v, u'). Use DSU.

Can someone explain C? I thought it was DP but I couldn't figure out how to put it together.

lets say string is from i to j then, for(k=i;k<=j;k++) { if(i,k is a valid substring ) dp[i][j]+=(dp[k+1][j]); }

You are right, it was a DP indeed :)

to calculate number of ways to split the substring(l,r) you have to choose the leftmost splitter i starting from l until it violates the conditions mentioned or reach r. after choosing leftmost splitter i you have to find number of ways to split substring (i+1,r) and add it with the result

Yes, it's DP. I used two functions: 1) Number of different partitions of prefix with length i when rightmost word has length j 2) Minimum number of words in partitions of prefix with length i when rightmost word has length j

Let dp[i] denote the number of ways to split the substring[0,i) in a valid manner. Then the answer is obviously dp[n]. We have base case dp[0] = 1. Then dp[i] += dp[j]%MOD if substring(j,i] is valid for 0 <= j < i. You can think of it as dp-ing on the possible spots to cut the string. Question 2 and 3 can be answered by updating along the way.

I loved D. Thanks for a great contest.

Lost a lot of points on C, because I thought there should be at least one cut :/

with 10 more minutes I would have finished debugging D and solved all problems. :(

contest is much easier than usual

Can you tell me the idea behind E, please?

I used centroid decomposition to solve E

I suppose it shouldn't fit to TL (because it O(N*logN*logMaxA))

UPD. Yes, you got TL14. The correct solution (dp on tree for each bit) doesn't use centroid decomposition and has O(N*logMaxA) complexity.

Yeah you are right i got TLE :(

Hmm... I solved it using centroid decomposition and it passed just fine.

Perform DP for each bit counting the ways with xor = 1 and xor = 0.

Root the tree at an arbitrary vertex. Let's calculate the answer for all bits separately.

For each vertex u calculate the number of pairs (u, v), where v is some vertex in the subtree of u so that the path weight for that bit is 1, and also so that the path weight is 0. This can be done through dynamic programming.

Handling paths (u, w) that pass through v (so that v != u and v != w) can be done through iterating through the children of v.

I could not understand your approach. Can you elaborate a little please.

For each bit i, assign value node u = bit i-th of a[u]. The problem become: Count number of path in tree that have odd number of 1. Then we multify it with 2^i.

Although I agree with u based on D and E, C was better than usual. Just check out round #394, C was a cakewalk.

Awesome problemset! Devoted my whole time in solving E but couldn't. If there would have been integers attached with edges instead of nodes then it was quite easily solvable but this little twist made the contest complete fun for me. Thanks !

A Problem copied? where?

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1099

Can someone give an idea for D?

While adding pairs, you can use disjoint-set union to see if the words are already associated with the same meaning (be it antonymous or synonymous). Ignore those edges when adding them. Run DFS for each component, coloring its synonyms white and antonyms black. Then you can answer the queries (of both kind)

Problem D is here Link However without the part of answering some queries on relations.

And here is E :P

I'm also pretty sure B is somewhere online

Second POI.

B is a simpler version of this https://www.codechef.com/FEB17/problems/MAKETRI

That's like saying A is a simpler version of the KMP algorithm...

This is B https://open.kattis.com/problems/stickysituation

It is different from E which has weights on vertices, not on edges.

The solution would still be the same.

Can you please explain how we can derive solution for weight on nodes. I had a solution with dfs and components counting if there were weights on edges. How to convert that in this problem ?

Just consider the given graph is a rooted tree, and the weight of node

`i`

,`a[i]`

, can be transformed into the weight of the edge between`i`

and the parent of`i`

.While calculation the answer with DFS, just don't forget to special handle the current node. We should also add the weight of the current node

`cur`

,`a[cur]`

to the cost of the paths passing through node`cur`

.You have to deal with every bit alone. Dfs from the root and calculate the value of the bit i on the path from the root to each node.

Now you only need the number of ones and the number of zeros in each subtree. You can combine the answers from different subtrees as for each two nodes the path length will be pathfromroot[x] ^ pathfromroot[y] ^ val[lca]

There is only 2 outputs for each bit depending on the value of val[lca] so it can be calculated easily

Just a couple of minutes more and I would've solved D. It's nice to spend the entire contest on C and realize that D is solvable when you have only 15 mins left... Thanks for the contest, anyway.

Can i see some hack cases for 'A' that you people used. I tried hacking, but failed. Thanks

I could only hack one submission that returned -1 when one string contained the other, so my hack case was: aaaa aa

+1

24496013

+1

For problem B, what should be the hack case for O(n^3) solution which didn't use sorting?

Update: This is a hack case for O(n^3): 100000 1 2 3 4 5 6 7 8 9 .......... 100000

100000 1 1 2 3 5 8 13 21 34 55 110 165 220 275 330 385 etc

In this way, the value won't fit in integer and will be > 10^9, so I think this won't work.

How would the values exceed 10

^{9}?The elements excluding the first nine are all multiples of 55, and so the last element in this list would be 55 × (10

^{5}- 9) = 5499505 < 10^{9}The 44'th number of this sequence ( i.e. 1 1 2 3 5 8 13 ......) is 1134903170 which is > 10^9

Dude, read it until the end.

Didn't you notice the sequence Flavius mentioned is not simply Fibonacci sequence? It is not a Fibonacci sequence starting from 55. So the 44th element of that sequence is not exceeding 10

^{9}, it is just 55 × (44 - 9) = 1925.I hope you can read carefully next time :)

220 275 330 form a Valid Triangle.

But the simplest

O(N^{3}) nested loop will still iterate long time through the first few elements until it finds the first valid triangle.In cases that the logic is similar to the above code,

`i`

iterates from 1 to 10 but still can't find any solution. Each iteration of`i`

takesO(N^{2}) as it will still check for all possiblejandkthati<j<k. In other words, the code will TLE before finding a valid triangle.BTW, the first valid triangle should be 110, 165 and 220

The sequence overflows after 43 terms. For O(N^3) solutions, the hack used can be any sequence with 100000 terms and the first term as 1: 100000 1 2 3 4 5 6 ...

since for i=1, the loop runs O(n^2) times and we get NO for all cases, this will give TLE.

Is it really hard to notice that the sequence is not just simply Fibonacci sequence?

Sorry. My bad.

There isn't, with more than 45 elements it's always possible and O(n^3) obviously works for n = 45 http://codeforces.com/blog/entry/50280?#comment-342293

O(n^3) solution got TLE on test case 33

Test 33 is abcd abc, so I'm guessing there was a bugged while instead of 3 fors

edit: disregard this comment, wrong problem

You are talking about problem A, while were talking about problem B.

Sorry, my mistake. Problem B's case 33 are just numbers from 1 to 10^5, so by checking in O(n^3) the first 45 numbers the solution (2, 3, 4) will show up

and

correct answers: YES | YES

Edit: these are tests with which I generally hacked some B codes. Misread your comment a bit... O(n^3) might not be hackable, since for n approx. >100 the code should always say "YES". See discussion few posts up about Fibonacci Sequence.

O(n^3) solution will also give AC output for your inputs.

But have you seen that in system test, O(n^3) solution got TLE on test case 33 ?

I tried to hack Atai solution for n=10000 with input as 1,2,3,4..........10000 but it showed unsuccessful.. But the same sol... is showing tle for test case 33 system test... how is my hack solution passing and system test failing... failed system soln http://codeforces.com/contest/766/submission/24500965 passed hack soln http://codeforces.com/contest/766/hacks/296935/test

You unfortunately forgot to add an extra zero. The max input size is 10^5, where your hack is only 10^4.

it was n^3 soln if it failed at 100000 it will also fail at 10000

The reason is he selects 1 as his first side length, and then selects 2, and then iterates from 3-10^4 to find a valid length but fails. He then switches his second leg to be 3, and iterates third leg from 4-10^4. You see this will continue until he selects 2 as his first leg.Here, he will immediately find a triangle (2,3,4).

This process is n^2 for this test case (because of the early break case). If you would have used 10^5, he would have done (10^5)^2, which is 10^10 and then he would have TLE'd. Sorry, bad luck.

100000 1 1000 10004 10006 10008 10010 10012 10014 10016 10018 10020 10022...

How can this user, r_clover, solve both problem B and D within a minute?

Wrote code for B, forgot submitting, then wrote code for D, submitted D, realized he had forgotten submitting B and submitted B.

Exactly ! and the funny thing is that took him 4 mins to solve A and 7 mins for both A and D ...

Coding styles are different too... He was not alone :)...

His results/submissions have disappeared

In the same way as you did here and got disqualified :

S for

SAVAGEProblems are good i think...i hope there would be a chance today...

guys is that site is true ?! http://cfpredictor.us-west-2.elasticbeanstalk.com/roundResults.jsp?contestId=766

So, Codeforces started copying problem from UVa :\ :\ :P

That moment when you failed both C and E only because of wrong answer on n = 1 case...

Did anyone else failed system test on test 22 on problem C.

Thanks for this good contest .

I really like these problems.

Why codeforces div2 contests are becoming easy?

Maybe you're getting better?

E div2 in 'div1+div2 rounds', are harder than E div2 in 'only div2 rounds'...

But it shouldn't be!

div2 only contests should be interesting for div1 users too.

What's the problem with it?

Solving hard problems makes you strong.

AB should be easy because before solving harder problems (CDE) we have to solve easier problems first.

That's true for a d1,but it isn't true for d2,so i don't think it is a big problem since the round is destinated only for d2.

guys this guy i tried to hack his code for A

by test case

abc xyz

but it's weird that it was unsuccessful attempt ?

his code :

s=input() t=input() if s in t: if len(s)==len(t): print(-1) else: print (abs(len(s)-len(t))) elif t in s: if len(s)==len(t): print(-1) else: print (abs(len(s)-len(t)))

else: if len(s) > len(t): print(len(s)) else: print(len(t))

The code works perfectly for your case. It is because your case belongs to the third condition (the

`else:`

line)As

`if s in t:`

in Python means checking if the stringsis a substring oft, while in your case,`abc`

is not a substring of`xyz`

, so`s in t`

returns`FALSE`

in your case. And same for the`t in s`

condition as well.As a result, the code goes here:

And thus, print

`3`

as the output, which is the correct answer.Interesting thing about problem B is that stupid solution which uses random works fine and passes all tests. Solution: 24513380

It's not so stupid. If n > 50 then you can always find such triangle so chance of finding one randomly is high. In other hand when n <= 50, randoming is pretty much like using n^3 brute force, so as I said it's not a dumb solution.

Div2 C, rip to all of those who got WA on test 36

Will be editorial?

It's already here: link

I implemented B in a little bit bad way, I used 3 for loops but the third one is redundant then also time complexity of my solution is O(n^2). After locking and seeing other solutions I thought that my solution can be hacked by giving tle but it indeed passed the system testing. But by intuition it was clear that finding such a test case was difficult, so I wanted to know whether it is possible to hack my solution with certain sequence or not ? and how did it passed the system test . http://codeforces.com/contest/766/submission/24497421

check the editorial and you will understand why O(n^3) passed system test

I got time run exception for solution of second qn written in python. after rewriting it in C++; It I passed it. What does it mean?

It means python is slow

see it for more information

Good round. Where I can find a tutorial of these tasks for training?

I'm sorry I have found — http://codeforces.com/blog/entry/50294

I know I'm a little late, I had to work yesterday :(

Problem D is exactly this problem (with different input/output format obviously)

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1099

I have calculated the complexity the code to be NlogN*maxl +MlogN*maxl+2*Mlog+N*logN+Q similar to the question authors (N+M+Q)logN*maxL, but getting TLE on test 13 please somebody can review my code. I know I havn't run the dfs from root node but this should pass too. please help!

http://ideone.com/EhwB7S

who can solve this problem http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=3092&run_id=249r32910#1

FIRST TRAVERSE WHOLE ARRAY ANF FIND SUM

IF(SUM IS ODD) RETURN -1;

THEN USE DP FOR SIZE=N/2 AND TOTAL=SUM

DP[SIZE][TOTAL]=DP[SIZE-1][TOTAL] || ( DP[SIZE-1][TOTAL-Arr[i]] for all i )

RETURN DP[N/2][SUM];

Can you send the code

I don't understand

Hey guys. How to solve E? I can't get this prob.