Привет Codeforces!
Рад сообщить вам, что 7-го февраля 2017 в 20:05 МСК пройдет Codeforces Round #396 для участников из второго дивизиона. Как всегда, участники из первого дивизиона могут принять участие вне конкурса.
Раунд подготовлен мной и mohammedehab2002.
Хочу поблагодарить moaz123 за помощь в подготовке, zoooma13 за тестирование некоторых задач, KAN за помощь в подготовке раунда и за перевод условий на русский язык и MikeMirzayanov за прекрасные платформы Codeforces и Polygon.
Вам будут даны 5 задач и 2 часа на их решение.
Разбалловка будет объявлена позже.
UPD 500-1000-1500-2000-2500
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
RetiredAmrMahmoud 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
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
Here's to clever yet easy problems! Hoping to become candidate master finally...
Your new rating is determined by your contest rank.
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.
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.
Hi can you mention the link of the problem which given weights are for the edges ? I'd like to practice on that one too. Thanks
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:)
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 betweeniand the parent ofi.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 nodecur.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
24496013
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 109?
The elements excluding the first nine are all multiples of 55, and so the last element in this list would be 55 × (105 - 9) = 5499505 < 109
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 109, 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(N3) 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,
iiterates from 1 to 10 but still can't find any solution. Each iteration ofitakes O(N2) as it will still check for all possible j and k that i < 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.net/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.net/contest/766/submission/24500965 passed hack soln http://codeforces.net/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?
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 SAVAGE
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
ОБРАТИТЕ ВНИМАНИЕ
Я хотел смешно пошутить, но нашёл кое-что, что меня возмутило. По этой ссылке вы можете увидеть, как человек опубликовал своё решение по одной из задач 108 минут назад, то есть прямо во время контеста. Думаю, его следует наказать. Ставьте ПЛЮСИКИ, подписывайтесь на мой блог. UPD Его забанили, всё хорошо, спасибо
аха, еще чего!
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 string s is a substring of t, while in your case,abcis not a substring ofxyz, sos in treturnsFALSEin your case. And same for thet in scondition as well.As a result, the code goes here:
And thus, print
3as 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.net/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
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
Hey guys. How to solve E? I can't get this prob.