Hello, everyone! Codeforces Round #320 will be held at Sep/16/2015 18:00 MSK. Note that round starts in the unusual time!
The problems are from tmt514, Shik, drazil, and me(dreamoon_love_AA). Also we want to thank Zlobober for helping us preparing the round, AlexFetisov and winger for testing this round , Delinur for translating the statement into Russian, and MikeMirzayanov for Codeforces and Polygon.
This is my second time organizing a problemset for a Codeforces round (my previous round: #292). In my previous round all problems were provided by me. But I think that if problems are provided by more people, then the contest will be more interesting! So I asked my friends to help me this time. Hope everybody can have fun during the round!
Participants in each division will be given six tasks and two and a half hours for solving them (the last four problems in Div. 2 are as same as as the first four problems in Div. 1). Scoring system will be announced later closer to the start of the round.
Bayan is an Iranian software company working on large-scale web applications. It doesn't only develop the search engine, but also it holds an annual open competition Bayan Programming Contest with an on-site round in Tehran. The on-site round of 2015 became an international event with many strong participants.
Bayan has supported Codeforces on our Codeforces 5-year crowdfunding program. Thank you Bayan! This round is in your honor!
UPD 1: Due to technical reasons the round starts at 18:15 Moscow time.
UPD 2: The round will use the dynamic scoring with 250 points step.
UPD 3: Problems are ordered according to their supposed difficulty.
UPD 4: Winners!
Div1:
1) Um_nik
2) Egor
3) Endagorion
Div2:
1) EmaxxMaster
2) gongy
UPD5: link of Editorial
What about sorry_dreamoon ? :)
I am requesting his participation!
In this Comment , sorry_dreamoon said that "I'm not going to take part in CF rounds anymore."
I think, he/she will not participate.
He is the loser
Are you sure?
It's not all about high ratings.. I mean he will lose the joy.
Do you think that you're better?
He is not a loser, but maybe he is really sorry , because he got caught by Enchom :p
So does contest has 8 problems at all? 6 for Div2 and 6 for Div1?
Yes, I have modified the content of post for clarity.
Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).
EDIT: it's a bit strange for me. Isn't dreamoon_love_AA working for Bayan, is he?
Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).
I hope I can become violet back after this round.
I think it's a good place to ask, any news about Bayan T-shirts? As far as I remember they announced that T-shirts will be delivered after the final and that time is long gone.
As I know from Bayan persian blog (written 3 months ago) the t-shirts quality provided by manufacturer was not what Bayan expected (I mean it wasn't good as expected), So by their agreements (with manufacturer) they forced manufacturer to reproduce t-shirts and Bayan did apologize in the post and said that it takes time to produce t-shirts again. BTW 3 months has gone and nothing happened! :-)
here is the link of the post (you can use google translate if you want, that's not good enough, but at least helps!)
Bayan Story
It’s common that organisers fill empty spots if someone can’t come to onsite, so right after the Elimination Round I approached the organisers and asked them if they were going to consider inviting contestants that were down the list in this case. The response was….well, there was no response.
It came later as a surprise that 2 contestants who were ranked lower participated in the Finals. You would expect that in this event the organisers would treat this matter seriously and point out the reason for this. I raised this matter hoping to get a reasonable explanation…
By now no explanation has been provided by Bayan. I tried emailing them, sending personal message in Codeforces (more than once), asked question in Bayan blog posts on Codeforces, approached Egor directly (as he was writing a blog for Bayan), but he was unable to help either.
Unfortunately that still remains a mystery to me...
References: Previous Discussion, Elimination Round Results
More upvotes for this man, please!
Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).
Why every author announces score distribution just before contest? I really can't understand..
Zlobober don't think that it is important for participants to know score distribution early. The main goals for authors and coordinator in the day of the contest are to fix translated statements and double-check everything. When all of this done we can discuss score distriburion.
Moreover, I don't think that scoring should be published at all. Let me provide a link to my old comment to clarify my position.
In a few words: the scoring is a part of a problem as well as, for example, the number of sample tests or the number of letters in the statement: it is some information that can be used to predict some characteristics (difficulty or "prettiness") of round with pretty low reliability. Then why should we post it? I don't see a situation when by knowing scoring something can change (for example, if you decide if you want to participate or not by looking on scoring, then, erm, it's your business, but it sounds very strange to me).
In my opinion there is no need to post a scoring at all, but nonetheless there was such tradition before I became a coordinator, so we kept it.
This sentence causes some kind of confusion, it sounds as if you are talking on present round : "In the last round all problems are provided by me". Maybe this can be more clear: in my previous round all problems were provided by me.
Thank you for teaching me English. > _ <
Don't mention it. I just can't understand why community is giving negative feedback here :)
Private message is better for typos and correcting grammar. Why would hundreds of people want to read such a message?
Maybe you are right. Anyways, I had no offence in mind and it was just a suggestion :) Somehow I still believe that it's more valuable (to dreamoon for example) than 90 % of comments that I see here.
Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).
...
challenge problem
beautiful life
Damn... Round will start 17:00 CET. I break at 16:30, plus route to home. Why not 17:30? Damn...
Try to teleport to your home :)
Thank you, CF, for delaying the round! I believe it's just for me :D
Wow in the same moment :D
They made a 15-minute delay for you :).
How to unregister for the contest? I just registered for the contest and later realized I have other commitments, so cannot give the contest on time. Thanks!
Ignore that
Find yourself in registered list(it's easier to search among friends) and click red button
Go to contest page, then to list of participants (there is number of registrants now x3066) and find your nick on that list. There should be X button, click it.
It's good to unregister if you know you won't participate. Registration allows system to put users into rooms and we don't want some rooms to be almost empty, it would be unfair.
Thanks fellas, I was able to unregister
congrats!! -_-
What kind of problem involved neither maths nor algorithms?
Solvable problems.
Wish this contest will be suitable and thanks for preparing this CF round.
Is this a rated contest?
Ofcourse, yes!
thanks for unusuall time :))
sorry :_(
But... you love Taylor!
i love you too :D
what about scoring?
yess! Dreamoon contests ( math !)
The problems are from tmt514, shik, drazil, and me(dreamoon). Don't be so happy!!!
Delayed for 15 min :(
why added 15 min? :(
Note that round starts in the unusual time! :)
Decided not to go to two of my lecture to do CF round. Delayed again
Unless both those lectures are total 15 minutes long, you shouldn't complain.
Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).
Oh my god :) big Delay
Your right, it was a shock :P
15 min delay again
We know that contest is postponed so there is no need to announce it in comments (just for gaining upvotes) !
Hah!!! and you were expecting upvotes too!!! Ps. Please don't upvote as it will not increase ratings.
I wasn't expecting upvotes. I just shared my opinion.
Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).
Is it just me, or the older codeforces gets the more technical difficulties we have?
Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).
Is problems sorted by difficulty ? (from your point of view)
6994 combined registrants...
Just a little bit short of 7000!
Came home early, was looking for an interesting contest, but got math and bitwise operations instead.
Go away >_>... Problems were nice! I can't express how stupid I consider all those complaints about 'math problems'.
It also baffles me. In fact, for me, as long as you have to devise an algorithm to solve a problem, it is a math problem. Then, I don't even know why people who don't math problems are here, in first place.
That dynamic scoring though -_-
.o. He is the new dreamoon in a dreamoon contest.
I figured the logic of C 3 minutes before the end :(
And that is?
You make the tallest possible pyramid that has (a,b) on either leading slope or lagging slope. This gives you the base of the pyramid and then you keep dividing the base by 2 until the value>=b. If b>a, -1. if b==a then leading slope, else lagging slope.
I'm guessing base of pyramid is 2*x.
Can you give a small proof why dividing works..etc
Yes, so you just do this:
while(c > = b)c/=2;
This works because There exists a pyramid that will contain (a,b) if (a>=b) . This is an isosceles triangle. Two isosceles triangles can be made from this bigger triangle with bases base/2 each. Draw it on a paper and you will understand.
UPD: Sorry, I didn't make my point clear earlier, here is a bit updated version.
In absolutely any place in English statement of E there is written demand that history of footsteps has to be one that admits minimal number of backwards steps (nor it is even suggested). I think that only sane action now would be to change checker of E not checking if history printed by contestant minimizes number of backward steps.
"Alice wants to know the minimum possible number of backward steps made by a person."
"The first line should contain a number denoting the minimum number of backward steps."
Isn't it written explicitly?
Of course, it is written explicitly that first number of output should be minimal number of backwards steps, but that is not my point. My point is that in absolutely no place it is written that path outputted in second line has to admit that minimal number of backward steps.
It'd be strange to ask as a certificate for the answer an unoptimal sequence of steps, isn't it?
If you really considered this you should've noticed that outputting the first number and the second sequence are completely independent tasks (much easier than finding a certificate for an optimal answer). You probably wouldn't pass the sample tests or pretests. Also you could've sent us a clarification request.
Although it wasn't written formally that we don't need any sequence just admitting left-right alternation rule but an optimal one, but my opinion that this case is unambiguous under some common sence.
Of course common sense prompted to print path minimizing this, but what should count is not what I consider as sane, but what is written in statement. And I haven't passed even first pretest, but that is irrelevant to whether my point is valid.
I'm an asshole right now, but I'm the one who is right, you can treat my hypothetical AC as my reward for very careful reading statement and punishment for yourself for not paying appropriate attention to make statements correct :P.
From some point of view you are right. On the other hand, the rules should be introduced exactly till the moment they can't be fulfilled.
Unfortunately, it is impossible to write a 100%-correct statement and to use some real-life legend at the same time. There will always be some amount of people who understand it in wrong manner. The outcome of problem preparation and testing process is that several people (several contest authors, 2 testers and me) read that text and didn't find anything wrong. The informal argument is that verification by 4-5 people is close to the limit we can afford during the preparation process, so I can't guarantee that statements will usually be better.
But as a small reward for you, you are always welcome to volunteer as a tester and we'll be glad to fix all issues you find :)
Of course, we won't rejudge this task. Hence, I apologize for an inconvenience.
What do you mean?
" Alice wants to know the minimum possible number of backward steps made by a person. "
" The first line should contain a number denoting the minimum number of backward steps. "
Which test cases were used for hacking problem B div1?
4 1 2
1 8 10 4
answer is 31, but DP f(i, j) — max number if we r at prefix i and did j multiplies returns 29.
Let's add random_shuffle — 13043864 :D
Could you please explain why DP without random_shuffle is failing for this problem?
-Thanks
Test against dp solution:
3 1 8
18 17 10
or
3 1 8
18 17 10
why it's wrong to use dp?
Math Contest
how to solve Div 2 problem D "OR" game?
DP
I was suspecting this only... though I didn't gave up on my greedy soln till the end..
No
Try this test:
3 1 3 17 19 8
ignore
n = 3, k = 1, x = 3, a = [17, 19, 8]
Note the optimal solution is to use all your operations on a single entry. So you can check a[i] * x^k | pref[i-1] | suff[i+1] for all i in O(n) time.
how can you say that the optimal solution is use all operations on single entry?
Hint: 2 ^ i > (2 ^ 0 + 2 ^ 1 + ... + 2 ^ (i — 1))
What is an example where doing all operations on the largest entry doesn't give maximum OR ?
3 1 2
4 8 10
Thanks!
5 1 3
1 5 13 8 16
Here the answer is 63 (multiply 13 by 3). If you multiple 16 by 3, it will give you 61. This is the 32nd test.
Consider two numbers n1 and n2. Suppose n1 has strictly higher no of bits than n2. It's given x>=2. So multiplying n1 by x once increases the position of most significant bit in n1 by atleast 1. Instead if you multiply n2 by x, position of most significant bit in n2 may increase but when | (ored) with n1, position of most significant bit may not increase.
Since it's always better to maximise the position of most significant bit, we have to multiply n1 by x. In the next iteration (we have to multiply by x, k times), clearly n1 * x has more bits that n2, so we pick n1 again. So it's always better to multiply the same number with x.
Well my DP failed :(
I did exactly the same :) EDIT : I got all the 3 submissions accepted , rank 338 . So, happy :)
What is the counter-test for greedy solution of div1 E ?
Explain your greedy solution.
count number of L and number of R , if L is bigger than R then walk must start by L , same thing when R is bigger than L , in case of R eqaul to L , I try 2 possibilities
now if my last step is L , then I try to find nearest not taken R from right , otherwise increase number of backsteps by 1 then find first not taken R
same then when my last step is R
for the very first step I find the leftmost L or R
RRLLR
my code answering 2 (1 3 5 4 2) , is it wrong?
Correct answer is
1
1 3 2 4 5
thanks
Math Math Everywhere !!
Div 1 C, "Weakness and Poorness".
Main problem statement:
Determine a real number x such that the weakness of the sequence ... is as small as possible.
Output specification:
Output a real number denoting the minimum possible weakness of ...
Feedback:
It's a bad style when main problem statements has clear imperative "determine X", and only in the output format I read "by the way, the task is not to find X, but to find Y!"
Agree, that's our fault. Though, it doesn't really affect any of the solutions I know.
It does effect mine!
In my floating point solution, the error of x can be controlled easily and implicitly by setting the limit in binary search to 1e-6. Whereas the error of weakness is much more subtle and hard to control.
Same here, my C failed and I quickly realised I had set low limit to my binary search, because in my head I imagined we're looking for X.
Isn't it true that error of weakness can be controlled by setting the limit of binary search to 1e-6 / max_n > 1e-12 (because the function is a piecewise-linear convex function with absolute slope no higher than max_n)?
My question above is just a curiosity, I agree with that the statement that this place was written in a bad manner. I apologize for that.
Yes, pretty much. My solution with epsilon at 1e-6 failed (13037903), while my solution with 1e-11 passed (~1e-6 / 200000) (13052071).
I mean, I understand this is a little detail that I missed, but I'm a bit disappointed that I missed this problem only because of this precision problem, even though I got the general solution right.
Actually till today morning we asked for precision 1e-9 in this problem. With such precision it is almost impossible to solve this task with ternary search (but possible by some kind of convex-hull-like or halfplane-intersection-like solution). So I'd disagree that handling a precision is a little detail of the problem, as you tell. Sometimes precision may even fail a certain kind of solution, despite the fact they implement "general solution right".
Right, calling it a 'little detail' isn't entirely correct, but the fact that an error in x is blown up by up to a factor 1/n in the output is something that is not immediately obvious (or at least not to me).
The problem could have just asked for x, in which case the precision of 1e-6 would be more than sufficient (and there would be no error amplification in the output), but instead it explicitely asked for the weakness. To me this doesn't really make the problem more interesting or challenging. It just kills a bunch of solutions (like mine) that didn't consider the division by n.
But yea, I'm just a bit sour because my solution failed and I missed the points, I liked the problem in general. At least I'm still orange.
That's because they can check with the sample testcase, I lost a minute thinking I did sth wrong in the code
heeeeey Alex_2oo8 !
come on! it was my first div1 contest and you hacked my solution ! :(
you have got a heart of stone.haven't you? :D :P
So, he gave you chance to fix your solution instead of it surely fail system tests, no?
Yep.fair enough! :)
so, thank you Alex_2oo8. :D
Can anyone give me a hint for Div1.D, I tried DP but could not eliminate repetitions of the same string.
How to solve C ?
Let's introduce the function M(x) — the minimum sum in subsegments and m(x) — the maximum sum in subsegments. Then it is easy to note that these functions are monotonic in x. Further, it is obvious condition for a binary search — if abs(M(x)) > = abs(m(x)) than decrease x, else increase.
Pretest passed on Div 2 ABCDE, but got accepted on only D :'-(
Very nice contest, thank you dreamoon_love_AA
The idea for problem D has something familiar with problem Horses from IOI 2015.
in Div2 E Weakness and Poorness. how X is Calculated ?
ternary search. Look at editorial
How to solve Div. 1D?
Doesnt Ternary search take about logbase1.5(N) steps ? in C i looped 80 times and it gave WA and when i changed to 100 , it gave AC
http://mirror.codeforces.com/contest/578/submission/13051709
http://mirror.codeforces.com/contest/578/submission/13043558
Any idea why?
Even I would like to know.
Can i know what's wrong in this solution for problem D. "Or" Game
3 1 2
17 18 5
My solution give 55 for your case, and it's correct. Can i know if there's any thing wrong in my idea?
Sorry
3 1 2
5 18 17
Maximum value for now doesn't garantee that OR will be maximum in the end.
That is why you cannot use dp.
Thanks :)
In problem D, using inbuilt pow() function on my system gave me the correct answer for test 9, but for some reason it failed on the system tests. Anyone has an idea why the pow() function gave different results? ps: replacing the pow function by writing it manually got it accepted. Thanks
bump :)
same thing happened to me...
The same thing happened with me too :'(
Don't use pow(), ever, its result when converted to integers is unpredictable and not guaranteed.
http://stackoverflow.com/questions/9704195/why-pow10-5-9-999-in-c
The 'or' problem, Can't you just multiply biggest number k times ?
I didn't try it it seemed too easy...
Can someone tell me if this is correct?
2 1 8 107 108
contest kiri
why the wrong answer test run on my computer is correct but here make my answer decrease 1 ? http://mirror.codeforces.com/contest/578/submission/13046231 upd:sorry,I have made a mistake that pasted my problem C solution ,my trouble is on problem B
where can I get help? will codeforce retest my solution?
I'm confused and helpless...how can I contact administor?
What's the problem? How were you able to run this your program on this test locally (our interface doesn't allow to download the full test, isn't it?).
but I can see which test get wrong answer in the page...
The test cases are visible after the contest, so we just tested the case and got the right answer locally. (Its a small test case)
Is it pow() funtion on codeforce dosen't work?
10^2 is 99 in C++ — that is the reality. No one cares for so many years. Just don't use pow()...
http://stackoverflow.com/questions/9704195/why-pow10-5-9-999-in-c
wow,I was astonished.
so the problem was cause by float point number.
I supposed this funtion had overloaded a int version in c++ but unfortunately it's a c funtion. however thanks for your help :)
finally I still got WA...
Div. 1 B, wrote suff[i] = pre[i+1] | v[i].
Copy pasting mistake -_-. The worst part is it passed all pretests and it passed all test cases till 16.
http://ideone.com/2nKw1d
My solution gives correct answer on ideone for Div1 problem 2 test case 9. However the server shows WA for tc 9. Please see. I think many users are having same problem.
Don't use pow. Write your own function
Same Power function is messing with answer; idk how
But isn't it a codeforces error since it worked fine on our systems?
Thank you Dreamoon xD
and bayan :D
Congratulations!
Tnx man :D
Why are my solutions "skipped"? I have not got any rating changes in this contest.
Can you give us eta on editorals?
It was very good contest! but the math was more than programming( at least in C(div2) )!
thanx dreamoon_love_AA !
hey guys https://gist.github.com/pse1202/a01d5c1f094e1599836a
This is my solution of Div2E/Div1C , but it's giving me a TLE
I'm wondering is it because of me using python, or if the algorithm is somewhat slow.
dreamoon_love_AA In problem E div2 something weird
I did ternary search in loop for 400 times and the max length of array is 200000 and I got TLE on testcase 15
I tried to submit the same code again I got TLE on testcase 21
http://mirror.codeforces.com/contest/579/submission/13052885
Then I changed 400 to 398 and I got ACCEPTED.
http://mirror.codeforces.com/contest/579/submission/13052699
can you please clarify that ,the same code got Accepted because I changed 400 to 398.
also the same code got TLE on different test cases.
I've iterated 500 times & got AC. Try using std::ios_base::sync_with_stdio(0);cin.tie(0);
I'm using std::ios_base::sync_with_stdio(0) but I didn't use cin.tie(0) I used it and got accepted but it's bad thing to make the time limit too strict
I don't know the details of these but when u have to take too many inputs or output too many things, try using cin.tie(0) or cout.tie(0) for faster results. If in doubt, just go for scanf printf. That's what i learned (in the hard way of course).
Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).
Why my Submissions are Skipped ??? I have solved two at Contest Time .
Do you completed registration?
http://mirror.codeforces.com/contest/579/submission/13054131 Can someone tell me where I am making mistake.I know this was not expected time complexity and would result in TLE but still I am not able to find why its giving WA .
Please someone help :(
Read previous comments above or editorial. DP won't pass.
Can anyone explain why this dp fails for div2 problem D. solution : http://mirror.codeforces.com/contest/579/submission/13040454
Screencast with Arterm and discrete optimizations at MIPT
Please add tutorial link in Dashboard and problem page.
Screencast