Приветствую сообщество Codeforces.
1 июня 2016 года в 19:35 MSK состоится очередной раунд Codeforces #355 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.
Это мой третий раунд. Надеюсь, он вам понравится.
Большое спасибо Глебу Евстропову (GlebsHP) за помощь в подготовке задач и Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.
Участникам будет предложено пять задач и два часа на их решение.
UPD Разбалловка: 500-1000-1500-2250-2250
UPD Разбор здесь
UPD Поздравляем победителей!
Div. 2
Div. 1
nice and short announcement I think one of the problems is about shortest statement :D Have a nice contest ;) Good Luck For All
Do you have a children's Day today?
As a 8 years old's black_red boy, I must be the king of this contest ((유∀유|||)) .
Are you really 8 years old's boy? Why your profile displays you are in Sichuan university?
Maybe he just want to get the last place in the contribution list by collecting down-votes.
No, you are absolutely wrong.I just say the true things.
Could you do me a favor?
Please close it :\
I think you are not black-red!
You are brown!
What is the meaning of Brown?
brown
I am offensive and I find this brown.
Probably born on leap year, celebrating birthday once in a 4 year, so its 32 years actually
Пора уже Div1 давать.
Не терпится в Div2?
Тогда я пропущу очень редкий див1 раунд и мне будет обидно :(
Ну а на самом деле я считаю, что тот, кто никогда див1 Е не решал во время раунда, не может сам давать див1 раунд.
Good luck everyone! I hope that I'll jump to Div.1 tomorrow and never return back to blue again...
It's pretty much not possible returning back to Div.2 when there is no Div.1 rounds whatsoever ;)
exactly ! :/
good luck tweety :D
Good luck :)
Congrats tweety :)
Almost did it. The only remaining part is not returning back :P
Wish you happy journey in Div1
Don't ever forget us Div 2 people :P
is it rated?
here he comes...
phrasing...boom :)
You know, It's not funny anymore..
I'm still giving them up-votes :)
This joke has been over-used, and you have to come up something new!
Vanya is in the house
Yes, the round is rated :p
This is answer is for those who are gonna ask "Is this rated?"
I am trying to solve problem from your past rounds, but when submit ( 18173020 ) it say Denial of judgement
Is the package for this problem crashed?! what is the problem in my submission?!
UPD the problem fixed.
How come Wild_Hamster's profile says his last visit was 5 days ago when he posted this 11 hours ago?
A Codeforces Round in it's usual Time now that's new :D
This contest is going to begin at 00:35 in china.It is too late, and staying up late is not good for my skin.but I really want to be a blue xiaoai.
Man, I'm in NZ and I have to get up at 4:30 for the rounds
She is a girl
There's a girl who's considering participating in a contest at 00.35 just to earn rating? I don't think so.. :)
In fact, I am a girl.Why do you think a girl doesn't be eager for earning rating?
Oops, I was wrong then! But you can't deny that there aren't many girls who would do such thing. Anyway, good luck for the contest!
@Deemo because of your profile picture , I have always thought that you were a girl
and I had crush on you :v
am I the first man who had crush on you ? :p
Yes, you are the first one that I know about :D I had a similar feeling for dreamoon_love_AA though, so I know how you feel :))
I also thought Deemo is a girl. Then I saw his name...
me too ! oops :D
That's a pity.Hope you have a great advance.
I play it, and feel not good too.
Nice & short announcement . And Hope to have some nice, short & easy to understand problem statement . And all the best to every participants for today's contest .
Let div1 round too. Otherwise, too many fakes will div1 by the participants.
Too bad it clashes with another Yury_Bandarchuk's div2 oriented contest on hackerearth (everybody knows it is held on the 1st of every month).
Not everybody. I didn't know. And I tried to schedule contest in such time, that it doesn't clash with another contests:
May 28 — Codechef&gcj
May 29 — RCC&gcj
May 30 — SRM 691
May 31 — csacademy beta round #6
June 2 — Hourrank.
Hope this round will be my first 4/5. God bless me ^_^
Yea I want that too!
and it's again 3/5 :(
me to...
Do not want 4/5. You should solve at least 5!)
Your previous rounds had all math problems. I hope this time there will be more balance :D
Yes maybe all problems related to data structures. Please no more downvotes I am sorry no data structures only maths.
Why people are against data structures problem?
I love data structures problems.
Yes, I agree with you. Let's hope this time around, we get some nice problems of algorithmic nature. After all, this is Codeforces, not IMO.
The email I got said that this was going to be 6 problems in 2.5 hours. Is it 5 problems in 2 hours or 6 problems in 2.5 hours?
Lots of math problems are coming I guess :)
Let's hope lots of algorithmic problems are coming.
Let's hope lots of problems are coming.
Five problems are coming.
ok then let's hope that 5 algorithmic problems are coming.
Winter is coming
Ok, then hold the door!
Let's hope we can learn new things from this contest :)
Not Lots of Problem, Maximam 5 Problems :)
You are right Lord Commander :D
Wild_Hamster interesting profile picture :D
Recursion :)
Any update about score distribution? Or is it standard?
what about score distribution ?
Links to hack submissions do not open in >ten minutes.
Omg, I'm so stuck on C. Thanks god it is not rated round for me.
Thanks very much for the great round! In my opinion, the only criticism is that the difficulty gap between C and D was too large.
How to solve D? Obvious DP gives TL 19.
I get TLE on 19 too, and waste the rest time dealing with this, still can't solve it
I too got TL on 19th case by dp.
I was thinking to sort the elements of each type according to their dp value. while traversing we could stop beforehand if it is guaranteed that the other elements would be more expensive.
I don't know if it would pass or not. But I didn't get any time to implement that.
Please share your approach if it worked.
I got TL on 19 too, and I tried to improve my solution exactly as you wrote — unfortunately I was in a hurry and got WA on 10 due to some mistake. But I believe it should be good enough.
I tried after the contest got over. Still stuck on 19th case
This was my solution during the contest but it was TLE as well :)
I was too slow to code it, and never coded Dijkstra before. But my approach would've been making a directed graph with starting point having edges to all 1's, all 1's having edges to all 2's etc. and then do Dijkstra from start to P, that should work right?
That would still get a TLE as the number of edges in the graph is too high.
Nope, it won't work.
I am using a similar approach as yours, the limit will be the case where p = 3 and there are 45000 elements with p = 1 and 45000 elements with p = 2, in this case it need >2s to finish so it will be TLE. To speed up the algorithm, keep the points with p = x grouped by their x-coordinate and y-coordinate respectively, then for each point with p = x + 1, we dont need to traverse all of the points with p = x, we can traverse each column and each row and find the best one using binary search, so the total time will be O(m*n*max(m,n)logn)
Are 99% of hacks on Div2B are of integer overflow?
Yes. :) That is how I got my 5 hacks.
that's why i implemented it in python.
Waiting for my D to fail...
How to solve D faster then O(p*(mn)^2)?
I wrote solution in O(n*m*n*log(m)). But it's not fast enough :(
Dijkstra?
Segment tree on each row to find minimal value
Actually, you only need to keep track on at most one value for each row.
Can you explain your solution?
Why Velter? Your solution is fast enough to pass the final test :|
It's a good question :D But TLE on 16 pretest
no. my solution is olso O(n*m*n*log(m)) add it got accepted CODE
I had a solution with time complexity O(p*(n*m)), but it failed at pretest :(
I think I got O((mn)^2) by just finding differences between n+1 key and n key, still not enough (for Python at least, I think 45000**2 might be OK for C++)
It won't be enough even for C#/Java/C++.
Even for magic, 'cos 300^4 is 81*10^8
I think you solution is actually O(n^3) ,just like mine, but this is too slow even in c++. I get TLE in case 19 too.
N^3 should pass easily in like 100ms on worst case. So probably it is not N^3.
I think the worst case is p = n = m = 300, and 300 chest for each type. But it's just intuition, Maybe case 19 is something else
It depends on algo used.
For some algos worst case will be p = n = m = 300, 44851 chests of two types and 1 chest of every other.
44851 chests of two types you are right, I didn't notice this case..
Worst case is when n = m = 300, and p is 4-5, so it's 20k * 20k * [4, 5] > 1.6kkk
you are right, I'm too simple
I think I missed D by seconds!
I hope my solution doesn't pass. I was taking the limits small.
I was getting TLE on 19th case. How did you manage that?
So uh, how to solve D? I was trying to think of DP but couldn't.
IMO , for a point you need not check every Other point with value 1 greater. Check all the rows and columns that form a border across it!
DP + Square Root decomposition
In the optimal path, once you have collected the first k keys, you should move to a square to collect the k + 1th key. Thus we can divide the entire matrix into layers where ith layer consists of the co-ordinates of the matrix where such that a[x][y] = i.
Maintain a value for each of these points -> the minimum distance traveled to reach it.
Now we need to do transition from layer i to layer i+1. A brute force implementation for transition could take O((nm)2) time. Thus we take two cases -> If the size of the previous layer is greater than (nm)0.5 and otherwise. If it is smaller than (nm)0.5 we can do bruteforce, else we do a BFS with careful book keeping. Overall complexity O((nm)1.5)
Hi, sorry if this is a stupid question, but what exactly are we doing in the BFS. I mean if we're doing BFS to find cells of the next layer wouldn't it still be wouldn't the BFS still be O(nm)? I read the editorial and it uses the same approach but I don't understand it.
A BFS from layer i to layer j will take O(nm), but you only do it if layer i is large (larger than sqrt(nm)). Since the total number of chests is nm, you can have at most sqrt(nm) layers with size sqrt(nm).
O(m * n * m * log(m * n)) with list + binary search and a little lucky!! :D :D
Problem C was very hard to understand. But B was hackable so I liked the contest
I hacked by you :( stupid mistake
Yup it was..i misunderstood the statement and took me a while to solve it.
I was constantly getting wrong answer on pretest 4. Any possible corner cases? I thought of all possible scenarios, could not find anything :(
same here.
Test case 4 is 5 5 5 4 2 1 2 3 3 4 4 2 2 3 4 1 2 4 2 1 5 4 2 4 3 1 1 2 If we start with 4 key then we can straightaway go to key number 5 with 5 moves!! Why is the answer 9 then?
You must go from (1, 1) to key 1 -> 2 ->... -> p ;) ;)
I WA in pretest 4 and after that I read threads again: "All key 1 open" (not (1,1))
почему мой код не взялся на проверку? я отправил когда было 3 сек до конца. пока обновлялось, время кончилось, и моё решение не взяли на проверку.
Почему этот генератор теста для B получает "FAIL Expected EOLN (stdin)"?
Problem D: I have Dijkstra in O(mlogn) approach based on std::set which don't passes 19th pretest. Starting vertex is cell of P type. Please any help, comments about my owful code 18199256 or your solutions for this problem.
The number of edges is very high, dijkstra is too slow.
D seems like some pro shit. When's the tutorial getting posted?
no matter how much i tried it got TLE
pro shit seems required
Basic ideas of D was pretty simple, you can solve for rows and cols independently.
EDIT : this is wrong.
Posted
What am I doing wrong at problem C?
https://ideone.com/fOMtB2
Your line with pow is incorrect. Take a look at Editorial
Nice round, I have already failed C in system test in the last 3 rounds, hope this time I can be lucky :D
I failed my B this time T.T
How the hell there are more submission for D than E?
that feel when didn't even get to read E because I was stuck on D. :(
I really hate when I miss to notice integer overflow, then get hacked 10 minutes before contest, after which I have to resubmit, thus losing 350 points. The only good thing is that after this I managed to hack one other solution :) so I got 100 points back
It's better than not getting hacked at all and never realizing it :/
You're right, but still it is better to notice overflow as you write the solution, not 1:30hrs later
Annoying how a simple overflow can change my ranking from 150 to 1000
if D turns out to be simple i'm going to shit brix
I can't understand C
is there anyone that explain for me?
i spend most time to understand it..
You get very long number in input. You should translate it in binary representation (6 bits per char in input, total max of 600000 bits), lets call it A.
After that you should eval how many unique pairs of (X, Y) exists, so that X & Y == A. Where & is binary AND.
Find & of all pair of values from 0 to 63 and then calculate answer for each character accordingly. Submission
Same here, i couldn't understand it until the last 15 minutes, and got Accepted in the end :D
In D i was misunderstanding that it has the (1,1) chest initially.That passed three samples....TAT..
*chest
You can edit your comments.
Thank you. :P
Same here. I tried my effort to find the nearest p+1 in eight directions for each p just like Manhattan spanning tree, submitted just before contest ended, and got WA on test 4 :(
UPD: It seems my solution doesn't work, which got WA on test 14 :(
There will be some mistakes? I thought that the proof of Mht mst based on the points were not in order. But in this problem the points are in a specific order.
Of course it is incorrect, which would fail when the optimal path is on a straight line.
I tried the nearest 200 points for each p , ans I got AC , I think perhaps you should try more points :)
С НЕТЕРПЕНИЕМ ЖДУ ОБНОВЛЕНИЯ РЕЙТИНГА)))))
NIET
D зашла с таким хаком: пишем наивную динамику, но для каждого значения x( ≤ p) оставляем 5К ячеек с наименьшим значением динамики. Соответственно для каждого x будет не больше 50002, что вполне заходит по ТЛ. Такой хак как-то можно сломать? http://codeforces.com/contest/677/submission/18200340
Я тоже такое решение написал, но вместо 5000 хранил 100(WA 26).
клетка (0,0) — сундук 1
клетка (0,2) — сундук 3
правый нижний квадрат 75*75 заполнен тройками
клетка (200,200) — сундук 4
Все остальное — двойки
Edit: Это если динамика начинается с сундука p и идет вниз, для обратного порядка пример легко построить аналогично
How to solve problem C?
Realize that.
1 & 1 = 1 //One way to get 1
1 & 0 = 0, 0 & 1 = 0, 0 & 0 = 0//Three ways to get 0
For the pair of strings to find a and b Lets understand that if a&b=1 , then there would be 1 in both. For a&b = 0, it can happen in three ways 00 ,01,10. As number is less than 64 , it can be represented with 6 bits. So you should check the total number of zeros in every number of 6th bit representation. So ans = 3^tot.
First u need precalc all the possible results, and count it in a map(or vector) Finally, multiply all the values (mod 10^9+7) example:
s = xyzw
ans = (m[x]*m[y]*m[z]*m[w])mod (10^9+7)
18194600
I love the contest! Surprisingly most of the problems have a simple way to solve :D.
Oh my god your username is the GREATEST. LOL
Correct me if I'm wrong.
Task E: nothing prohibits non-positive d (it says three integers, not positive integers). With non-positive d set of items under given constraints is empty. So, technically, answer for all zeroes must be one and not zero?
My solution that prints 0 passed, and I think some solutions that printed 1 failed, seems not fair if I'm right =)
Problem B says, that each second Vanya does the following:
1) If there is at least one piece of potato remaining, Vanya puts them in the processor one by one, until there is not enough space for the next piece.
2) Processor smashes k centimeters of potato (or just everything that is inside).
So at each second Vanya checks if the next piece can be accommodated. Most of the solutions that I saw, first add whatever can be accommodated, and if at i_th index, ar[i] + remainingAmount > h, they add to the answer remainingAmount/k. But it is also possible that after some seconds that is less than remainingAmount/k, we get enough space to accomodate ar_i. It is clearly given that Vanya does the above two mentioned things each second. Do both of these solutions give same answer? Am I missing something?
Can you please explain the time complexity of problem D?
How do you people solve problem E?
I thought 10003 divided by a good constant is just fine for three seconds, but my initial attempt took 2x more. Eventually, I managed to squeeze the O(n3) solution into the time limit. Perhaps it's even easier with a superior optimizing compiler such as GCC.
For each center binary search the maximal radius such that you don't pick up any zeroes. Count the number of 2's and 3's in a cross with this radius. Use partial sums to quickly get number of 0's, 2's and 3's in a cross.
Thanks. That's
and not much more code than O(n3) with the 45 degree rotation — nice!
I will not use int anymore, I will write all my future solutions using long. this is the second time I fail system test because of using int. is there any disadvantage of using long?
Memory Limit
Multiply operation is a little slower than int.
#fastreading
2016-06-01 19:35:59
Shouldn't've submitted much later :P
that's fantastic , I hope once I can submit one like this ( and get it AC ofcourse )
I think that D sucks a lot. The time limit was chosen very badly. Some solutions with the same complexity: O(n*m*max(n,m)*log(n*m)) passed and some failed because of that.
Besides author provided theoretically strong pretests. People got busy trying to improve their solution as it was getting TLE on pretests. It created an impression that the pretests are strong in terms of performance and once you pass them you should just worry about the correctness.
Surprisingly I spent some time optimizing my solution just to discover that it was failed because of tle in the final tests.
Either time limit should be higher — 3 seconds or pretests should be weaker so that nobody wastes their time improving something which was going to fail anyway.
I didn't analyse many solutions and you may be right about adjusting TL. But, I don't agree about pretests. It's awesome that pretests were strong and it should help many people. People with slow codes can check their solutions with Custom Invocation anyway. So, in general they shouldn't do it not to waste their time? It's risky to implement complexity which won't obviously pass and one must take it into consideration. I don't see why telling someone "hey, your solution is wrong" is bad. I know that later there is info "hey, your solution may be OK because passed pretests" but it doesn't guarantee anything.
I think that I was one optimization away from the acc, so if the pretests were stronger it would be also ok.
The problem is that they were chosen in such a way, that they were engaging people in solving this problem. Contestants were spending time trying to pass pretests instead of solving other tasks. It was a false help. If they were stronger it would be a real help. If they were weaker, nobody would complain about it as passing pretests guarantees you nothing. But also nobody would bother spending so much time on this task.
Besides we are speaking about n*m*max(n,m) (obviously pass?) and n*m*max(n,m)log(n*m). In my opinion both should pass easily. If somebody is trying to differentiate solutions worse by factor of log it means that he wasn't confident that the problem was difficult and interesting enough, so he made time limit more restrictive.
It was a false help for some participants, a useful help for others (I had many things wrong and catched them one by one, thanks to pretests). That being said, I see your point now. But I think it's hard to adjust pretests so perfectly.
Unfortunately, if you want to allow O(n3·log(n)) to pass easily, then it may also allow squeezed O(n4) to pass. I think that the chosen constraints were ok — there is intended O(n3) (passes easily) and one may risk and write O(n3·log(n)) carefully, to also get AC. Fine for me. One may get TLE a few times but in the long run it isn't a big deal and I don't see a better solution.
Okay Wild_Hamster, you beat me this time, well done!
it's your 2nd contest , take it easy , it took me 55 contests to get here and you just did in 2 , you're a monster hahaha , div1 is waiting for you next week good luck .
Thank to all for such contest. It was really unexpected thing for me to be in top-10. :D
I was writing it normally, solved ABC, then got TL #19 on D. Then I thought: "I need to get maximum points here" and started hacking. :D When I opened my room there already was a guy with 1 hack. After 1 refresh I saw +2 near him. Then +3 were near me. :D And when I only refreshed my page, it said "Sorry, your balance is X, you can't surf internet anymore". As you already understood, X is some negative number. :D I ran from home to nearest terminal, which is not near my home, :D put cash for my dear internet provider, came back, made 2 more hacks, optimized my TLed D solution in some shitty way and it passed systests. :D
Try to tell this story better and you can pick up girls with it.
Savage :D
Perfectly right submission http://codeforces.com/contest/677/submission/18209483 calculating 3^n. WTF test 9 has no input. I was lied. they said length was more than 1? In contest solved two problems but shouldve used long for t in 2B but i used int for a perfectly correct answer :(
The input is a lots of underscores ('_'). You should have processed the input char by char instead of using slow BigInteger class.
oh great thanks.
is there anyone that explain to me D?
testcase #4
5 5 5
4 2 1 2 3
3 4 4 2 2
3 4 1 2 4
2 1 5 4 2
4 3 1 1 2
why answer is 9?
what i understand is 2: (1,2) -> 3: (2,1) -> 4: (2,2) -> 5: (4,3) thus ans = 7
you need to go to 1 at (1,3) first
Congratulations to Div. 2 user fake_fake who wins the round! 1st place from the 3rd try! Nice progress, man...