Всем привет!
Через два дня, в 19:35 состоится Codeforces Round #339 (Div. 1 & Div. 2) Этот раунд необычен тем, что мы, его составители — обычные школьники, объединенные тем, что вместе занимаемся на кружке в 179 школе. Для нас этот раунд — первый опыт и мы постарались сделать его максимально интересным и безошибочным. Я приглашаю вас всех писать этот раунд, потому что задачи будут решаемы, но при этом даже tourist-у придётся подумать над некоторыми :)
Под началом и полным контролем Михаила Тихомирова(Endagorion) задачи для вас готовили: Егор Чунаев(ch_egor), Василий Алферов(platypus179), Дмитрий Саютин(cdkrot), Тимофей Гутор(Tigutor), Мария Федоркина (crossopt). Кроме того, задачи придумывали: Михаил Сорокин(themikemikovi4), Сергей Алейкин(Derrior). Отдельное спасибо Глебу Евстропову(GlebsHP) за помощь в подготовке контеста, Маше Беловой(Delinur) за перевод условий на английский язык, AlexFetisov и winger за тестирование, и, конечно, (MikeMirzayanov) за уникальные системы CodeForces и Polygon.
Раунд будет проведен по стандартным правилам Codeforces, сначала — претесты, потом финальное тестирование, внимательно продумывайте все случаи в своём решении.
Удачи всем на контесте!
UPD Разбалловка: Div 2. 500-1000-1750-2250-2250, Div 1. 750-1250-1250-2000-2500
UPD Поздравляем победителей! результаты
Div1:
Div2:
UPD Разбор
Poor english, let's hope the english statements will be better..
Yes, i dont speak english very vell, but lately we'll correct this post. English statements will be created by Delinur, and she know English very well.
But you translated Wikipedia...
From English to Russian Example This to This
So this post can be better if you want Delinur to translate it to English, too.
Deliner->Delinur
Statements were pretty clear, thanks for that!
problems were also nice and interesting, I really liked C div1 and D div1 :)
my only complaint is A div1. there was no idea behind it, just a stupid geometry formula.
i has very very good expect contest, so many prepared people and i like endagorion contest because they very very good.
best hope much good statements
isn't it rude to make fun of someone who just prepared a contest for you?
Yeee, another codeforces round rated. Wishing ratings high to all, hope math problems to see.
hope your english to learn
This comment is actually funny! I like it!
Google Translate would have done better. :D
=\ http://pastie.org/10686682
Somebody help, my sides are leaving the orbit
Is this the original post? Hillarious!!!
I bet touristy will scratch his head for the entire duration of contest, as to why the drafters have given solved problems in a contest :D
The statement of problem B in the last round was horrible, i was not able to understand it till the contest ends.
and from the English used in this blog, I think this one will be worse :(
please make sure the problem statement be clear and concise to be fair enough for all contestants.
GL & HF
I want to say the Tigutor-у that his knowledge of english is very good.
I'm not only fan of Ilya_MSU but fan of Tigutor too. What tasks have you created except Div1E?
You will see the problems authors in the editorial when it is published :)
I will keep silence before.
Div 1, F, certainly.
How do you know tourist will have to think it over..?
Maybe they have asked him?
Strong feeling about this : Some new algorithm/trick/concept from some recently published paper will be involved.
Вчера — школьник в ЛКШ, сегодня — автор раунда на CF (c)
И???
:D :D :D :D :D :D :D :D :D
He scared to participate in contest :D
but..
More upvotes on a comment than the post itself :) Tourist is gonna make the contest setter remember who he is.
It's really inspiring to me that someone with less rating than me could hold an CF contest. Thanks!
I'm so sure in Tigutor that I'm going to cut my balls off if he won't be red in a month. Just like Ilya_MSU
I'll remind You to do so. ;)
I'm waiting for next month.
S/He seems careless! Maybe s/he is the girlfriend of IlyaMSU?
I'd like to but I'm not. :(
Username relevant.
I don't want to underestimate from anyone but he has Registered 18 months ago and the maximum rate he can get 1514 and now you say that he will be red in a month do you actually think so
Thanks a lot for your research
research!! it just a click on his handle
I enjoy contests by lower rating writers. They usually contain interesting problems that involves creative thinking.
Has Endagorion too low rating for you?
I think there are at least 3 problem eassy in CF round 339.
No buddy. All problems are solvable by you if you are coder like Tourist :)
why you must compare with tourist... you must do better and you must solve problems even tourist cant... you must make it solvable.
It is quite impossible for him . I know him very closly
Spam detected :P
thanks!
A contest prepared by so many people is my worst nightmare. Hope for the best though.
I'm new here, could you tell me if there's a difference between Div. 1 and Div. 2? Thanks
Hello, Div 1 is more difficult and is generally for contestants with a rating >=1900. On the other hand, Div 2 is easier and for less experienced competitors.
When the contesters take part in Codeforces contest, they raise or lower their rating that reflects their ability to solve the tasks. The rating is a modification of Elo rating, several details can be read in a fuller form. According to the rating, the contestants are split into two divisions: the second one (the weaker one, amateurs) and the first one (the stronger one, pros). The contestants who don't take part in contests and those whose rating is below 1900 belong to the second division. The 1900+ rating means that you're part of the first division. Usually two types of contests are held on Codeforces: for the second division contestants (the first division contestants can take part there out of competition) and for both divisions. The first contest type contains simpler and learning-oriented tasks.
What is your div1 account?
Difference between Div. 1 and Div. 2
To be honest I don't think the English is poor...quite clear for me...
they edited it, the last version was a bit funny but if you tried your best you could understand what it meant
yes!
Initial revision is really funny!
Look, like this one : << I invite all of you write this round >>.!!
BTW,you're good-looking:D[user:Tigutor]
Aren't you male?
Yes...But it doesn't matter to praise him...
He is a she. No guy praises another guy for looks bro, unless gay.
Otherwise, chinese names gender neutral. I know a girl who has same name as her.
it's quite normal for us to praise other's looking no matter what the gender you are,if you like.
Alright, I accept that. But YOU are a girl, unless, your name is gender neutral and you are gay(which is cool, btw) :)
but you're wrong.maybe there's something different between our culture.anyway,stop talking about this.
Eeek!!!
No offence to you sir, our cultures are probably different.
Okay.good luck for the coming contest
哇塞高中生出题好厉害也！
I hope tourist takes part in this round and talk about the difficulty
Does the scoring mean that the difficulty of div2 D & div2 E is the same?!
It's difficult to say. For decent div1 coders it may be same. For good div2 coders it may not.
какое растяжимое понятие :)
The comment is hidden because of too negative feedback, click here to view it
Look, a self-predicting comment!
Make here as a link to your comment, then it'll be perfect :)
Can someone plz explain the second testcase in DIV-2 1000 points....
What is 'product'? I don't get it....
Now I got it.. Product means multiply... My english is terrible....
If i get WA in pretest then also 50 points will be deducted?
yes, but if you don't AC that problem , there will be no decrease on your total score.
this is what Codeforces says : "there is 50 points penalty for submission which fails the pretests or resubmission (except failure on the first test, denial of judgement or similar verdicts). "
I'm becoming newbie today n:). So happy to achieve this feat. Feeling gratefull. after being hacked 3 times. :)
:)
Well. That could've gone better.
But dat number of pretests... I really hope not to fail systests now :D
Let the hate begin!
He did hint at problems being hard, but people laughed him off because of his weak english.
I cried at your comment XD
Will the tests which lead to successful hacks be used for system testing?
Yes.
Do we need convex hull in div2C or we can find the smallest radius without it?
Min from distances to all edges.
No, because points are given clockwise or anticlockwise direction.
Look at the second test
You just need to find the point on the polygon closest to P and the one farthest away, the one closest to it is going to be on one of the edges ( so check each edge), the one farthest away is going to be one of the vertices ( so check each vertex )
Let MAX be the largest distance to P and MIN be the shortest distance to p. Then the aswer is (MAX*MAX-MIN*MIN)*PI.
No convex hull required.
wrong.
Consider the segment with end points -1,2 and 1,2. The minimumis at point 0,1.
read more careful, 0,1 is on the edge
I tried something similar , but I was checking for min distance on vertex too. Can you clarify a bit more why the one closest is going to be on one of the edges?
It could be that the point which is closest to
pis an endpoint of some line segment. In general, for a given line segment if the projection ofplies on that line segment then that's the closest point topon that segment. If not, then the point which is closest topis going to end up being one of the endpoints of that segment.I think we just need to find the point of intersection of each side with normal from origin to that side. If it lies within that segment, then that point is to be used to find minimum radius, otherwise, the smaller distance to origin from the 2 end points of the segment are to be taken as candidates for minimum.
Waiting for editorial.
edge is not the same thing as vertex. The one farthest away is a vertex, the one closest is ON an edge.
Oh, read it wrong. My bad :)
we can do it without convex hull also. to find shortest distance of each line segment from center first find distance of both points from center and then check if the line having slope equal to the perpendicular of this lines egment and passing through center intersects the line segment or not. if yes, calculate intersection point as well as its distance from centre. take minimum of all calculated distances.this is the smallest radius.
I don't think Div1 B and C worth the same score. T^T
What's the idea behind Div2 Problem C pretest 3?
I tried a naive solution by finding nearest and farthest radial points of the polygon. Guess there is more to it. This approach works for the illustrations
I suppose something like:
How did you make that colorful and cool drawing?
Umm, microsoft paint? Then post a picture comment here.
You are right. Something like this :)
Div2 B time limit was a bit too strict I thought
Dont use python or biginteger.
No! You must check if the given number is beautiful (reading it as a string). If it isn't beautiful, save it for the final step. For each beautiful number, you have (lenght-1) zeros. So, if the number is only composed by one "1", and this one must be at the first position (because the restrictions), you don't need to do estrictly a "product", because most of them are one "1" and a bunch of "0". You need to save the sum of total zeros of beautiful numbers called "zSum". So, if the non-beautiful number is zero, the answer is zero. Else, the answer is a string composed by the non-beautiful number (remember to read it as a string, because the lenght can be 100000 as maximum) and then "zSum" zeros. I took me a few submissions before figure it out.
Yes, my java submission counts number of zeros and appends a 1 or the non-beautiful number at the front. In java, it TL-ed on test 8, but in c++ it did not. Minor optimizations could drastically change the verdict for this problem. That is why I think this TL was too strict(I wonder how hard it was to pass for python users...)
15351819
Oh, sorry then. Yes, I submitted it in C++.
В задаче С Div.2 у меня недостаточная точность на тесте вроде: 3 0 0 0 1 1 0 1000000 1000000 Думаю, не проходит третий претест именно из-за этого. Как избавиться? Неужели длинное умножение?
Нецелочисленная арифметика там возникает только при выводе ответа, так как вместо расстрояний в этой задаче нам интересны их квадраты.
Нет, третий тест на логику программы. Посмотри на картинку с комментария выше. Скорее всего, ты не обрабатываешь этот случай.
Да, да, уже понял. Только хотел написать, что бы не обращали внимания на мой коммент. Но, к слову, то, что я написал выше, для моего решения также является проблемой.
Третий претест — это когда ближайшая точка лежит на одном из отрезков (а не является одним из его концов).
Даже неловко, что попался на то же, что и тысяча других людей)
Да я и сам попался, сразу заподозрил что решение неверное (уж слишком легко), завалился на третьем претесте, еще немного подумал, 15 минут гуглил как найти расстояние от точки до отрезка, и наконец сделал :) AC после системного.
UPD: Интересно, почему столько минусов у комментария? Вроде и чуши полной не написал, да и не обидел никого. Отпишите в ЛС пожалуйста в чем дело :)
Я тоже часто не понимаю. Бывало наоборот — писал какую-то фигню и получал за неё больше десятка плюсов. Но все равно минусуют намного чаще и без видимого повода.
Отличный контест, огромное спасибо. Задача А очень поучительная, никогда не получал такого интересного эффекта во время переполнения. Были мысли написать что-то, что не позволило бы произойти такому, но отвергнул эти идеи как ненужные, что является очень грубой ошибкой и хорошим уроком на будущее. От этой задачи по-настоящему получил массу удовольствия, несмотря на то, что провалился на ней
Ну не могу сказать, что получил массу удовольствия от полученного взлома через 1.5 часа после начала, но это было несомненно поучительно :)
The test case 1 900000000000000000 12345678, helped me earn 1800 points in the contest by hacking the first problem of almost every user in my room. My best ranking ever, thanks to hacks.
Actually python rocks for this question.
Whats the correct answer?
1 12345678 152415765279684, is the correct answer
I think 1 12345678 152415765279684 108064748184340920 is the correct answer
I think with C++, something like taking logs should have been used. Damn so much overflow :\
The only you need is to check whether if LONG_LONG_MAX/n<k you need to brake a cycle, where n is current power of k.
My solution with unsigned long long int fails :\ Another -1 so
FFFFFFFFFUUUUUUUUUUUUUUUUU----------------
Arithmetic overflow is such a bitch....
It gets me every time...
deleted
Div2B pretest 9? how?
This one checked if your program could answer correctly the case where all numbers were beautiful
What?? There's always 1 non beautiful number..
at least n - 1 beautiful numberssome number of tanks of one country was removed from the game, hence the number of tanks of this country may not remain beautiful.
may may may may
it just guarantees for atleast n-1 beautiful numbers. never for atleast 1 non beautiful no
There is always one number subtracted from, but it might remain a beautiful number. Confusing, I know :P
And here i was thinking i can hack some submissions because of this. -_-
There could be a lot of hacks on problem A if not third pretest(
There could be a lot of hacks on every problem if not these good pretests :)
I think it was a bit cruel — to give samples which can be solved with "point-point" distance, without "point-segment". And at the same time there was no crazy hack fun...
I figured out the point-segment thing with concave polygons after failing the 3rd pretest, but didn't have time to code it all...
Effing geometry.
I remember some people were joking about the difficulty of the problems before the contest... Anything to say? :P
Can anyone explain Div 2 C? My idea was to find the minimum distance from P to the polygon and the maximum distance and then pi*(max*max-min*min)
I don't know correct solution, but yours fails at this test:
4 0 0
-1 -1
0 2
1 -1
0 1
My idea was exactly similar to this comment Now I'm confused
You're wrong. The minimum distance doesn't have to be the distance from P to one of the point in the polygon.For example, for the test: 3 0 0 0 2 -1 1 1 1 The minimum distance is 1 while not sqrt(2).
Minimum distance doesn't always lie on vertices.
eg 3 2 -1
1 0
2 1
3 0
ans = pi*(4-1) = 3*pi.
I handled that issue
Then maybe you didn't handle the finite line issue.
The min point must lie on the finite line segment.
If you just considered perpendicular distance from point p to line then you might fail some cases.
I also handled the issue and failed test 3 : maybe you forgot the edge between the first and last vertex.
Maybe your solution to find the minimum distance from a point to a segment has some bugs.
No I just added the last edge and it passed all tests :)
I think this round is too difficult ....
Do this sample
2
10 10
for Div2 B
This is for pretest 9
Div2:C could also be named as "Peter and Ygrrite".
PS: Game of thrones fans will know:P
What is the intended approach for div 1 D?
The same question for a single query can be solved using dp on trees in linear time which led to me to come up with an approach which involved using HLD to compute dp at the bare minimum required nodes (klogk for each query I think) but the implementation was turning out to be too long so I went off to sleep instead.
You can first build the auxillary tree, which is a compressed tree of the marked nodes in O(klogN) time consisting of O(k) nodes and then apply the same dp on this tree in O(k). For implementation details on how to build the auxillary tree, refer my soln here
Div2 A should've been named Hack those overflows.
My WA solution for div2 C was to compute minimum and maximum radius, find difference between circles and output. I specially handled the case in which all radii were the same(answer =0)
I claim that any radius between [minradius,maxradius] can be attained by some point in the polygon. Is this false?
3 0 0 -2 1 2 1 0 2
submit it
Thanks for great div2A! 22 successful hacks are non penis canina. My hacks:
536870912 = 2 ^ 29
Very good!
second test case can be used to hack unsigned right , awesome
Yep, and the third one is the test, which generates overflowed long long less than 10^18 and greater than previous one.
In first redaction 1 ≤ k ≤ 109 but we thought that it is big trap for Div2A.
Can you describe how do you find second and third tests?
Thank you for strong pretest for B!
I hate Div. 1 A. No interesting idea, just applying mathematical formulas and crying when wrong answer on pretest #3 shows up and then finding a typo in one of these formulas :'(
I agree div1A doesn't find its place in any contest it's a stupid problem.
But we struggled with it. It was for us.
I think this problem fits well in some ICPC-style contest. However, CF round is not ICPC :)
I don't understand what you all are talking about. I see the only problem with it: some guys could use prewritten geometry and get accepted a little faster (several minutes). I haven't used it.
It is the great problem to have a lot of hacks/challenges :)
I don't think it is a good idea to have an ugly problem for the sole purpose of allowing people to hack more
I just used the ternary search for each side of polygon
same here but got TLE on test 37 :(
Same here, but could not get AC during contest. Missed the line segment between 1st and last point :(. Code Link
I don't get it. Why your comment gets +28 while mine gets -32? Is there something wrong with my comment which doesn't meet Codeforces standards?
By mathematical formulas you mean distance between points and distance between point and line? They are well known and quite easy. Actually, geometry problems are quite rare on codeforces, so it's good to have them sometimes.
'Well known' — yes. Quite easy? Well... (between points ok, that's easy, but I didn't remember the formula for the distance between a point and a line and I had to deduce it by myself)
Also there surely are many much better geometry problems than that.
We have this formula on the lesson in 8 form: abs(a*x0+b*y0+c)/sqrt(a^2+b^2) x0, y0 — point's coordinates
There is an interesting, simple idea. However, there's also annoying geometry. If P was inside the polygon, though, it could've made an easy div1A without the annoying stuff.
Any One Please tell me that is What is "Hacked".
After my submission I received a message that solution is hacked...
This means another contestant has found a case when your program produce wrong output. In short, your solution is wrong.
It means someone found bug in your solution and found test in which your code fails. So, your solution incorrect and you should find bug and resend solution.
Thank you for preparing such a contest like this!Although I don't pass Div.2 C,this contest is well! Thanks everyone!
At this time tourist
What is test case 9 in div2B?
Do this
2
10 10
My code gives correct answer for these test cases. still wa on test case 9. http://pastebin.com/rz7D6CKm
Your code doesn't give true answer. It gives 010. Answer 100
It gives 100 for me on my system.
Maybe you used 'cout' and 'printf' together,aren't you? When you use this ,please don't use 'ios::sync_with_stdio(false)'.
something like
4
10 10 10 10
the number of the removed country is also beautiful .
try this : 10 10 10
спасибо за интересный раунд! очень понравилась задача div2 C. К Сожалению, когда понял свою ошибку, не успел отправить правильное решение)
Спасибо Вам за участие :)
The only problem I liked from this set was Div1 D :(
Seriously? My code started working after the contest (on pretests) and it's 300 lines. I don't like it. Idea is simple: there is a stupid algorithm with time O(n+k). How to fit the queries? Just compress the graph to make it O(k) vertices. Or do you have another solution?
I liked the problem D too.
My solution is slightly above 100 lines; the idea is to compute the answer in offline and to use maps with small-to-big optimization.
And I just processed 64 queries at once using bitmasks :)
My solution is heavily based on LCA. We sort vertices from the query in the Euler order (it's computed in one of LCA implementations anyway). Then it's optimal to take consecutive vertices whose LCA has the largest depth and disconnect them by deleting their LCA. If LCA is also a selected vertex, we need to delete some of its children, also -1 case is handled here. The only difficulty is how to implement this idea in the best way, but anyhow it should be O((N + K)logN).
What about div. 1 C? I know you enjoy palindromes :)
Any idea in DIV2E/DIV1C?
There are no DP, right? Just only some tricky but easy-to-implement construction? :)
If we have two letters with odd ai then the answer is 0. Otherwise the answer is g = gcd(ai).
Let's build such string:
1) If all ai is even then we can build a block of length
with 
occurrences of the i-th letter (in any order). And then copy that block g - 1 times, each time reversing it. Easy to see that we will have exactly g palindromes (because g is even).
2) If we have some odd ai then g is odd. So for each even ai the value
is also even. So we can build g identical palindrome blocks of the length 
, where the letter with odd ai will be in the middle and all the letters will occur 
times.
It's not hard to prove that the answer can't be greater than g.
I don't like Div2B statement — take too much time to figure out that numbers could be very long etc etc. One of these tasks where statement reading takes the same (or more) time as solution finding and coding.
Authors at this moment...
system testingWe're sorry, because The Great Admin now in taxi and hurry to start system testing)
When I read the problem statement of Div2.B at first, I could not understand.
, and then I could solve immediately.
By repeating to read the statement many times, I noticed that "find the product" stands for calculating
By and large, the accounts for sample case are too short for me.
Div1A is really great for Educational Round. Authors would do better by PM'ing Edvard with this task. I know that it's wrong, but I was badly confused about this right from the start of the contest.
Did you participate in Education Rounds with geometry problems? In the first one, half of solutions were hacked due to precision problems. In the second one, even the author solution had precision problems and they had to increase the error tolerance 1000 times. I think it is not a coincidence that there are no geometry problems in the last 3 Education Rounds. Too much work to get them right when your adversaries have 24 hours to find challenging cases. Unless you want to restrict coordinates to be less than 100 and set required precision to 1e-2.
Its very funny that participants who have 26 successful hacks on A failed A on system testing :)
Anyway, they earned a lot of hacking score (besides they didn't solve the A)
Is that Endagorion in the background?
Tourist fanboys everywhere -__-
Super Contest, I got a lot of fun!!!!!!
And KPACUBO got a lot of fun!!!
Что особого в тесте 26 к div. 1 B?
Если кому интересен ответ:
В моём решении перебиралось число чуваков, которых поднимем до A, а также "вторым указателем" поддерживался чувак, по которому выровняется минимум. В 26 тесте они "наползают" друг на друга.
Странно. У меня из-за этого был WA6.
Если интересно, вот строка генерации:
Иначе говоря, n = 2054, A = 6746, cf = 807, cm = 237, M = 6525798, seed = 561626.
Рандомный тест.
Вы абсолютно правы, этот тест именно против этого, а строка генерации действительно немного страшная, потому что этот тест нашло стресс-тестирование.
А если минимум — это не число из массива?
Ну я немного упрощённо описал решение. На самом деле я храню индекс в отсортированном массиве элемента a[i] такого, что минимум находится между a[i-1] и a[i].
"Респект" тому кто составлял легенду к div1A. Просто самая лучшая..
Благодарю.
Look there, running code: here
Why system testing stuck at 100% ?
Thanks to authors! : )
Хороший раунд, требует не просто знания алгоритмов, но и знания языка
Endagorion tomorrow published editorial, please wait...
and you will publish the announce 3 days ago
Well it's tomorrow , still no editorial published
div2 D. Skills what's the answer of 3 5 1 0 4 0 4 1
Another test case for Div. 2 A:
K <= 10^9 but in your test is more
Sorry, I have replaced the big K with 94906267 (<= 10^9).
My code working fine on my machine but failed system test for the same code. Working fine on custom invocation also.
I'm sorry to say there's no way that code's "working fine". You're getting an overflow error, checking that it doesn't become smaller isn't enough, as it can overflow into a bigger number.
For instance, consider numbers modulo 40, k = 4. The powers are 4, 16, 24. 24 is clearly wrong, but it's still higher than 16. Your code won't detect this kind of error.
What you could do is checking whether the division is sane: check that the next number divides the previous into k. That is, if pow[i] / pow[i-1] = k, then you know it's right.
Sorry I misread the Jury's output as mine and vice-versa, Thanks btw :)
Отличный контест! Большее спасибо и успехов авторам, не забывайте сменку :З
Don't know why it failed system test ? code
Looks almost perfect to me, maybe a bit overcomplicated. The problem seems to be you're forgetting the last return value on you function
bool check(string s);
which should be returning true at the end, if it doesn't catch one of the false conditions. It seems you got lucky and the undefined return value is usually true, but it's bound to be false sometime.
Here's a hint: this kind of mistake is something that can be detected by your compiler. Make sure you compile with warnings enabled! With g++ this is done with the flags:
g++ -Wall -Wextra -Werror
(Of course there's more warning flags, but these should do for most things)
Thanks got it :) Why I did this mistake
Do you know how to set these conditions in Sublime Text?
http://stackoverflow.com/questions/23789410/how-to-edit-sublime-text-build-settings http://stackoverflow.com/questions/22516094/sublime-text-compiler-build-options
Ratings Updated!
We have exactly similar ratings, fine)
the worst contest I see in codeforces problem B was unclear
Can't agree with "worst", was quite well overall.
But Div2B is bad, I agree with that. Statement is over-complicated a lot.
As for me it was one of the best problems during last several rounds because it is the one i have just solved and only thanks to it i have become a "specialist") And it is the one you haven't solved (from what you have tried to solve), i know(
Congrats :)
Yea I've failed on that one — algo was correct, but I didn't checked all branches correctness. My failing case was where non-beautiful number comes before 0 in sequence, so I printed "nonbeautifulnumber0" instead of "0". After self-analysis I blame my bad emotions about problem statement — because of them I wasn't very concentrated when checking.
Besides that, its very easy problem. ProblemStatementComplexity > ProblemComplexity. I really hate these ones (and my hate is what caused these bad emotions) :)
That moment when you realize you failed test 3 on Div2 C because you forgot the edge between the first vertex and the last one...
Well done KPACUBO, good job!
Div. 2 D is interesting except for asking the final value of the numbers, that adds nothing but boring and time consuming implementation.
I was thinking about and decided that it doesn't add a lot of code, and has some advantages.
Firstly, you can check participant's answer more precisely.
Secondly, you could detect [potential] situation when participant's solution is better than jury's one and report.
It's true a lot of lines of code aren't added but the logic behind them takes a lot of time to think and debug properly. It costed me 15 minutes to code it on top of the 30 minutes used to find the best value.
1º Indeed, but I still think the problem is already good without them, maybe just asking the minimun value and the number of maximum values used is enough.
2º That's not a job for contestants.
2) Yes, but first reason still applies =)
What about your idea to output a number of full skills and the minimum level I think it is too spoilerish, because allows to guess that the maximums can be taken greedily.
Can anybody please help me where my div2 A problem is getting wrong. ?
Code link — http://ideone.com/EzXlNf
Input case : 1 999999999999999999 1000000000
My output : 1 1000000000 1000000000000000000
Correct output : 1 1000000000
You are using doubles for l and r, doubles have precision problems. It's probably representing 1000000000000000000 and 999999999999999999 as the same number.
You should store l and r in long long and use doubles to check possible overflow.
Ok thanks :)
Was
longintended to fail the tests (Test 24) in Div 2 A in JAVA ? I changed my code toBigIntegerand it passed.I'm sure a lot of people used the method I did. All I did was preprocess the powers, store them in a
TreeSetand printsubSet(l, r+1)(which is an inbuilt method in JAVA TreeSet (similar to C++ std::set)) which prints all the elements in the range [l,r]. You can do this by adding it to avector, then sorting etc, same thing.I don't think these solutions should have failed. This is just my opinion. Here is the WA code and AC code.
Only changed Long to BigInteger, nothing else
You need to be clever if you use 64 bit ints (java long) in order to avoid overflow errors. Echoing a similar answer I already gave:
Checking that the numbers are in the correct range isn't enough, as they can overflow and land in the range again. For instance, consider numbers modulo 40, k = 4, and [l,r] = [3,25]. The powers are 4, 16, 24, etc. Since the third number should be 64, 24 is clearly wrong, but it's still in the [l,r] range so your program will print it out.
What you could do is checking whether the division is sane: check that the next number divides the previous into k. That is, if pow[i] / pow[i-1] = k, then you know it's right and you don't have overflow errors.
This problem basically asks you to properly handle the overflow. If there exists an input which make your code fail, then your code should fail (no excuse).
You can deal with overflow problem without having to rely on
BigInteger.From your code, you only need to add one line before start *= k;
But wait,
start * kcan be overflow, can't it? Yes, so change it to this:You don't need
BigIntegerat all.(http://imgur.com/JckabmD) Why is my output wrong?
That number is clearly not a power of k, and it's appearing due to overflow errors.
See http://codeforces.me/blog/entry/22726?#comment-272811 or http://codeforces.me/blog/entry/22726?#comment-272774 for a better explanation.
Got WA in problem a, initially I was using long double, and I lost a lot of time because apparently codeforces wont work correctly with %Lf. So I switched to double, then I got WA because I needed long double precision. What was the point of div2 a? To get me not to use c++?
Почему после cf round 340 идет сразу 342, где 341 ?
Oh, I didn't know that Decimal in Python is so slow. TL56 on Div2 C :( And the same solution with the usual Float is correct.
Its not "decimal in python", its "python" itself who is slow :)
It is ok for the problems like Div2 A-C. I just mustn't be too greedy for precision in 2C=1A.
Well yea, I was using it before. But then I've failed to implement some solutions because it was 40 times slower than C#. So I've decided to switch.
And I believe two active languages is a bad idea for competitive — it is better to master one (there is a lot of cases to study, like overflows, reading 1e9 test inputs, etc etc).
On the bright side you got to hack my botched handling of vertical lines.
Div2 problem A, good example how useful Biginteger can be.
BigInteger Will get TL, Muhaha.
it won't BigInteger submission
logk r BigInteger multiplications. That definitely wouldn't time out.
Not sure about C++, but in C# we have "decimal" type which can store up to 28-29 digits (basically it is int128 with "floating point position").
I also have another somewhere interesting solution for C#:
Do all the math on regular long type (int64) inside the "checked { }" block which force compiler to check all math operations for overflow. If got an exception -> break cycle.
Cool solution!
Also, there's BigInteger in C# (in System.Numerics), which is also fast (in such small case).
To Java Users : ...... and easier to write. 15385528
I think It's fair to say that
decimalcan be used more like int97 or unsigned int96 rather than int128. Because mantissa is only 96 bits plus 1 sign bit.Typical GNU C++:
No warnings.
naive.cpp: In function ‘int main()’: naive.cpp:92:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (rand() % 10 < a.size()) puts("0");
Sad but logical.
With floating point types being silently and implicitly converted to integers all the way in the history of C/C++, it is only logical to extend this property to simple aggregate types as well. So, no warning, as in
int x = 4.59;.Regarding
rand() % 10, there is no way to tell that the result ofint rand()is actually non-negative, except if we go and analyze the source of functionrand(). In the general case, it would be impossible for a compiler to do (with halting problem as a subproblem). Whyrand()returnsintand notunsignedis however a good question — why, indeed?And the problem the compiler warns about gets quite real with
if (rand() % 10 - 10 < a.size())when the partrand() % 10 - 10is converted to unsigned (~4 billion) before comparison takes place.I don't understand why this get warning:
naive.cpp: In function ‘int main()’: naive.cpp:85:38: warning: conversion to ‘int’ from ‘long double’ may alter its value [-Wconversion] int ans = (long double) (10 + rand());
but conversion for pair<long double, long double> don't. My solution for A fails today because of that.
And about comparing of signed and unsigned values. Why it can't compare them in the following way: if signed value is negative then we know answer, otherwise compare them in unsigned type?
Oh, there's
-Wconversionwhich is not covered by-Wallor-Wextra. Didn't remember that, sorry!Now that's actually strange. In my hand-rolled implementation of
pair <T1, T2>(version 1, version 2), such usage does trigger a warning with-Wconversionright where it should. Perhaps the library authors do something more clever, or, theoretically, not detecting the warning in the library code might be a compiler bug.Regarding comparison of signed to unsigned, that would be a really clever move if there was a processor instruction to do exactly that. Looks like that's not the case, and the alternative is to issue a branch instruction, which may be an expensive operation on a modern PC. And C/C++ compilers usually produce efficient (while not necessarily intended) code by default.
Also, legacy software may depend on the current documented behavior.
Not knowing how to know when overflow will occur in power costed me getting to expert. Oh well, atleast I learnt something today. :)
Can someone tell me which edge case did I miss for DIV2B ? http://codeforces.me/contest/614/submission/15367847
It seems your code fails for such a non-beautiful number:
100005
Its start from '1' AND have zeroes. So you count these zeroes towards the final answer, but also printing the number as it is. So 4 more zeroes than necessary.
Picture removed.
Please don't take it personally but honestly speaking I don't like this picture. A national flag is the symbol of independence and sovereignty of a country. Inappropriate uses of a national flag is not appreciable. May be you didn't do it purposely. But you should know that we can't disrespect our country by using our national flag inappropriately. As a Bangladeshi, my request is please remove this picture. It hurts my feelings. I don't want to see a big hole and some stripes on our flag.
I'm not sure with the question, but I guess, the answer is yes.
I also fell for the notorious test case #3. My solution was: find the furthest and closest point among the N given points to P. Apparently the "among the N given points" part is wrong. The closest point is not necessarily one of the N points.
consider this case: 3 0 0 -1 1 1 1 0 2
The closest point is (0, 1) which is not among the 3 points in input.
So where is the tutorial ?
They said it will be posted tomorrow.
can anyone tell me what is the logic behind div2 B ?
The beautiful number are in the form of 1, 10, 100, 1000, 10000, ..., and there is at most one non beautiful number. So you only need to print the non-beautiful number, followed by as many zeroes as there can be. However, you should be careful with the case where there is zero or no non-beautiful number.
WOW!!! We have 9 Legendary grandmaster now!!! :D
There were only 5 after the rating changes if I remember correctly. I wonder what happened, wasn't the new system supposed to counter rank inflation?
I passed the pretest of problem D with a little issue, and I skipped my old solution and lost 145 points when I found the issue. But when I submitted my old solution today I just surprisingly found it pass the system test.
Your text to link here...
This is the correct one. Just press "compare" to view the old code and the obvious issue.
It seems that the contest will be with no Editorial :(
Отличный контест! Интересно вышло, что по кол-ву взломов самой сложной задачей оказалась DIV2 A! :)
NICE
В списке посылок DIV1 в начале раунда видно огромное количество решений DIV1A "по вершинам" и фейлов на претесте 3. Причем цвета участников самые разные, даже красные есть с таким ляпом.
По-моему, стоимость задачи 750 и простота пришедшего в голову решения должны насторожить. :)
В DIV2 к концу первого часа было примерно 40 участников с пройденными претестами против 600 попытавшихся, но это не так удивительно, как попытка отослать решение по вершинам из DIV1.
Авторам спасибо за достойные задачи, требующие продумать все случаи в своём решении!
Подсказка, предполагаю, была не просто так написана :)
That moment when you realise that E is solvable faster than all other problems (except A). :(
Just because there's no different cases and the most complex operation is modular plus.
hello, have a question: is double on the system a single-precision float? because i believe my solution of the problem C of DIV-2 was correct and on my computer i had correct outputs and apparently on the system it has output different answers.
No. I don't know any system where double has a single precision.
Use %lld to read numbers.
I think problem A is one of the most Hacked problems on Codeforces.
I hacked 11 and an other 15 solutions failed system test .
every one will know how to handle overflow after this contest :D .
just another way to describe div-2 A
how did you do in the contest? I am surprised that you found time. Syllabus finished?
I am getting wrong answer on Case 56 for Div2 C . i used ternary search.. Can someone please help ???
I feel vertical lines you don't like.
Oh thanks buddy , got accepted.. I owe you one :) :)
There wont be any editorial for this round?!
should have been published today
How to solve problem C from Div.2? I assumed that it is necessary to subtract the area of the minimum of the maximum circumference. But it is not so. Thanks
Yes we need to find the area between the farthest point as radius and the nearest point as radius. farthest point is just the vertex at maximum distance from P , but the nearest point can be a vertex or an edge . So just find the distance between each edge and P and take minimum.
But it wont work for the second sample test case. In that case you can see there is a traigular segment with its base towards the pivot. The distance between the line and the pivot is 1. If I use the above approach the answer would be 9*PI — 1*PI but the answer is clearly 9*PI — 2*PI.
I am still unable to get the approach for this problem and waiting for the editorials eagerly.
It works all right ! :D .
In the second sample case farthest point is clearly (1,2) and when you compare distances between every edge and P , You will get the minimum distance with either point (0,0) or (2,0) . I'm not sure what's confusing you !
but when you consider the edge joining (0,0) and (2,0) the distance between that edge and the pivot is 1 which is smaller than sqrt(2) which is the distance with point(0,0) or (2,0).
There is no edge between (0,0) and (2,0). edges are given in clockwise or anticlockwise direction. You are mis-understanding the question. Read it again carefully.
How to solve Div2 D ?
Будет ли разбор?
How to hack a c++ solution that use the defined pow() function ?
search for cases where pow behaves differently(from past experience). :P
Can you give a case were pow behaves differently ?
Read this: http://codeforces.me/blog/entry/21844
25 25 5
И когда будет разбор?)
Что-то мне кажется, что уже никогда...
Разбор будет в ближайшее время.
Антон, а конкретнее?
Waiting for editorial~~~
Still no editorial?
Many people don`t know English very well. And I also. But we are gathered here to develop our skills in programming!
Ребят, как Div2D решить? Никаких мыслей... И когда будет разбор?
Отсортируем навыки по возрастанию, назовем этот массив
v, будем хранить два указателяLиR. Все навыки большеRбудут раскачены до максимального значения, все навыки меньше L будут раскачены до какого-то значенияval, гдеv[l] <= val < v[l+1]. ИзначальноR = n-1, аL— максимально возможным. Дальше идем отR = n-1доR = 0, двигая указательLвлево, пока нам не хватит денег для прокачки всех навыков доLдо какого одного значения значения, для каждогоRхраня ответ.Editorial here.
Auto comment: topic has been updated by Tigutor (previous revision, new revision, compare).