Hello Codeforces!
I'd like to invite you to Codeforces Round #287 (Div. 2). It'll be held on Friday, January 23rd at 19:00 MSK. and as usual Div. 1 participants can join out of competition.
This is my first round so wish me luck! :)
Great thanks to Maxim Akhmedov (Zlobober) for helping me preparing the contest, Alex Fetisov (AlexFetisov) for testing and giving useful tips regarding statements, Maria Belova (Delinur) for translating the statements into Russian and Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform.
The scoring distribution will be announced later.
Good luck everyone and I hope you'll find the problems interesting.
UPD #1 Score distribution will be standard 500-1000-1500-2000-2500.
UPD #2 Contest finished, hope you enjoyed the problems. :)
UPD #3 System testing finished.
Winner of the contest is going to be disqualified due to "Do not use harsh, rude or misleading handle." part of Codeforces rules.
So congratulations to the winners:
UPD #4 You can find the editorial here.
Hello Egyptian contests :D
orzzz... Hoping to see problems without too hard data structures
Masters/candidate masters are the best setters for only div 2 round.They can't invent a lot of hard problems,but if the effort problems are very interesting and solvable for two hours.
Well, they can't invent hard problems, but you are still not able to solve more than 2, eh, what an pity. :/
Good joke,I am little sick and this is really cheer up me:-)
I hope this won't be dynamic scoring in this contest...
I agree dynamic scoring is messed up in many ways...
I hope this Egyptian contest wouldn't be so "interesting" such as previous one from Japan :D
ok, so ? ( 3ayz eh y3ni ?)
What? I can not understand both your message in brakes and -22. :)
sure you'll make a good contest my friend :D
hope the you make the next contest as a grand master :D
Damn that would be a while
well , i didn't see that coming :D
I'm new here, What should I do to register? I can't see the option?
Registration begins in 13 hours from now :)
Thant was not really helpful :-/
As a reaction to "I can't see the option"? He already knows registration is necessary, but is asking how it's done. The answer of "it can't be done yet" is perfectly valid.
So probably I misunderstood the question. I assumed he knows he has to register, for example because of other competitions like TC, where registration is needed... If he knew, where to register (contest list page), he would see the countdown, so I wanted to navigate him to the page...
You have to register.
On this page will be the link to register — http://codeforces.net/contests ;-)
"The scoring distribution will be announced later."
So mainstream)
the contest is first rate to me
i hope to be good :D :D
Good luck!!!
And you didn't participate the contest.
All the best for this round ~
Is this the 1st Egyptian contest on Codeforces ?
That's awesome =D
I hope to see interesting problems =D
No ahmed_aly was the author of Beta round #67
No Atef was the author of Beta round #83 :P
how to register for this contest? It is the first time for me to take part in the codeforces contest.
answered here — http://codeforces.net/blog/entry/15930#comment-208463
There will be link, when registration starts:
Finally an Egyptian contest ! That's awesome *_* :D
an Egyptian contest with Egyptian problems! :D
It will be a good contest I think.
Good luck ^_^
This is my first contest on Code-forces. I hope everyone will help in this platform.
upvote pls!
Why are you downvoting?I was asking for upvote :(
You have to deserve upvotes, you cannot ask for them, it works only with downvotes :-D
Sometimes it does not work for downvotes too — guys asking about downvotes receive upvotes instead :)
pics or didn't happen ;)
It will be attractive if all problems be about Pyramids...
My first contest in here, not sure how it works, but we will see :) Quite a lot of registrants so far, so it looks like to be a good contest. Looking forward to puzzles. GL&HF to all
Nice training for my eyes :P
It must be good for improving eyesight!
That's the first contest I cannot compete (DIV2 only), but I found that I can register as "out-of-competition" contestant. I can hardly believe, that some DIV1 guys, are creating new account, just to beat DIV2 contestants (of course except the case of dreamoon_love_AA in contest #284).
still we don't know who is sorry_dreamoon
I_love_tigersugar once explained his motivation here; and YuukaKazami said about other reasons for it in this message.
It is hard for me to understand their reasons and motivation, but not hard to believe that some DIV1 guys are actually doing it.
Be a winner !that feel is like some good.DIV1 guys maybe feel some glad!
Good luck everyone!
You can use this tag :
"1 hour for system testing "
or this tag:
"dynamic scoring"
Where is the scoring distribution? :)
Thank God!! No Dynamic Scoring Gl & Hf!!
лишь остаток после деления результата на номер m.Какой еще "номер"? Даже Google Translate переводит как "число".
i was using 1<<h and got wrong ans in pretest in C question and when used pow(2,h) got correct ans why ??? because of this i couldn't attempt more question in this contest..
Don't talk about problem solutions before contest is over. Particularly if you are participating out of contest.
You needed to do 1LL<<h because 1<<h will be an int, which may overflow.
Wish I knew this earlier :P Cost me a 100 points.
me too...
Use 1LL<<h or ((long long)1)<<h instead of 1<<h. Because 1<<h is int.
I made the same mistake. (1<<h) will be an int as 1 is int. (1LL<<h) will pass too as it will be a long long.
Since 1 << h is an integer, it will cause an overflow, while pow(2, h) will store the value in a double, so the value will fit in the variable.
my code failed because of this stupid overflow mistake
use 1ll << h instead. because int can't hold 2^50.
What are the answers for following cases for Problem B:
100 0 0 0 1
1 0 0 0 1
How? We can use the pin only on the circumference of circle, right?
You can show that by putting the pin appropriately even on the circumference of the circle, you can always move the center of the circle by any distance not greater than 2r in one move.
my answer is 1 for both cases.
You can move center of circle to any point with distance to it not greater than 2R. Why? Let's consider a line segment between an old point and a new one. Now draw a segment bisector and put a pin in any intersection of an old circle and this bisector.
Thanks for the proof.
How to solve D? Is it DP? If yes, can you say me what is 6th case?
How to solve B? I solved everything but this f***ing geometry :(
Calculate distance between two points, divide the distance by diameter and output ceil of it. :D
Consider the test case: 4 0 0 1 0. How to do it in 1 move?
The furthest point on the circle to 1,0 is -4,0, and the closest point is 4,0. By the intermediate value theorem, there exists a point that is equidistant from 0,0 and 1,0 on the circle. Using this point as a pivot works.
EDIT: Fixed error in points
I asked the same variant here
Answer is 1. I tried to hack 3 solutions[All unsuccessful] using this case. Author's answer is 1 for such case. I dont know how :/
I'm not sure if my solution is correct but for me the solution was: ceil(dist(center1,center2)/(2*radius))
mark03, My formula was exactly identical to yours, but my code doesn't even pass pretests .
You need to check your formula for checking the distance between two points.
Round #287 (Div. 2 Only): 3298 participants
Round #286 (Both divisions): 2600 participants (572 + 2028)
It seems that harder problems might lead to fewer participants, an important lesson we learned :/
my personal opinion,your problems were more fun and challenging than todays contest ,,plus i really liked the editorial :D
Thank you! :)
How did you count the "participants"? I guess you use the number of people who made a submission. Then that's reasonable your contest have few participants: Petr said he don't know how to solve any problem after read them, so it will be sure lots of people read Div1-A and don't know how to solve, then they will not make a submission.
And another reason is that the difference of start time: your round start at an unusual time.
My definition of "participants" is the people whose handle are on the official standings, so yes, that would be same as the people who made at least one submission. I think the current system of Codeforces which allows participants to "run away" from contests when the problems are not so convenient for them is not very fair, especially in these cases.
The time of the round was probably a larger factor, though, since Div.2 A and B were not too hard for those slots (at least in my opinion), and Div.2 has a larger population.
You need at least one easy problem in a problemset, otherwise there are lot of participants who just can't solve at least one problem.
I know 3 guys, each of them with rating 1800+ (and one even with 1900+), each of them registered for previous round and spend at least an hour trying to solve something.
But none of them is included in your stats, because they didn't submitted anything.
Yes, we also know more than one Japanese who were motivated to participate but "failed" to do so because of harder Div.1 A. It seems that the problem in this slot should be easy to code some solution that can at least pass the samples, if the rules (which allow "retreat") remain unchanged.
Right, even if it will be not so easy to write corect solution, but general idea will be obvious — number of participants will be bigger.
Something like this problem comes into my mind... Just take a look at standings of that contest :)
В последние минуты пытался взломать Д. Приходил непонятный вердикт типа "отказ". с 3 раза взломалось, а те 2 взлома превратились в "игнорирован".
не нравится мне это в положении
Wow, I was stuck on D for so long with thinking that anything ending in 0 was bad since y=0. I could always make my code pass either the second or third case, but not both. After debugging for like an hour, I saw y!=0, and fixed it (badly) and found my new mistake with like 30 seconds left.
Kudos to the problemsetter for adding a case where if you forget both that 10000 works and that 01230 doesn't work you still get the same answer :P
I was implementing shitloads of math stuff for D for like one hour, I read E 15 minutes before contest end and finished typing 15 seconds after contest ended, imma kill myself if the thing I typed is correct :(
Feel free to share your solution with your real accaunt :)
Ehm, no comment :D The late soln got accepted, damnnnnn
Does the following approach solve D?
since k <= 100, we at most care about the 2 last digits in the suffix. so for numbers up to 100, check that the number is a multiple of k, if so then we can extend this suffix just by padding digits and making sure that the first digit is not equal to 0.
I tried it but could not implement it correctly. Also, we should not count twice: say if 12 divides k and 2 divides k, when we extend 2, it will look lik xxxxxx2 but some of these will look like xxxxx12 and those are counted already in extended suffixes of 12.
Your assumption is wrong. Try with K=39 and the number=139. In this case, you would say that 139%39=0, which is not right.
You are right but that's not what I mean. I think that you got me wrong. We can, for example, choose y = 39 then any number ending with 39 will work because y is a suffix of that number.
What you can do is use complementary counting, and instead count numbers where there is no suffix that is a multiple of k (except 0), and subtract this from 9*10^(n-1).
To do that, loop over the length of the number, and add a digit at a time, but only to numbers that have no suffix that is a multiple of k (i.e. don't use the 0th element to find the next row).
Don't worry because you did not implement it correctly,idea was wrong!
If I interpret your approach correctly, you will fail on n = 3, k = 3, among with all other cases with n ≥ 3 and k ≠ 1, 2, 4, 5, 10, 20, 25, 50, 100. You will not count the number 102 because its 1-digit and 2-digit suffixes (2 and 02), so you discard the possibility of x02 working.
I was on
Bfor 1h 30m. No success! Wish I thought about C from the first place.Same here, except I wasted an hour cause I had used int instead of long long. Never making that mistake again! :P
C problem. Really good but I can't understand the fourth test example. Can someone explain it to me.
Как только закончился раунд понял как надо решать D: двумерная динамика, dp[i][j] = количество чисел, где i — длина числа, j — остаток от деления. Лень расписывать как считать, но если идея верна — подтвердите пожалуйста. Асимптотика O(10*n*k).
у меня было еще 2 состояния — последняя(старшая цифра) и делился ли суффикс на К.
А мне и так хватило: 9529659
Got WA at #9 on problem C. What is it about?
I used 1LL for shifting.
did you use long long int for n?
Yes, I used long long for all variables.
What's the answer for:
50 50
1125899906842544
You have
It should be [...] y = 1LL << h;
God, what a stupid mistake. Thanks!
oh my god!!!!!!!!!!!!! my C problem!!! why did it lag in 10 seconds last T_T ?!!
Jan/23/2015 19:59 Unsuccessful hacking attempt by * tourist
Now I have this achievement not only at TopCoder, but also at CodeForces :)
lol, what did you do to him that he wants to hack your solutions so badly? :P
I guess
dist-=1e-12;of problem B.I've hacked two people whose eps is larger than
1.25e-11with this test case:which became the case 37 in system test.
And funniest part is that my solution is actually wrong.
This
-1e-12is too small comparing to dist; it just does not change dist at all :)My solution says 2 for this test case:
It also fails this test even with 1e-11 — this value still does not change dist.
I bet here is the actual funniest part:
http://codeforces.net/contest/507/hacks/132553/test
This is the testcase I tried to hack you with :) and your solution prints 1.
I found at least three ways to make it fail:
1) Set
dist = 200000;instead of actually computing the distance.2) Add
cerr << dist;after subtracting 1e-12 from dist.3) Turn -O2 off.
When none of this is done, your solution miraculously works.
You are right, thank you:) Checked your hack attempt... Well, it works :D
2) Add cerr << dist; after subtracting 1e-12 from dist.Yeah, and this was my mistake while trying to hack my solution in customtest; it was like let's output some debug values; I'm not changing my solution in any way, so it is OK :)
4) Turn -ffloat-store on.
Does Tanya Romanova love you back?
крутой вердикт
My accepted solution for E just finds a shortest path in the graph, if the cost of each edge is 4-z[i]... >.<
And that can be proven correct, even. Among all shortest paths, the one that uses the most roads that are working is the best solution.
@AmrMahmoud
Nice problems. Liked the second one more :).
i just need ten sec
I though that I needed ten seconds too. So I cry "NOOO!" when contest have finished, type last line of code ... and figure out that my solution is wrong anyway.
Nice problems, I loved them! (although my D failed on test 78 :( ). Still, more than the problems, I love that you put a list with the winners, which is very nice :). (at my previous div2 I was first and that guy didn't put a list with the winners, I will put him in my "black list" hehehe....)
I've looked at your graph... Great... You improved A LOT in a very short time (Y)
Yeah, well, I had a great teacher during that time :).
wtf niggers participate in contests? is there internet in africa?
The Fuck_Eyelids's profile is filtered for Iranians...
really nice problems RetiredAmrMahmoud :)))
How sad it is, that almost in all Div. 2 Only contests (and many both Divisions contests as well) the leaderboard is always filled with unrated contestants... :(
Dear Div. 1 users, there is a feature called "Unofficial Participation". Is it better to fight someone your size?
I'm just wondering, what can go wrong if DIV1 participants are competing on same problem set, but in different division (not competing with DIV2 participants). I think it's still fair, for the best is maybe just typing competition. Also it might be not interesting for the best of best, but still interesting for the rest. What do you think?
First of all, you already pointed it out — in most cases it will be just a typing competition. I think it will be a bad idea — to calculate contestant rating basing on results of solving such problemset.
It may be also separate division (DIV1 contestants competing on DIV2 problems), but for example in my room only reds solved D and E, so for most contestants in DIV1 this might be interesting...
Getting into top10 of div2 isn't easy for violet, I think that one should be at least strong yellow to have good chances for it. So even if we'll made such contests for violet and yellow (but not red) — it will not solve problem with unrated contestants in top10, i am sure that lot of them have red color at main account.
Well, maybe CF should invent another rating — for unofficial participation:) It will not affect main rating, but may help with all those "i don't participate unofficially because such contests are not displayed in my profile", "i don't participate unofficially because it does not change my rating and i have no motivation" and so on.
For div 1 users, two different rating:
Rating div 1 contests (official -> Contest Rating)
Rating div 2 contest (Additional -> Typing Rating)
How rating is calculated, I joined and solved 2 but my ranking and contest tab doesn't show any change?
It does now ;-)
Patience
I've just 1-2 minutes ago jumped blue->pirple
Wow, so nice!, maybe this was my worst contest (I didn't solve any problem) but, after an hour and a half of competition, I noticed that I knew how to solve the problem E, so I started to code it, and finally, 30 minutes after the end of the competition, i got ACCEPTED from my first submission, also this is my first E problem solved :D congratulations RetiredAmrMahmoud, and sorry for my english, please tell me if you don't understand something.
What?!? I become candidate master on first contest :) :) :)
by the way, time limit is a bit strict for python 3 user like me on problem D, I got TLE on test 74, finally I use some constant optimization to get AC on practice mode. but It's really fun :D
It is known that the time limit is designed mostly for fast languages like C++. Python users sometimes need to do constant optimizations, or otherwise use another language altogether for time-critical problems.
As this was first contest on code-forces, I become 'Specialist' with solving one problem. Wish, better in next contest.......
Can somebody tell me what is wrong in this logic for C what i did. 1) calculate the parents of n upto node number 1 and store them in a array ( parents are always n/2 (integer division) ) 2) started from second last ancestor of the node ( first being node number 1 a.k.a root node ) 3) used the lrlrlrl relation to check if the number i wish to go to belongs to this sub tree or not . if it did just did count++;and changed character .(if l change to r otherwise change to l) else did count+= (1<<h) -1; and didn't change the character because my last step was already reverse of what it was supposed to be hence next will be same as before .
CODE
I loved the problem set. I encourage you to continue proposing problems, you're very good :).
lol everyone who failed B on test 37 due to floating point issues (me included, why does round return a double?), you can blame johnchen902, since the test was only added because johnchen902 hacked two solutions with it, and otherwise your solution would have passed :P
lol, thats why I used integer arithmetic and binary search (I am always unsure about precision/rounding)
It was not about floating point issues but unnecessary eps. In your case, your solution failed because of the minus
1e-9, which is too large. It should be smaller than1.25e-11to get pass test 37. In fact, you didn't need to minus anything, just like:printf("%d\n", (int) ceil(hypot(x1 - x2, y1 - y2) / (2 * r)));By the way, the toughest case I've found requires your eps to be smaller than
6.28009e-012:what is the output of this testcase in B
0 0 1 1 2
the target point inside the circle ?
R can't be 0, and if the target point is inside the circle, the answer is 0 or 1, depending whether the target point coincides with the current point or no, respectively.
Ok got it I wrote the testcase wrong I was meaning 2 0 0 1 1 , Thanks :)
Could someone please take a look at my solution to C? I got the correct answer
830699159852for input39 457181784666on my machine but wrong answer547231318312on the judge. Notice that the second input is a 64-bit int. Later, I realized during the contest I forgot to changescanf("%lld", &n);to%I64d(9526642). But after that is fixed, I still have the same wrong answer (9538126). So I usedcininstead, but again, wrong answer (9538164). Could someone please take a look? I think the algorithm is ok it is just the difference between my machine and the judge. Thanks for any help!OK. I changed the language to
C++11and it is AC now. I am more confused now. Which part of my code needsC++11standard?It seems that the constructor of bitset is 32 bit for C++98 and 64 bit for C++11
from cplusplus.com
Got it. Thank you so much!
Probably for the first time in my programming history I didn't care about float numbers' error and hey, it worked!
sorry for posting off-topic, i couldn't find any other place to post: this time AGAIN the CF round (288) is div-2 only. Why the sudden change of plans? earlier it showed both div1 and div2 o.O
I don't know why you're posting here. You can discuss this issue in this thread.
I wasn't aware of this thread.. thanks for replying :)
Can someone explain the last case of DIV-2 C ? 1024 is located in the left subtree of the root(1). Now our first command is L , so from root(1) we will be going to the left subtree . That means we will not visit the right subtree before finding the exit , so how come the answer is 2046 while we already have reduced the half of the node in first command ?
I think you have mistaken, since the height of the tree is 10 the leaf nodes are from 1 to 1024(2^10). So
1024 is on the right sideand not left.thanks , I misunderstood the problem
مبروك