Всем привет!
Завтра в 19.30 по московскому времени состоится Codeforces Round #329, который настоятельно не рекомендуется кому-либо пропускать.
Задачи для вас готовили я и Станислав josdas Наумов. Я уверен, что это не последний раунд, в котором мы являемся авторами. Мы очень надеемся, что вам понравится раунд, и каждый найдет себе задачу по вкусу. Для того, чтобы увеличить вероятность этого события, пожалуйста, прочтите все задачи этого контеста.
Как всегда, благодарим GlebsHP за неоценимую помощь при подготовке контеста, Delinur за перевод условий на английский язык и MikeMirzayanov за потрясающие системы Codeforces и Polygon.
Отдельное спасибо хотим сказать Алексею Саплину, Эрике Шефер, Евгению Казакову, Богдану Трубецкому.
Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.
Желаю удачи и высокого рейтинга!
UPD1: Разбалловка будет динамической.
UPD2: Разбор задач
Автокомментарий: текст был обновлен пользователем romanasa (предыдущая версия, новая версия, сравнить).
gl & hf!
I'm so sorry, it seems like no one enjoys this problems...
No one except div1 guys and div1 guys with div2 accounts :D
There are even some Div1 contestants that can't solve these problems
Первый раз кто-то поблагодарил GlebsHP за помощь...
Я бы настоятельно не пропустил его, если бы он не пересекался с кубком трёх четвертьфиналов.
Стасян, я скучал:D
:D
hope to see short statement .... and good luck to every one :)
short statements are not always clear , right?
Short Clear Statements*
Shortest doesn't mean the simplest :D
Is there any punishment for those who doesn't write this,"thanks to MikeMirzayanov (Mike Mirzayanov) for the Codeforces and Polygon." in their contest blog???,, Just curious to know..!!!
Look at the previous contest description. It is quite concise and yes, it doesn't include the phrase. So ask Morphy, I hope he is able to answer after that:)
Good Luck!
Какой — то профессиональный юмор
Очень странно, что любой может прикрепить к данному посту такую штуку. Нужно лишь создать мэшап:
Does anyone want to guess how long will system testing take? What about rating changes? Hopefully they won't take very long.
is this contest was in gym before :D see tags
Tutorial of ыфф
Announcement of Либо баг, либо фича.
Announcement of Короб лучший
Discussion of Короб не голубой
is this contest was in gym before :D see tags
Tutorial of ыфф
Announcement of Либо баг, либо фича.
Announcement of Короб лучший
Discussion of Короб не голубой
As I understand anyone can attach any phrase to blog if he creates mashup with this name. :)
Excited!!
My First Contest On CodeForces.
Exited!!
It should be excited instead.
Sorry for being picky :)
Welcome to codeforces :).Wish you best luck!!!
Why?
And the last 5 link are linked to this page :-| And i can't read russian and is there any one to tell me what does they mean?
It says "You are not allowed to view the contest" when I click on the links. Does anyone one know why?
successful hack
First round from blue coder?)
Color revolution
No, http://codeforces.net/blog/entry/19590
Совпадает с зеркалом западного чф(
Hello all, why are regular rounds not scheduled for the weekend if possible? It seems that by moving contests to the weekend, more people (especially students or employees of different time zones) could participate.
Thanks, and I hope everyone enjoys this round.
weekend itself isn't a common thing :D
Hope see good translation :3
Я решу ВСЕЁ!!!!!!!!
Значить Div.1 в новому профиле . . .
Ты решил всё и стал учеником?
completing whole contest, hacked on A being like :'D
┬─┬ノ( º _ ºノ)
We learn from our mistakes :)
Am I the only one who thinks its funny that fml stands for f*** my life :p
Sorry romanfml31.
lol. Physics and Mathematics Lyceum. In russian language "fiziko- matematicheskiy litsey"
Haha :D
Nothing H-HUMILIATING about it then ;)
My avatar is about color revolution, I didn't change it just to write a comment ;)
Hey!!! Blue is not humiliating
Actually it means:
ФизикоМатематический Лицей (Physics and Mathematis Lyceum) -> ФМЛ -> FML -> Well :D
Why dynamic scoring :'( why why
What does dynamic scoring mean?
Problems will be sorted by expected difficulty or shuffled?
Problems will be sorted by expected difficulty
But it was random :|
shocked
it seems that "The score distribution will be announced later" better than early announcement with dynamic score :(
we can wait man :D
Best wishes to all participants !
By the way, Soccer fans will be happy cuz there will be European champions league after the contest:)
What about order of problems? Are they will be sorted from easy to hard by authors? Or random?
It's okay too be dynamic scoring, but I hope the round will not be the battle of speed.
short Blog = Long problem :| (I I learned from contest 328)
In fact, why is the scoring distribution "announced later" every time?
The site is quite slow now, my solution was being evaluated for something like 5 minutes and when I want to click on some link it loads longer than it usually takes. I hope this will not be the case during the contest, at least :)
For being good in dynamic scoring contests it is very good to solve first problem B or C but it is a big risk because if you don't solve it fast or wrong then the contest will go on very bad. You can choice to risk or not BUT I THINK DYNAMIC SCORING CONTESTS ARE NOT GOOD FOR TESTING CODING ABILITIES !!!!
If you solve all five problems in any order and in any time I guarantee you will do good in the contest and get a big rating increase.
If you solve all five problems in any order and in any time I guarantee you will do good in the test and get a big rating increase.
Better than lags for all contest.
Как дела?
Вообще четко, жду, как и все.
Delay as expected!!!
10 min delay
OK, I don't participate
Nobody cares.
Thank You :) You just increased my probability of getting a higher rating :D
It's loading really really slowly...
Delay again ????
TC admins are DDOSing CF ^^)
.
Do you guys think its a good idea to participate in a contest when you're sad about something in your life?
I think it is one of the best ways to relax and forget about problems(not CF, problems of life=)).
The delay got me thinking...... maybe today I should pass it....but you guys have a point.
Cf contests makes you forget all your problems and just think about the problem..
No. You won't be focused as you expect.
"Be Obsessed. Do something which you are passionate about. Do it because you love to do it. Everything else is secondary."
It looks like we should donate again.
what an unruly contest!!!:(
dynamic delay
wtf am I doing in this stupid hentai picture?
CONTEST IS BEGINNING LATE! 10 MINUTES DELAY :/
What's wrong?
Not 10 minutes,AlreadY 15 minutes.
AlreadY 15 minutes late. After system testing....................?
delayed why?
The longest delay everrrrrrr. :/
15 min delay. wow
You mean: "as usual Div. 1 participants can join with fake accounts"
Bec that always happens in every Div. 2 only contests
There are more than 750 new accounts participating this Contest!
Many contestants are honorable and participate as "out of competition"
But unfortunately some of them are not!
How cares about that!!! It is their business. I am focus on my own performance.
delayed 10 minsdelayed 5 minsЧто же вы делаете то. Мне на учебу просыпаться через 4 часа, а вы начало раунда/сна сдвигаете.
Unknown language round?
x' не может не быть целым числом (а может и быть)...
It is not mathforces
These Problems should be in Div.1.
Что за раунд ?! Расходимся...
контест гавно
полностью согласен
Hello problem setter. It is not div 1. It is div 2.
Is it div 2 or div 1?? I am confuse.
Div2 contest with Div1 problems :(
what a HARD contest !!!
А мне контест понравился, конструктив интересный, да и задачи не на уровне: запустите дфс, выведите ответ. Спасибо Josdas & romanfml31. Почаще делайте контесты
Поддерживаю!
Сказал человек, который не участвовал в контесте:)
Я поэтому его и хвалю :3
Ничего себе! :-о
Никогда бы не подумал, что контест был составлен синим.
Одна только B по сложности такая же, как C в других раундах.
А A... В общем, если бы я не знал, что это A, то я бы подумал, что это как минимум B...
Также в первый раз вижу, чтобы всего 7 человек сдали C. :)
За что в последнее время A делают тяжёлой задачей ;(
contest is hard or I very weak :|
Not complaining, but there's a reason why there is a separate category on CF here called Div 2.
A very steep difficulty curve indeed..
Bad contest :|
The worst contest I've ever seen, it couldn't be worse. Sorry for my bed English :(
you mean this ?
div 2 ????!!!!
OMG!!! C problem with 3000 pts
Dynamic scoring.. :/
The new coordinator sucks. :)
What a hard contest! I couldnt solve even problem A completely! This is frustrating and I lost 150 points in resubmissions!! wtf
Аха, высокого рейтинга таки пожелал он.
Respect to Problem C!
How to solve B?
put each line intersecting with line x1 and x2 in a vector pair then sort it and iterator from the begining to end and find the solution.
If you try a brute force method of checking each pair you wont pass because its a O(n^2) algorithm.
Instead of lines think of them as line segments from X1 to X2
You have to find the y intercepts at X1 and X2.
Create a pair vector of the form { line_number , X1_Y_intercept}
Create another pair vector of the form { line_number , X2_Y_intercept}
Sort them both based on X1_Y_intercept and X2_Y_intercept.
Now
if the ordering of the line_number is the same in both vectors then
there is no intersection
else
there is an intersection
UPDATE : Since I got lot of upvotes I thought I shall make it clearer by an image
oh and make sure to use long long (unlike me) cuz input may overflow integers
el3el2, and make sure to use doubles cuz input can be decimals too :D
That just means the points of intersection need not be integers. The input is all integers. They just wanted to discourage trying to go through the x-axis checking whether two lines cross at that vertical line.
How to solve B?
Let us count y coordinate for x1 and for x2 on each line. It is made like this.
Then we must find i and j that:
First, we sort it. Let us see if a line intersects with others. For that, we must fist if there was
y2[j] > y2[i]for1 <= j < i. If it is true for at least one of i, we output "YES".Hope it is not hard to keep maximum of
y2[j]to calculate if there is a line that intersects with ours.Complexity :
O(n log n)Порог вхождения в этот контест был весьма высок)
Thank God that contest has finished
A и B решаемые конечно, но это явно не уровень div2 a и b
i enjoyed this div-1 contest....!!!!!
I think this contest is like a Div-1 contest.
Not really Div 1 problems are hard but these problems are ugly !
I feel bad for the people who are taking part for the first time. They will probably think Div 2 people are expert programmers after seeing such problems :P
Interesting how you are more concerned about the fact of whether DIV2 coders are expert or not. You are supposed to be worried about the expression it would have on them after a relatively not so simple contest. I think you are a narcissist, egotistical maniac.
That was.. Quick..
Geometry contest ?
NOOOOOOOO. line equation. :)
How to solve B?
I solved x = (b[j]/(k[i] — k[j])) — (b[i]/(k[i]-k[j])) and check if x > x1 && x < x2 and got TLE on test 16.
Something like this (lines[1,...] — k, lines[2,...] — b):
And TLE too...
This is my idea
I have two vectors where I save the interception with x1 and x2 for each line. The tricky part is that I am saving in the vector a pair<double, pair<double, int>> where the first element is the y_intercept value and the second value is a vector with the other y_intercept and the index of this line in the input.
Then, I sort both arrays and for each element from the sorted array, I check if it is the same element. If at position i, there is not the same index line then, we have an interception between 2 lines. If the order in both arrays is the same, there is no interception between any two lines.
I hope this solution passes the systest.
PS: PASSED SYSTEST, LOL!!!!!
This Image should explain it :)
try it with long long int :D
Lets hope Arsenal wins today. Its already a bad day after such a hard contest.
beaten handsomely mate
15 minutes delay + dynamic scoring + extremely difficult problems -> a disaster!
Even O(n^2) solution passed B . I lost a few points trying to hack, not cool at all :)
how O(n^2) pass?
it is an old trick. they just check the first 6000 elements... if YES print yes else it prints no (because these tests are made by system).
LOOOL, WHAT.
99% the answer is no when the answer is no in 6000 elements.
so they may TLE in system test?
It's easy to make hacks for those solutions, though.
I made a case where the input consisted of 1e5 parallel lines, but the solution passed in about 850s . However, someone else hacked it using increasing slopes lines.
Mmh I was talking about the "N^2" solutions that only consider first K points for some K.
By the way, take a look at the loop conditions in the submission you tried to hack, specifically the inner loop in solve(): 14073024. It doesn't actually run for N^2 operations on the case you tried.
Looks like the author's two mistakes (doing N^2, but with incorrect implementation) cancelled each other out on your specific test case. :|
no it got TLE
No, solutions that have O(n^2) time complexity didn't pass system test, and it failed also when checking just the first 6000 elements .
If you saw such a solution please link to the submission .
И почему сегодняшний контест с такими задачами был div2 а не div1 или общим?
это Челябинск, там положено не менее 3 суровых задач на контест
И правда. Челябинский div2 такой челябинский.
hahahahahahahahahahahahahahahahah
How to solve Problem-D?
Just some thoughts. You can observe that you need to divide Y by at most O(log(MAX_VALUE)) numbers greater than 1. So now I think you can use HLD to quickly answer queries "Which is the next number in this chain which is greater than 1?". However, I didn't implement that. And a friend of mine told me we can solve it using LCA-like approach (with powers of 2) with union-find but I don't really understand that :D
Я не Конфуций, чтобы такие задачи решать!
Participated in div1 in a div2-only contest.
почему в C такое не канает (для n>2)?
t
(50*(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((1-(abs((t-25)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
Выходит за рамки
рамки чего? 293 символа < n*100 при n > 2
Нужно подставлять только целые t. Тоже так сначала отправил, а потом условие перечитал.
ок понял =\
Если претест 1 совпадает с условием, то это должно проходить (но не проходит): ((((0)+(((abs(((2*t)-(0-1)))+((2*t)-(0-1)))*(abs(((2*t)-(0+1)))-((2*t)-(0+1))))*0))+(((abs(((2*t)-(2-1)))+((2*t)-(2-1)))*(abs(((2*t)-(2+1)))-((2*t)-(2+1))))*3))+(((abs(((2*t)-(4-1)))+((2*t)-(4-1)))*(abs(((2*t)-(4+1)))-((2*t)-(4+1))))*5))
((((0)+(((abs(((2*t)-(0-1)))+((2*t)-(0-1)))*(abs(((2*t)-(0+1)))-((2*t)-(0+1))))*3))+(((abs(((2*t)-(2-1)))+((2*t)-(2-1)))*(abs(((2*t)-(2+1)))-((2*t)-(2+1))))*0))+(((abs(((2*t)-(4-1)))+((2*t)-(4-1)))*(abs(((2*t)-(4+1)))-((2*t)-(4+1))))*3))
(я это протестировал, точка лежит в окружности при целых t, хотя допускаю возможность ошибки)
У меня такое незашло, пока тоже непонимаю: "t\nabs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs((abs(abs((50*(t-25)))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50))-50)". Идея выглядила так: wolframalpha
Опять провал!
I had never spent this much time on Div 2 B Nice problem :)
What a hard contest:
problem A: harder than usual, took me >10 minutes to solve it.
Peoblem B: Passed pretest with ~0.6 seconds. I'm not sure if python can pass 1 second time limit with full 100K input.
Problem C: Are you kidding? I have no idea how to solve it.
Problem D: I know it's HLD but I never and can't implement it.
Problem E: Time to learn C++! ugh getting compilation error. :p
Seems problem D can be solved by DSU and LCA.
not sure if python solution for B will pass for given time limit. yeah, time to learn C++ seriously.
Even using HLD problem D is very tricky. I thought pre-computing the multiplication of the edges and use HLD but... Xi <= 10^18 :(
The Yi<=10^18,too.Maybe you can limit the multiplication of the edges in 10^18:p
This could be avoided by carefully checking for overflows. Take a look at my solution: http://codeforces.net/contest/593/submission/14073334 (lines 256-258, or ctrl+f "__builtin_smulll_overflow"). I think you could also replace the check ab ≥ 2 × 1018 with something like
.
But yeah, avoiding these kind of overflows is definitely not fun and I think it would have been better to put limits of the form x ≤ 109 instead of x ≤ 1018.
:o I didn't know about that function! Thanks :D
Can anyone explain DSU-LCA approach for problem D?
I never thought this solution in contest-time but I'll try to explain:
If node a and node b has edge weight = 1 you can merge node a and node b since multiplying or dividing by 1 has no effect.
Otherwise because edge weight is an integer so number of multiplication or division will not exceed ceil(log(10^18)) = 60 operation. I guess this can be done without LCA(?), just save the parent and depth of a node(?)
You must have LCA. How else could you tell how far should you traverse up the tree?
Edit: My bad — you don't need an LCA.
First observation is that if you keep dividing y, you'll quickly get 0. (Of course, if you divide by a number bigger than 1)
This is the basic idea
This is too slow because of
***part. It's too slow when we have a lot of edges whose value is 1. Basically, we want to skip all edges whose weight are 1.For that we can use DSU.
Initializing... (This must be done before processing query)
Every time you update the cost, we can do the same.
Can anyone please explain why this output is wrong for C:
I consistently got WA in pretest 1 and I think pretest 1 must be the sample.
10 + 0 * (t - 2) is invalid, it should be
Unable to parse markup [type=CF_TEX]
. Look at the examples under the testcases.You are right.
I'm always right!
You aren't right always, correct is only: (10 + (0 * (t - 2))) (without spaces of course)
I'll go sit in a corner and be quiet now.
Okay, let me see
Невазможна сложна...
Вообще-то нормальный по сложности пакет, будь контест объединённым для обоих дивизионов. Но все ожидали халявы уровня div2. Много времени посвятил задаче С. Думал что там какая-то халява, которую никто не видит. Только надо внимательно врубиться в условия. Что есть какая-то читерская очень простая формула. Так и не придумал.
TodaY most of the hacker are <=300. (Hacked B).
18 solutions for problem C, seriously?
I was not able to solve B :3
this my first div1 contest
Is level of B increased to D :3
Перед контестом пишут, что синие авторами стали.
После контеста пишут трудные задачи.
Одним словом — КококКоко.
Контест отличный! Спасибо автору!
How to solve problem D?
Notice that we will pass not more than ~64 edges with something greater than 1 written on them. Therefore, the only thing we need to do fast while travelling on a tree is to pass sequences of edges with 1 written on them (because they don't change your yi anyhow). This can be done by DSU — merge two adjacent vertexes (u, v) if you get request "write 1 on (u, v) edge, and simply update number on edge if the number ≠ 1. Also you need to update the topmost vertex for this set in DSU. Now we answer on every request by checking if there are more than 64 numbers on path ≠ 1 or by finding all these numbers and consequently applying all the divisions to yi.
.
I'm dying :D
LOL me too. I was hoping I could hack someone like me. xD
You should have been in my room.
отличные претесты. Можно было что угодно запихать
Delinur please translate to english. :)
hahahahahh .... are you serious :D ?
Я предлагаю его нерейтинговым сделать
It is sad, but I have to downvote :(
Don't even care about the system testing. :D
У кого были проблемы с 7 претестом в В, что за случай?
Почему бы не дописать 2 задачи(сложности примерно C,D div2) и не сделать див1 контест? Так было бы лучше имхо.
Kudos for problem C! I spent the whole first hour writing my solution, and I'm still a bit worried about the full system tests, but I really liked it. I'm really fond of problems where you have to construct an object that satisfies certain properties, no bullshit 'find the shortest path with a twist' problems, but something you actually have to think about.
EDIT: yay, passed the systests! It also seems my solution finds much shorter answers than the jury solution :)
I tried to use polynomial interpolation on the axes independently, what did you do? I dont understand the part of your code where you are taking modulo 50
I exploited this function: W|A plot. It's zero for all x ≤ c and for x > c it satisfies f(x) = 2(x - c). In other words, this function only becomes relevant after position c. Let's denote this function by fc(x). If you pick for your function g(t) = a0 + a1 * f0(t) + a2 * f1(t) + a3 * f2(t) + ..., then this function will satisfy g(0) = a0, g(1) = a0 + 2 * a1, g(2) = a0 + 4 * a1 + 2 * a2, g(3) = a0 + 6 * a1 + 4 * a2 + 2 * a1. If you pick your coefficients ai appropriately, you can reach any even value you want (or equivalently, exclusively odd values if you pick a_0 odd). Since the cirles have at least radius 2, this is sufficient jump into any circle.
I also thought about polynomial interpolation but the fact that you couldn't do division was a bit unfortunate.
EDIT: As a bit of background, the idea for this came from the beautiful identities:
(verify this yourself! hint: consider $a \geq b$ and
separately)
It would be great if you could use these functions directly so you could make the step function max(0, min(1, x - c)), but unfortunately we cannot divide by 2, so this step function would make jumps of size 4. So I dropped the minimum, ending up with f as described above. Then you have to mess around with your coefficients, and poof you have a working solution!
Nice solution :D I'll try to implement this
Не могу не признать, что раунд получился неоправданно тяжёлым для второго дивизиона. В следующий раз буду стараться лучше оценивать сложность задач.
Sorry community, I must accept that this round was too hard for div. 2. I will try to better evaluate the difficulty in the future.
I have 1 suggestion for C: Why do you need to have so many brackets? I don't think it is that hard to write judge that works without those extra brackets, but it makes life of contestants much easier.
The problem is already quite hard, and you're making it much harder for contestants that could come up with some complicated functions but failed to insert brackets correctly.
Задачки явно сложнее, чем обычно. Под конец контеста кажется понял, как решать C (надо же подобрать функцию, чтобы она накрывала все окружности во всех возможных точках даже если радиус 1?)
Как решать D? Ощущения, что там heavy-light декомпозиция? Никогда не писал такие программы, даже не стал пытаться :(
Да, D — heavy-light (Да, тоже никогда не писал:D)
C — не просто функции, а функции от целочисленных аргументов + радиус не может быть 1.
Ok, you should definitely lower Div2 problem difficulty... Problems A and B were excellent. Problem C... i don't even know what to say about problem C. It's difficult to even understand what is asked. Problem D should at least move to most difficult and problem E is for Div1 ...
This is my humble opinion, but i think others will agree.
Что в D кроме HLD?
D was standard HLD. Just the overflows had to be taken care of. But how to approach E?
I think it doesn't need HLD.
May be there are simpler approaches, but what came first to my mind was HLD.
Can you please explain how to solve it without HLD?
How did you approach D? and what is the intended solution of E?
E: (I'm using zero-based index, which is different from problem statement)
This can be solved by dynamic programming with matrix multiplication.
In a nutshell, make a vector V that keeps the number of ways to get to each cell and make a square matrix C such that C*V is the information about 1 second later. And basically keep doing (C^n)*V with some changes on C.
Here is a more detailed solution.
Let f(i, j) = i * M + j. (This maps location (i, j) to an integer, and it's bijective.)
First make a column vector V such that f(i,j)th element has the number of ways to get to (i, j) at some point. Initially, V is filled with zero except f(0,0)th element is 1.(Because we have 1 way to be at (0, 0))
And make a square matrix C whose size is (N*M) x (N*M).
Fill 1 in matrix C such that C*V is going to be a column vector such that f(i,j)th element has the number of ways to get to (i,j) 1 second later. More specifically, for each (i, j), we need to fill C[f(i,j)][f(i',j')] = 1 if you can move from (i',j') from (i,j).
Now to get the information of n seconds later, we just need to calculate (C^n)v. (C^n) can be calculated very fast by using Exponentiation by squaring.
Cats can be handled by changing the elements in C. When a cat shows up at (i, j), every element of f(i,j)th row of C is going to be 0.
Can you explain how to solve it without HLD?
http://codeforces.net/contest/593/submission/14078235
Check it out. :D
Solution without HLD.First observation is that you need to make at most 60 / with numbers >1 to make it 0. I note 1 edges>1 and 0 edges=1.So I want all 1's on path from a to b,if there are more than 60,the answer surely is 0.
So starting from a,b I go to lca and should have a function that gives the first ancestor of x that has 1 to have no more than 60 steps on each query.
The brute force is using disjoint sets.The problem is the updates on edges,but update is of form x[pi] to ci with ci<x[pi].So from a 1 it can be 0 but not reverse,this helps a lot.
Try firstly to do this problem 1D on an array,then it will be similar(just that position x+1 is father(x)).
Complexity O(q*log(max_y)).
If the updates were random,I can do a query in O(60*log^2),does anyone have a better complexity?
System testing please?
lol i wish this contest as unrated
Too hard for me... Only able to solve the first problem.
And failed on the system test..... :(
Что я придумал в D (чисто посмеяться):
На каждый запрос первого типа ищем lca. Теперь с помощью ДО считаем произведение на обоих ветвях пути. Внутри ДО нужно уметь определять середину на отрезке. Допустим, нам пришли вершины l и r, нам известна их высота. Считаем среднюю высоту h. Теперь из всех вершин на заданной высоте h тернарным поиском ищем ту, у которой высота вершины lca между ею и r максимальна (в частности, lca будет равна искомой вершине). Эта вершина и будет серединой отрезка между l и r в ДО.
Для запросов второго типа всё менее интересно.
Асимптотика: O( M * ( log(N) + log^3(N) ) ). Думаю ТЛ.
Ну ты там действительно заугарел)
Написать ДО по Эйлерову обходу?)
Я придумывал решение теми способами, которые знаю)
Maybe stupid question, but how solve A? :)
Try all of the combinations of two letters and check what length of the text we'll have if we take only words with these letters :-)
Count the maximum number of words that can be formed with every pair of letters
I_love_Hoang_Yen didn't solve C :'D and I am expected to?
What is wrong with this approach for B?
Take xi = x1+EPSILON and xf=x2-EPSILON for EPSILON = 1e-7. Find the indices of the lines with the highest value at xi and xf. If these indices are the same, print NO. Else print YES.
Draw two intersecting lines and then draw another one well above them.
seems I miss great contest!
Editorial?
2 solved problems + 2 hacks = 67 place. NICE.
Can codeforces show recent comments at the top instead of bottom of the page. We need to scroll down to find recent comments.
Also it would be best to too negative comment all together as it doesn't serve much purpose on this forum.
Are there any a, b, c such as [[a/b]/c] != [a/(b*c)]?
No. Let
be the remainder of 
after division by 
, so we have 
and 
such that 
. Then 
. Now let 
be the remainder of 
after division by 
, so we have 
and 
such that 
. Note that 
, since 
. Then 
, and since 
, 
. So 
.
After that announcement I decided that HLD was bad idea)
P. S. To be honest I didn't even try to implement it.
The thing I liked the most is "Yes" and "No" were case insensitive. :D
Понять не могу, почему решение 14068268 не легло по времени на взломе с макстестом :) со второй попытки только завалил его (когда сделал, чтобы ответ был YES, а не NO) :)
оно и на 16м тесте почему-то не легло, кто объяснит, ребят? А то я в недоумении что-то :)
UPD: А еще там массив до 10к, тут еще и RE должен вылезти был, нет?
Could have had such a good rating ...
Problem B...Failed System Test...changed int to long long int...Got Accepted :'(
I feel the same way with such stupid mistake. On D i have MAX=1e18+1 instead of MAX=1e18 and that made my program fail system tests.
I miss PrinceOfPersia 's contests :D
excellent contest provider ♥
I wonder how many solutions of problem E fails at this test case:
5 4 10000
1 1 1 i*10000 + 100
There is no restriction in the statement that forbids using this test case, right?
I don't see what is special about this case?
Yes there is nothing special about it. It is just an ordinary maximal test case. For instance, your code with that input, gets TLE on custom test.
You are right. It seems either the test cases are extremely weak, or the constraints and restrictions are misleading. Here's a more extreme version of the worst test case:
5 4 10000
(Followed by 10000 lines, i = line number)
1 1 1 i * 200000
I can pass this in 3 seconds but my implementation is heavily optimized. I'm certain most solutions will fail in this case. I got accepted in 156 ms and that's a joke, considering I can generate test cases quite easily where it takes > 3 seconds.
problem D A Big Trouble I use quick_mul to judge the num is exceed 1E18 or not,and this solution has no accuracy error!But someone may use log function to solve the problem,but we know the double only has 15~16 bits of accuracy,but the problem can have 18 bits,so this solution has no accuracy error! When I submit my solution,I get WA.Just a big data,the answer requires 0,but I output 1.But I think whether my answer is wrong.Because if standard procedure use log,I think may the data is wrong because of accuracy! So does everyone know standard procedure uses which method?
This contest was very difficult, but I must admit I overthink problems like B :( always seeing "geometry" problems like demons ...
If I remember it right, this blog should have gotten nearly 70-80 down votes after the contest ! I think you're not alone with the vision
First round from blue coder, they said
Easy contest gunna be, they said :P
Actually the lower rated the coder, the harder the contest. They are just trying too hard.
Some bug in my code for Problem B Anton and Lines, please, thanks you
my submissions WA on test 24
Just change the variables to long long
Слабые тесты в задаче B. Зашло решение с неправильной идей. Вернее, оно зашло если добавить if( test == 83 ) cout << "No";
Идея: заменяем все прямые на отрезки (y1, y2). Соединяем все отрезки для k >= 0. Причем соединяем их просто вот так: l = min( y1 ), r = max( y2 ). Аналогично для k < 0. После этого смотрим пересекаются ли эти два отрезка. И дополнительно, перед соединением отрезков — отсортируем их и проверим пересекаются ли два соседних между собой.
Легко подобрать тест на котором это решение не работает:
Здесь результирующая прямая (синяя) для k >= 0 явно пересекается с прямой (зелёной) для k < 0, но ответ No, потому что на самом деле есть только точки касания исходных прямых (красные и зелёная) (а их может и не быть совсем).
В тестах есть только один тест на этот случай — 83.
Код
А разве одного теста не хватает, чтобы упало такое решение?
Странно то, что всего один такой тест есть. Тем более в нём всего 4 прямых.
It's so difficult that those whose scores are around 1700 can only solve the first two problems,and the third problem is so difficult that I don't think it's a successful problem.So sad.
Хорошо что я его не писал...
Finally Experted!
hope see you in red ;)
Necroposting may be discouraged by the community, but I trust they'll forgive me for making the very necessary comment that problem C is the most absolutely horrendously disgusting dumpsterfire of a problem in the history of computing, and that the fact alone that there exists a human smart enough to see a solution, yet not smart enough to see the ungodly number of reasons it should have been rejected as a problem idea before being typed is proof enough we do not live in a simulation.
Also the "Incorrect functions" section has a typesetting error in example 3. But I do not recommend anyone dare to fix it, because I am not cruel enough to show such a statement to even my worst enemy, let alone someone trying to be helpful.
That is all--carry on.
it would be funny if they actually corrected the sample