Привет, Codeforces!
Завтра, 15 ноября 2016 в 19:35 (время московское) состоится очередной Codeforces раунд для участников из второго дивизиона. Как обычно, участники из первого дивизиона смогут поучаствовать вне конкурса.
Автор контеста — я (gepardo). Это мой первый раунд, и, надеюсь, не последний. Огромное спасибо Глебу Евстропову (GlebsHP) за помощь в подготовке контеста, Андрею Календарову (Andreikkaa) за тестирование раунда и Михаилу Мирзаянову (MikeMirzayanov) за великолепные платформы Codeforces и Polygon.
Как обычно, участникам будет предложено 6 задач и два часа на их решение. Рекомендую прочитать условия ВСЕХ задач. Желаю всем побольше Accepted'ов, и, конечно же, получить удовольствие от решения задач.
Задачи будут про моего младшего брата Антона. Надеюсь, они вам понравятся :)
Раунд рейтинговый.
UPD: Все-таки раунд будет не совсем обычный, и в нем будет 6 задач.
UPD2: А вот и разбалловка: 500-750-1250-1500-2000-2750.
UPD3: Разбор опубликован.
UPD4: Контест закончен, поздравляю победителей :)
Div. 2
Div. 1
Автокомментарий: текст был обновлен пользователем gepardo (предыдущая версия, новая версия, сравнить).
Finally a 2 hour contest. Things are becoming usual now.
Finally a regular round!
Let's hope for a great round with diverse problems!
Finally a usual 2 hour contest. All the best for your first contest as a problem setter gepardo
Thank you :)
Usual time? How unusual!
Here we go again :D
It is becoming so usual to see comments about usuality
not at all
It is such a long time that has no contest!
Wish it to be an exciting contest! :)
And we thought it's going to be an usual round
is it rated?
Have you even read the statement?
maybe he means that : are you going to make it unrated after the contest or not?
not at all
Как необычно, раунд начнется в обычное время. Кстати когда там div1 раунд? А то жалко, давно уже не было, а люди ждут.
Через 12 дней)
"I wish everyone many accepted" — yes! we love this green word.
I wonder why so little div 1 contest lately. So sad :(
Maybe because, they require harder problems which are harder to create.
wow, didn't know that
Logic
не могу участвовать из за времени! непривычное время!
Я думаю, что не нужно проводить раунды каждый раз в одно время, так как в них участвуют спшники со всего мира. Нужно то днем, то ночью проводить, так как, когда у кого-то день, у кого-то другого ночь. На Удобное время право имеет каждый, с другой стороны каждый автор имеет также право провести свой раунд в удобное ему время. Думаю было бы классно, если авторы выбирались по очереди с разных краёв мира!
Hope next contests will be a bit earlier.
Next contest is just after 5 days :)
I have recently joined.Shall I be able to participate in #379(Div.2) ?
Of course yes, just register to the contest. Wish you good luck :)
I wanna thank your younger brother who faces problems and made us get into competition , All the greetings and appreciation to him
Thank you, it is me.
I hope you are not competing in this round, that would be a huge advantage against all other participants, as you already know all your problems
No, of course, I'm fair. I know all the problems and I will not compete in this round.
Good luck everyone! I hope you will enjoy this round!
It's happening after a long time, also after a long time next one will happen! we'll miss it for long time!
Автокомментарий: текст был обновлен пользователем gepardo (предыдущая версия, новая версия, сравнить).
I'm attending a CF round after a long time hope there are a lot of interesting problems :)
I also hope that my problems will be interesting for you :)
Thanks :D they were really good.
"the round won't be completely usual", will there be a clown dancing in the middle of the contest or something :D
and the clown's name is minasamehlabib :3
Автокомментарий: текст был обновлен пользователем gepardo (предыдущая версия, новая версия, сравнить).
6 problems in 2 hours, will they be enough??? or shouldn't it be at least 2:15 :\
May be problems are easier to solve :P
easier to solve = less fun :(
come on !!!! 12 more days until the upcoming div1 round
It seems that not having 5 problems is the new default
Щас бы длинку написать .
I guess problem C hacks use this: ci are not decreasing and di are not decreasing?
I hacked someone because he didn't handle only using second spell.
E test 3 — what was this?
Consider a white node connected to three black nodes and each of these black nodes is connected to another white node. The answer is 2.
in first sample , add a white child to 11 , that should fail most wrong logics.
Maybe something like this?
Answer is 4.
your input is not valid.
The second line doesnt have 16 integers.
It was just a random test.
Is this rated?
How to solve C?
using binary search!!
Use binary search.Since potions of type 2 are already sorted and also greater the cost of potion 2 greater is the number of potions that are immediately completed. for each potion of type 1 find the maximum type 2 potion that can be bought using upper_bound(In C++ ofcourse) and find the amount of time it takes and find minimum among those.
Time Complexity — mlogk
m-number of potions of type 1 k-number of potions of type 2
I used similar approach but failed on pretest 3... 22247888 any idea why its failing ?
pretest 3 was about not considering using only first spell I think.
in the commented portion i was tackling that as well but still It was failing on pretest 3. btw can we see pre tests once the contest is over ?
yep, just scroll down to see tests.
What if we just need to cast spell type 2?
1.First solve for only using second type spell — O(k) 2.Iterate over m and during each iteration use binary search on k and find minimum value during each iteration. 3.Then take minimum of all value which find in step 2.
Time complexity — O(mlogk)
I add one artificial spell to both types. (x, 0) for the first type, and (0, 0) for the second one. Picking one of this spells is equivalent to taking none of respective types as they have no effect. Thus I was always picking exactly one first type and exactly one second type spell, sparing myself consideration of corner cases. It got accepted so I suppose it's valid.
Two pointers. Sort first spells by mana and go from left to right, at each step decrease the pointer for the second spell while you don't have enough mana.
I solved it with two pointer technique
sort first type spell's by cost of each. then you can use Two Pointer algorithm for each a[i] (the i-th first type spell)
когда это редакционная?
nice try google translate
Should have defined axis in D . The picture for sample 1 got me all confused :/
same as me
What is the simpsons prediction about this contest ?
Any approach for problem E? i used dp on trees but it failed on pretest 3. My solution
compress adjacent node with same color , answer is radius of this tree.
ohh nice one! but can you look into my dp solution? (its short and easy to understand). I cant figure out why its wrong.
in the first sample add a white child to node 11 , answer is 2 , your code gives 3
how is the answer equal to 2?
click 1 twice
Why is the answer radius of the tree?
pick the centre of the compressed tree , and keep painting it till the color reaches the leaves , it takes radius number of steps.
How did you not think it was dp on a tree question?
After painting one node (and compressing the tree again), the number of layers of the tree decreases at most by one, so we have to find a tree with the minimum number of layers (minimum depth). That means that the root must be the center of the tree
The colors make a ring like structure visually. ans=no. of rings-1
Nice contest! Easy problems — so I can feel me smart xD
What was the hacking testcase for F? Probably something for which answer looks nice, but b[i] and c[i] are computed incorrectly.
Was E to Find largest number of alternating 0 and 1 in a chain then ans= (largest_chain/2) if largest_chain is even else largest_chain/2+1
I tried hacking this code on test case: 5000000 5000000 5000000 5000000
but got unsuccessful hacking attempt :( . I was expecting int overflow as the ans for this test case is
1280000000
MAX_INT = 2^31 — 1 = 2147483647
Thanx sir :)
128000000 fits in a regular
int.In addition to what other said, if you want to quickly find the max value without googling, just type this-
cout<<INT_MAX;and run it.Whats the fastest way to check for the optimal solution in C?
I checked for Spell 1 only and Spell 2 only by normal for-loop and used two-pointer method for Spell 1 + Spell 2 checking.
Use binary search.Since potions of type 2 are already sorted and also greater the cost of potion 2 greater is the number of potions that are immediately completed. for each potion of type 1 find the maximum type 2 potion that can be bought using upper_bound(In C++ ofcourse) and find the amount of time it takes and find minimum among those. Time Complexity — mlogk m-number of potions of type 1 k-number of potions of type 2
Oh damn, I'm an idiot. I thought that the upper_bound function was O(N).
At the last minute, I submitted D and got WA, and I found there was an obvious bug and fixed it immediately, there was 15 seconds left and I resubmitted as soon as I could, but I couldn't click the submit button T T
I can feel your pain :D
Can someone give me testcase for C for which my solution[submission:22243090] fail
I wrote a correct solution(I think it's a correct solution) for the problem E but when I was submitting it I choose the GNU C++ compiler instead of GNU C++11. Is it possible for the site administration to rejudge my submission with the right compiler?
link to my submission: http://codeforces.net/contest/734/submission/22248724
I resubmitted it after contest and it got accepted!
http://codeforces.net/contest/734/submission/22249620
Suggestion:
Either 6 problems in 2.5 hours or 5 problems in 2 Hours.
Thank you!
Антон может использовать не более одного заклинания первого вида и не более одного заклинания второго вида, при этом суммарная стоимость заклинаний не должна превышать s единиц маны.
Заклинание не сгорает если его использовать. Может все таки стоило уточнить что и количество раз которое можно использовать ТО САМОЕ ЗАКЛИНАНИЕ не больше одного???? Решал весь контест другую задачу.
Извиняюсь за свою привычку не замечать основного и самого заметного)
Вопрос: когда будет проверка и начисление баллов (очков рейтинга)?
For the beginning of the contest, I could not submit codes to problem A and C. The site kept me waiting without echoing anything, which really really annoys me (I have lost 100-200 points and spent some ten or twenty minutes trying to fix it). After each time I submitted a solution, I had to wait 1 or 2 minutes to see the result, and in most cases, it told me the connection was lost(maybe timeout?) and I must resubmit. Finally, I used a VPN proxy and it somehow worked. I think at the submit page there should be some js code to handle timeout, because (at least for me) a successful submission usually won't take a long time.
In problem E: Does the paint function simply work like the paint bucket in mspaint.exe (floodfill all adjacent nodes of the same color)? If yes, then the description is needlessly complicated. Interpreting it like this I used a disjoint set union, and tried to count the number of white and black sets and printed the minimum of them. Seems like I'm wrong...22248877
Yes, and the idea was taken from paint bucket in Paint.
The paint bucket in Paint has lead to one another interesting problem.
PAINT — ONTAK 2015 (Polish Training Camp)
https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2015/p/pai/
I'm really scared from C's tests everyone is failing in it.
:(
UPD: got it AC
:)
My B failed! :(
Can anyone tell me what is wrong in this?
Edit:Jesus christ, I wrote (k2,min(k5,k6)) instead of min(k2,min(k5,k6)) ...... How does (k2,min(k5,k6)) get evaluated anyway?
TrueSadness.jpg :(
it's interpratated as std::pair(k2, min(k5, k6)), so after assignment mini is k2.
well, maybe it's the same as
ll mini = k2, min(k5, k6)Ohh.. this looks more likely
Comma operator
In a comma expression E1, E2, the expression E1 is evaluated, its result is discarded, and its side effects are completed before evaluation of the expression E2 begins
There should be some warning like:
warning: left-hand operand of comma expression has no effectsee this: http://stackoverflow.com/questions/13579801/left-hand-operand-of-comma-expression-has-no-effect
Solutions for C of many people failed any idea where it failed.
Upd: Mine too failed any idea on the mistake in my code
http://codeforces.net/contest/734/submission/22243843
My solution failed i believe because i set maximum value for answer to be 10**16 (I thought n = 10**5)
I got WA on test 13 because I forgot to take minimum of possible potion values and the original value of x, :/ Feels bad man. :/
i think you forgot if pos <= 0 or something like that
Thanks i got the mistake if upper bound return 0 pos becomes -1 .
Facepalm :)
I too did the same mistake !
What's up with A? I understand it's Div. 2 A and you can give there pretty much anything solvable by anybody in less than 5 minutes (I have been an author myself), but I think it's too much: I feel like I have seen this problem ten times before, it's pretty much one loop and one if (no brain involved), and looks more like a programming language exercise.
Still thanks for a contest! :) I enjoyed E (and have no clue for F).
As you've seen C was a little bit hard, so I needed something very easy for A.
Nice jobs on your first contest :D
Thank you :) Wait for the next contest :)
I believe they meant to test the platform for a lot of quick submissions ;)
I must say, well done, everything worked very smooth this round, good job!
(I submitted A in second minute of the contest thinking how quick I am... and there were already 500 accepted submissions)
Auto comment: topic has been updated by gepardo (previous revision, new revision, compare).
Auto comment: topic has been updated by gepardo (previous revision, new revision, compare).
where is tutorial? good job for the contest
It was good
May be pretests will be more stronger!7! At least in realisations such as D
Where? ! :O
And also how Tutorial was available before the contest is over ! :P
It's available now.
Still not showing any link -
Thank you, the link is added.
http://codeforces.net/blog/entry/48397
In Problem D, It was stated that it's a x-y plane. However, it didn't seem like a Cartesian Coordinates System at all. :\
It is a cartesian plane.
X represented the row instead of the column, -ve rows(i.e -ve X) were on the top !
That doesn't change the result. A rotated plane is still a plane.
I am a new participant. After the contest my rating was not updated and my contest list doesn't show my participation in this round. Is there any problem with my profile or anything else?
Ratings will be updated soon... :) Then you'll find.
I think it might take some time for it to be updated.
Just wait some time, it will be updated.
It takes a while for updating the ratings.
кайда рейтинг?! уйкым келип тур
уйктащищ ертен сабак кой ХD
Has anyone solved problem E,using dp on compressed tree ?
I had submitted a solution to the C problem during the contest and it was giving wrong answer on 5th pretest and I submitted the exact same solution after the contest and it is giving TLE on 6th pretest. I don't know why this is happening.
Submission during contest: http://codeforces.net/contest/734/submission/22240240
Submission after contest: http://codeforces.net/contest/734/submission/22250847
Only
is added !!!
Authority should take a look at this ! The both solution is same ! But for some reason during contest time there occurred a overflow ! for that output was -7166261092318506304 !! -_-
Автокомментарий: текст был обновлен пользователем gepardo (предыдущая версия, новая версия, сравнить).
For problem C, can anybody please explain me why for input
output is 17 ?
Shouldn't the output be 10? Since Anton can use the 1st spell of the first type that costs 17 manapoints. Thus, the preparation time of each potion changes to 1 seconds. So the preparation time is 10*1 = 10.
Yes, u're right. You're reading bad your submission, USER OUTPUT:17, ANSWER=10. So the answer is 10. 22249437
deleted
My AC code gives answer as 10.
Auto comment: topic has been updated by gepardo (previous revision, new revision, compare).
In problem C, I have used range minimum query segment tree + binary search to find the minimum possible time. I am getting WA on test 13. Testcase is pretty much large, cant figure it out manually, Somebody help please :) http://codeforces.net/contest/734/submission/22241998
I had WA on the same test, make sure you're considering the case when you don't use any spells of the first type.
Thanks Ahmed :)
You're welcome ^ _ ^
when will the ratings be updated!!!!!
I got a RUNTIME_ERROR on my submission 22244664 for problem D. If I run my solution locally, it runs fine. Does anyone have a clue?
--EDIT: Also on submission 22251648, which is the same code but cleaned up.
How long do they update the rating ?
We need more regular Rounds like this and in general more rounds..
A funny thing about the contest:
Illuminati confirmed :)
Waiting for the rating change..
dear codeforces PLEASEE UPDATE RATINGS ... maybe someone has to sleep and cant sleep : (
i have an Exam tomorrow send me a message when you update the rate ,i am sleeping XD
it's updated.
this was a great "prime in number" round :D
http://oeis.org/search?q=379
:V :P B)
Deleted
What did you delete? ! :O -_-
First time 'BLUE'! It's great to see my name in blue color! :D
gepardo Problem C: Can you check why test case 21 has only 3 lines, its hard to take input as in questions it specifies input in different lines.
Codeforces doesn't show the tests fully, so you can see only 3 lines. But in fact there're 6 lines in the test.
My bad, thanks
This was my first competition and I really enjoyed solving the problems. Good job Alex! :)
Thank you :)
That is a pity!I have read problem.E for more than one hour,but fail to understand the description until now,please illustrate your meaning clearly in the future.
Stuck on finding bug in submission 22242517 for 734C - Anton and Making Potions. Got error on 13 test case. Any suggestions, please?
Consider the case where you meed to take only potion of the second type.
May I ask you to provide some more details, please?
I am iterating over all items of second type and searching for appropriate items of the first type using binary search in the for loop.
For me it still looks like in 13 test case there is an item of second type with c == n and d <= s.
Just figured out that min_fst function was incorrect. Should check if iterator points to the end after lower_bound
if (it == fst.end()) { --it; }I'm not sure whether I am right. I'm getting WA on test 1 in E. I checked the answer on my computer and it's 2. However, the result of the onlinejudge is 5, which makes me confused. I made the judge print the edges of the data1, it's 3 8 3 8 3 8 3 8 3 8 ???, and that made the wrong result. Also, I get RE on data1 if I chose C++11. I assume that the data of test1 is wrong? if not, why is the problem coursed? Thx
Hi, I had a similar problem before. I see that you are using both scanf and ios::sync_with_stdio(0). Use either scanf or cin when u use ios::sync_with_stdio(0), but not both. That's the reason for the problem you are experiencing :) EDIT: Also, your code has wrong logic so correct that too :).
Thank you! I solved this problem= = With regard to the wrong logic, I will think it over later = =
In problem E
Who can help me explain this example, why the answer is 3?
10
0 1 0 1 0 1 0 0 1 0
1 2
2 3
3 4
4 5
5 6
6 7
4 8
8 9
9 10
I got it..
Solved all problems with Haskell. I really like your problems! :D :D :D