Всем привет!
29 марта в 19:05 MSK состоится рейтинговый Codeforces Round #407.
Задачи готовили я — Игорь Баренблат, Станислав giraffeh Томаш и Антон arsijo Цыпко. Большое спасибо Ивану Fekete Фекете, Адальберту Adalbert Макаровичу, Роману chakred_namor Деркачу, Владиславу winger Исенбаеву и Александру AlexFetisov Фетисову за тестирование, Николаю KAN Калинину за помощь в подготовке раунда, а также Михаилу MikeMirzayanov Мирзаянову за системы Codeforces и Polygon.
Как всегда участникам будет предложено по пять задач и два часа на их решение. Разбалловка будет объявлена ближе к началу раунда.
Надеемся каждый найдет для себя интересную задачу. Всем успешного раунда и повышения в рейтинге!
Разбалловка:
Div2: 500-1000-1500-2250-2500
Div1: 500-1250-1500-2000-2250
UPD. Разбор опубликован.
Поздравляем победителей:
Div.1:
Div.2:
Nowadays number of problem setters+tester of each contests are more than the number of problems :D That's cool. Thanks to all the problem setters for giving their important time in problem setting for us B-)
Yeah! you're right!
My Boy !!! They are not setters ; they are Testers
so, 3 setters and 5 testers? That's also good.
Contestant's are 7000+.... That's awesome
4056 + 461
Hope to have interesting problems and good problem description.
wish high rating for all
now you can see my pokerface
I actually see it is a see-saw and your art gives me an impression that rating have to be balanced in a round, therefore "wish high rating for all" is an illusion.
:|
:|
How many problems？
"As usual, contestants will have 2 hours to solve 5 problems."
thanks！i havn't read the instruction carefully
It already not usually
who is maria ivanova Barichek ?
The most beautiful girl in the world)
Sorry, but Meghana is the most beautiful girl in the world :)
I_love_Tanya_Romanova
All of you are wrong.
I agree.
Thanks!
How about my UNCLES? :'3
All of you are wrong, Rem is the best waifu. /s
but dude! equi . And (to round 407) LetsDoThis
I_Love_Equinox
I_Love_Sasha_Golovach
I will be in top 1000 this contest!
Well I m new in programming contests ... Can you plz tell me that in in which Division should I register.....It will be great if you can give some tips to me .
If you are new, you should register in Div.2
Rating prediction: div1 div2
Extensions:
Have fun & high rating:)
Hey, Can you Github it? and share the link, please?
It's already on github. Also you could read blog on cf about it.
Hey, What's the matter with accuracy? Why not accurate when you know the results?
The results of this predictor are very much accurate.
Gotta try it from now, lets see how today's contest rolls up. all the best everyone.
Is a2oj down?
I believe I can fly.
I BELIEVE, I CAN KICK YOUR ASS.
you can‘t kick my son’s ASS！
you are not my father
You can't kick my grandson's ASS!!
Did I offend you? Why do you want to kick my ass? Who are you?
I'm you missing Biological father！！！ CALL ME FATHER
DID I OFFEND YOU? HOW CAN YOU FLY?
be quiet please, if you can`t write sth clever
haha, best reply ever :D
Good luck in the competition! Here's a little song to hype y'all up!
Beautiful program
Please run for me.
I've tried you in BASIC,
FORTRAN and C.
Beautiful program,
You've errors galore.
And each time I run you,
You're swapped out of core.
You are good in programming (as I see your color) but sorry to say, not in literature.
В задаче D есть ограничение на кол-во прямых?
Полагаю, это число следует из ограничений на тест-взлом (n, m ≤ 104)
Problems in CSAcademy are getting better than DIV2 CF Rounds. Long Problems, uneven difficulty levels.
Is it at all possible that problem E is just named "New task" because it is a placeholder name :P?
Hack page not loading... Can someone please check?
Problem with the hack page :/
Today we are going to witness the fastest system tests ever .
Hi div2 :V
RIP RATINGS...
what's test #14 in B Div2?
What is pretest 14 in div2 B ? Your text to link here... What is wrong in my solution?
Try this:
5 0 4 1
1
I think it isnot this case because my pro can cover this
inf?
ans is "inf" ?
Ans is "0". Because Masha will stop writing immediately if |bi| > L.
That's exactly why I got WA on the first submission.
Now I got it.. Thanks
my sol is giving correct answer my solution
Ans is infinity.
Because 5 0 0 0 0 0 ... Now 0 is no=t in list...So ans is inf
it think ans is 0 i thought it was inf before i changed it and passed that test and the statement was confusing.
she will firstly write 5 that's bigger than l so she stop and write no number so answer is 0
I want to know too
i passed it by putting
if(abs(b1) >l) cout << 0 <<endl;
at the beginning
thank you , it must be this case
How come? if b1=0 and q=0 then the answer should be infinite!!
the condition has nothing to do with q it just compares b1 and L and if b1 =0 the condition will be false because L is always bigger than 0
if q==-1 && Math.abs(b1)>l then ans = 0; i think this is the case .
I don't know actually, but this case troubled me a lot today :-/ somehow, passed it in 11th submission.
How to solve Div2B. Got stuck for 1 hr.
check for exception cases — q = -1,0,1 and b1 = 0. for others apply naive method.
I got hacked once because of not putting b1=0 case seperately.
@mizuki instead of checking exception cases, we can count iterations here is my code (maybe it will fail in system test):
I did that ..can you check my submission?
i used that but i had wrong answer on pretest 9 .. could some one tell me why ? i thought i did it correctly i did all the cases ?
I tried for q=0,1,-1 and b1 = 0. As well as same way as of iterations count but got pretest 9 WA :(
Just use binary search instead for checking if bi is 'bad'.
or a map :)
What could be Problem B test 14 ?
I think it was abs(b1) > L.
I considered that case too along with q==-1 but still got WA
How to solve C?
The answer doesn't exceed 1000. But I don't know how to prove it.
If there exists a[i] == n, answer is 1.
Else if we don't have both a[i] < n and a[i] > n, answer is -1.
Else we have some a[i] == n — x and a[j] == n + y. Then we can take y bottles of type i and x bottles of type j. x + y <= 1000.
This >.<
me too :/
Mine is wrong too :(
Masha writes all progression terms one by one onto the board (including repetitive) while condition |bi| ≤ l is satisfied (|x| means absolute value of x).
So if bi>L u don't have to check for 0 too when common ratio is 0.
fail 4 times, which case did I missed?
Hacks, Hacks everywhere 8-) <3
Is Div1 D solvable by Java? I think the solution needs almost 300000 queries. An Educational Codeforces Round held some month ago has such problem (many queries needed) and no one can solve by Java since flush() is time-consuming.
Codeforces and ACM want people to code in C++, thats why I changed from java to C++ :(
If so, statement must not advice for Java or other languages' flush.
Well I should be doing 1.8*10^5 if that matters. Isn't there another way to make flush?
we can solve it in at most 100000 steps.
fix... my estimation is wrong before...
Can somebody tell, if for div1B suggestion, that 2 used only once edges are neighbour edges, is right?
Any two self loops can also be single edges.
Also any normal edge(non self loop) with any self loop can also form a pair.
is that only 2 cases? self-loops and neighbour edges?
1- pair of self-loops
2- self-loop and edge
3- pair of edges that share an endpoint
Can you please tell me a case where this would go wrong:
sz[i] tells the number of nodes adjacent to node i (not including i even if there is a self loop)
n is the number of edges which are not self loops..
As I said, pairs of self-loop's should be counted
Sorry I don't understand this very statement pairs of self-loop's...
for example:
2 3
1 1
2 2
1 2
My program gives 2, which I think is the right answer too.
Sorry if all this sounds really stupid..
Answer is 3. You can select any 2 of the 3 edges.
Using the two self-loops once the path is 1->1->2->2->1
Thanks.. got it :)
So something like this?
in this test the answer is 3, because you should also count this pair: (first edge,second edge)
I forgot second case anyway, so I got WA. But can you prove that only needed are these three cases ?
Eulerian path/cycle exist if the graph is connected (edge-wise) and degree of all nodes are even except for 0 or 2 nodes are odd.
so if all edges are doubled all degrees will be even, if a pair of edges don't share an endpoint then they will make 4 odd nodes
Fantastic proof, thanks !
I was so close to solve this :)
I did the same. Wrong Answer on pretest 18.
Edit: I messed up in checking whether all edges are connected or not.
I did the same solution but I am getting WA on pretest 5 :/
Not necessarily, for example two random self-loops work.
Nope, check the graph 1->2, 2->3, 3->3, and you can use edges 1-2 and 3-3 only once by going 1-2-3-3-2-1.
Awesome problem set! problems was tricky though xD
Pretty nice contest. My most favorite problem is Div2-D. Though, I don't like Div2-B.
Btw, how to solve Div2-E? Is it some kind of DP?
UDP: I don't know if the words "geometric" and "depression" in Div2-B title are intended puns or not.
Solve the multivariate linear indeterminate equation? I guess...
The crux here is to notice that all we need is the sum of (signed) distances of the cokes that we include to our desired amount is zero.
Then do we something like Knapsack's DP, except we notice that an optimal solution could be arranged so that we never stray beyond [0, 1000], supposing that we start at the desired amount and then add/subtract the distances from there.
To make it run faster, we implement it using BFS (store the reachable ones in an array that indicated how many steps needed)
Div2 B take a lot of time debugging.
"14" it became my worst number because of problem B
aoso to me
Please check this test: 2 0 1 1 0
Announcement:
are announcements supposed to give hints or only to clarify the statement?
Guess they didn't want people hacking
It is in pretest 18 I think.
Actually, the statement is still incorrect:
Ok then announcement was needed, but I still think it gave hint to some people :D
And what about div2 B pretest 10?
How to solve Div2 A ?
In Div1 C, I really tried hard to hack O(N^3) solutions. But the CF evaluation server was too fast.. They all worked within 900 ms.
What was the expected solution?
My solution is O(N^2) with BFS.
Wow how did you solve ?
We are to pick some of (a[i]-n) such that the sum of them is zero. We don't need to go to a state greater than 1000 or less than -1000, because for all i, |a[i]-n| <= 1000 and we should make zero. Therefore, BFS with 2001 nodes ([-1000, 1000]) will be enough.
Which test case did you use to hack? As I feel intuitively that if you have a many types of a[i] the answer can be found quite fast and if you have a small number of different a[i] each iteration will have a small number of operations.
Almost all solutions that I tried to hack first check if there is n. If not, they divide numbers into two groups, and calculate available sums for each group with time complexity O(N^3). No matter what numbers come, they iterate full O(N^3) loop. So I handcopied them to custom invocation and just tried K = 1000000.
what the data of DIV 2 B test 8?
please read this : http://codeforces.com/blog/entry/51309
is it means the test data is wrong?
Problem B — Masha and geometric depression It looks like not only geometric who has depression
My Status Right now
I tried to hack a solution with this code
for problem A in Div.2
include
using namespace std; int main() { cout<<100000<<" "<<1<<endl; for(long long i=1;i<=100000;i++) { cout<<10000<<" "; } cout<<endl; }
It says invalid input.Why is it so?
[DELETED]
*Thanks for the round
You can't solve it,so you decide that it isn't your fault?
Thanks for the awesome round. I am ok with this round. Sorry for earlier comments.
Wrong ideas? I don't understand. If you don't know how to solve it, you can look at programme that have passed
int main() { cout<<100000<<" "<<1<<endl; for(long long i=1;i<=100000;i++) { cout<<10000<<" "; } cout<<endl; }
Used this code to Hack a Div.2 A...why do i get invalid?
last element should not be followed be a space.
I made a hacking attempt with similar script expecting TLE. But the solution passed in 436ms. I guess that was because the operations were small (x++)
I want to see, how many DIV2C solutions will fail due to integer overflow. I managed to hack 4 people in my room alone, who used
int ans=0;. My hack testCorrect answer:
3000000000DIV2 B if |b1|>l masha will stop,but you do not say it!
so if |b1|>l && q=0 masha can write 0 ,i think the answer is "inf"! But your question is "0", you did not give me a clear meaning! sorry my english is poor.
Can I already post "start systests" meme?
How to solve C ? I used two accumulative arrays where in the first array l=1 and in the second array l=2 (r=n in both arrays), then i looked for max range sum of both arrays. this is supposed to be O(n) but still gives TLE on pretest 10. help?
For Div 2 B,
Whats the correct answer for :
5 0 4 1
5
Main confusion:
Does abs(b)<=l check happen even if b is a bad number?
0
Mine gives 0
it should be "inf"
It will be 0.. But if generating doesn't stop, It will be "inf".
you can write down “0” endless，,so it should be "inf"
You should immediately stop writing when |bi| > l
It should be 0.
0 because 5 > 4, so we never enter the while loop.
0, because of condition b(i) <= l
It should be 0 since initially abs(b1)>l is not satisfied.
So just a side note, not like the statement says the opposite? Really, why didn't you fix that? "At first, he decided to visit all the cities of his motherland — Uzhlyandia." or any other sentence does not even suggest that he may not want to visit all cities, does it?
Also, don't you guys think that "Boy thinks a path is good if the path goes over m - 2 roads twice, and over the other 2 exactly once." isn't well-defined for M=1? I made them tell me that the answer is 0 for M=1 on my third try.
Well u kinda cant walk -1 edge, so.. Kappa. Agreed, statements are awful
Yup, also "the other 2" suggests there are at least two edges. Not only did it take me three tries to convince them to explain the situation with M=1, but they didn't even make an announcement after that...
The English in that statement was also very sloppy at times.
I am in doubt, was their any DIV2 round today?
Yes, this contest was for both DIV1 and DIV2
Спасибо за задачи :) до встречи на всеукре)
can some one help me find out what is the difference between these two codes:
and this:
What I've noticed, is that the second code adds the remainder to the answer before dividing it. (wrong)
The first one is adding the remainder after dividing, which is the right way.
ceilwill return for example51in case that the computer calculates100.0 / 2.0as50.00000000000000000001... floating point arithmetics are calculated with some machine specified fixed precision...thanks for the reply so you mean that the second one is correct?
Yes.
Division by 2 does not have such flaw since 2 has exact representation. It will break only if the numerator is already not exact, which for integers means it must be more than 253.
but in case of division by k this has a problem.(based on what others are saying)
I remember I tested it on two integers less than 100 and it failed. I don't exactly remember the numbers.
That is possible only if one of the numbers was already calculated with an error (for example, if you used the
powfunction).Here is an old but good TopCoder tutorial by misof to learn about integers and reals representation.
http://codeforces.com/contest/789/submission/25922219 Отличные претесты :)
TFW you finish debugging 30 seconds after the round ends
feels bad man
Can someone tell differences between these codes for Div 2 A?
First one passed pretests and second didn't.
Code 1
Code 2.
same here.
I think there might be some precision issue involving doubles.I kept on getting WA on pretest 6.
I think there are some issue in Problem Div2 B. For this reason system test is delayed.
Started..
Here we go :D
Systest is still pending, because even the setters get WA 14 on Div2B :)
С упала только потому, что неправильно обработал случай с n = 0(подумал, что в таком случае нам вообще не надо покупать колу и выводил 0). Чо ж вы в семплы его не включили или не написали в условии жирным, что изначально у нас НОЛЬ ЛИТРОВ КОЛЫ И ГАЗА СООТВЕТСТВЕННО. Формально косяк мой, но это же не совсем крайний случай и многие его учли(и я тоже), просто я неверно его обработал.
Div2.B... 13 is not unlucky number. now, 14 is unlucky number.
Div2 Problem B Case #14: 123 0 21 4 543453 -123 6 1424
Accepted. But A failed :-/
System test are over but div2 B test doesn't seem correct. 14 test case's ans should be inf but it shows 0
Here b1>l. Hence, answer should be 0.
No. 0 is correct. Because b<l.
Div2 B : 1221 pretests passed -> 771 AC ..
May God be with us !!
Div2 B, WA on main test 43 opps :( :(
even though i am not the only one who dissapointed with problem B, but i do appreciate your effort for giving your time to us for making this contest, i'll wait for your next contest of course with a better problem to be solved, graciass
problem B
why output of this case is 0 123 0 21 4 543453 -123 6 1424
it must be "inf" because b1 = 123 will not be printed because it's invalid b2 = 0 will be printed because it's valid b3 = 0 will be printed because it's valid . . . infinity
l is smaller than 123? The process stops at b1. Beware of the difference between "skip" and "stop"
123 > 21 ... 0
Автокомментарий: текст был обновлен пользователем Barichek (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by Barichek (previous revision, new revision, compare).
editorial link is broken edit: fixed
http://codeforces.com/blog/entry/51312
Here's the fixed link
I don't why but there is some issue with the challenging system near the end of the contenst. It seems that my hack page keeps refreshing and it failed to load the hack interface so I cannot hack other's solution...
Surprisingly after I change from chrome to firefox it suddenly works...Don't know why there is a difference between firefox and chrome...
Happiness is getting into Deep Blue.
Congratulations!
System test data for Div-2 problem A are weak. They should test some hack cases too.
Here is interesting submission of Div2 E/Div1 C. It seems to be O(5004) with some heuristics. I try to find solution using one, two or three types if there is such. If no, then comes what should be O(5004) DP. But it passes systests.
Can anyone take a look at THIS submission please? This code gives correct output of the test case 15 on my compiler but wrong ans on codeforces' compiler. Help would be much appreciated. Input case : 3 2 115 16 24 48 12 96 3 720031148 -367712651 -838596957 558177735 -963046495 -313322487 -465018432 -618984128 -607173835 144854086 178041956 .Output should be '1' but on cf it gives me '3'.
Anyone please?? Atleast you can run the code on your compiler with that input and let me know if you get the wrong ans or correct ans. :/
Man !! you don't make your code easy to read.. do you...
For part A : I initially submitted 25910962 with variables declared globally and I got wrong answer in test 5. But after that I declared the variables inside the int main() and the solution 25923127 was accepted. Can someone explain it to me how this makes a difference?
Compare
ll w[10000];toll w[n];. First one fails, becausen<=10^5, but you declare the size as10^4For B div 2, shouldn't the following test case output in "0" instead of "inf"?
because b1 = B, and |b1| > L, she shouldn't write anything on the blackboard.
But I might've missed something. The hack attempt is here: http://codeforces.com/contest/789/hacks/312464
Thanks in advance.
Ah, it is my blunder. I misread "expected output" as my own output.
Kindly ignore above question.
In Div2 Prob B test case 14 — 123 0 21 4 543453 -123 6 1424 The output should be inf because First 123 would not be written on the board as it is greater then 21 but 0 should be written as its not present in the m numbers ,So it should have been written every time. But why is the answer 0..? Answer should have been inf
Masha writes all progression terms one by one onto the board (including repetitive) WHILE condition |bi| ≤ l is satisfied. So if |bi| > l she will stop.
Thankyou :) Got it.
No. The question clearly states that the number won't be written if it's absolute value is greater than 'L' and the loop would break. In this case, 123>21. So even that would never be written.
The problem description state that she will write as long as the condition of |bi| <= L holds.
On the test case 14, b1 = 123 is already greater than 21, hence the girl will stop there.
There is a difference between skipping a number (because the number exists in bad number set) and stop writing (because the current number already exceed the given bound).
Thanks for the great contest!
Very clear description and interesting solutions. Unfortunately, I spent half of the time of the contest trying to figure out why my solution for problem C did not work? In the end, a friend told me that the function f(l, r) = sum_{i=l}^{r — 1} |a[i] — a[i+1]| * (-1)^i-l while I thought it is f(l, r) = sum_{i=l}^{r — 1} |a[i] — a[i+1]| * (-1)^i-1. Anybody else had the same problem?
I used the following generator code to hack a solution 25904282 for Problem Div2A:
Unfortunately, the attempt became unsuccessful as the solution produced the output in 998 ms.
Later during the system test, the same solution gave a TLE on the exact same test case — Test Case #27 :(
It's bad idea to hack solutions where only basic addition and subtraction operations are performed in loops.
See this solution. It is performing 10^14 operations still system test passed.
Lol no, this is compiler optimization :D
I have an interesting solution for div1 D and maybe it need only O(n) queries.
First we choose a number number G less than
, probably 
(M is the coordinate range and n is the number of lines). And we can random several times to find a point a = (x, y) such that 
.
Then, for vertical lines, we query all the point (x + kG, y) which is in the coordinate range. And we can find several lines. But if there are many lines which are very close, we may only find out some of them.
So, the next step, we need to find out the remaining lines. If the dis between two adjacent lines is larger than 2G, then there are no lines between them. Otherwise, we can search between these two lines. Each time we query the midpoint of the search range, if we get a new line, then we try to search both sides and otherwise, exit.
We can find out the horizontal lines analogously.
This is my code 25939395.
During the contest, I made some stupid mistakes and failed to pass it. Sad story.
My solution (25925383) also only uses O(n) queries and is very simple.