Привет, Codeforces!
16 декабря 2017 года в 14:35 MSK состоится очередной раунд Codeforces #451 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса. Обратите внимание на необычное время начала раунда!
Раунд будет рейтинговым.
Этот раунд проводится по задачам муниципального этапа Всероссийской олимпиады школьников по информатике 2017/2018 года г. Саратова. Задачи были подготовлены силами Центра олимпиадной подготовки программистов Саратовского ГУ. Убедительная просьба к участникам муниципального этапа в Саратове не принимать участия в этом контесте.
Хотелось бы сказать большое спасибо Григорию Резникову (vintage_Vlad_Makeev) и Николаю Калинину (KAN) за помощь в подготовке задач, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а также Алексею Рипинену (Perforator) и Роману Глазову (Roms) за прорешивание задач.
Участникам будет предложено шесть задач и два часа на их решение. Разбалловка 500-750-1500-1750-2000-2500.
UPD Разбор
UPD2 Поздравляем победителей!
A friendly round for Chinese! :)
But, I registered for it and it doesn't show that I'm out of competition. Why?
Fixed, thank you for the notice!
eselppa is my classmate,I dont know why he is unrated,and he cant login now?
Not so friendly to uni students as ICPC EC Finals will take place on 16~17/12.
I guess real ACM dalaos can clear this round in 30 minutes anyways.
Edit: You must be dalao http://mirror.codeforces.com/profile/eselppa
No, It's not me. It's my friend.
I really think that CF had a difficult time, but at least last 3 contest had a decent queue and nice problems. I think CF is going in a right direction, mentioning the number of contests.
Last week, I saw that c.f. Round 451 would be held at 18:35 MSK. Why it comes to 14:35?
MikeMirzayanov , there is a clash between tomorrow's atcoder match and this , can something be done? , I dont want to miss either one of these! fcspartakm
Unfortunately, we can not move the round because of the onsite high-school olympiad and Russian AI Cup Final Round. Usually we avoid such clashes but this time we can't choose start time.
Similar contests of last year:
1) http://mirror.codeforces.com/contest/746 2) http://mirror.codeforces.com/contest/747
Nothing is mentioned related to rating.
Is it
-rated?
It's 0.15(90)-rated one
MEOWWWWWWWWWW~
May as well be a nice warm-up before ECL Final :)
Will it be Sunday tomorrow in Moscow or it is just typo ?
it is just typo, saturday will be in moscow tomorrow
Thank you, fixed.
GOOD LUCK !!!
Is this contest rated? lol
writing "lol" won't protect you from down votes
Not cool it overlaps with arc tomorrow. Why so early?
Тык!)
Just curious, is that a rated contest?
Certainly
CAn yUU please, SiR, stop deleting my "is it rated?" comments/censor me ? We live in democracy which means I can freely act like a retard , not in communism where i would be put in some gulag.
No
You have the freedom to post senseless comments, and everyone else has the freedom to vote it down into oblivion. This results in you being hidden for negative feedback.
please make sure the time limit is enough
This is my frist contests after cet-4 , best wish for my cet-4 , besides i want to rise my points!
Best wishes for us.....
Hope for short statements <3
When you open Codeforces for no reason and you see a contest is about to begin in 30 mins :P. I always get an email for contests saying "Attention! Unusual start time" but this time when the timing was really unusual I didn't get any email. Not cool Codeforces :(. Anyways, it's nice to see so many upcoming contests lined up before New Year.
"The scoring distribution will be announced later." When?!
Scoring distribution please?
Good Luck!!! Удачи!!! ;)
Nice time start point for me:)
The round was the best for me
Very nice difficulty distribution of problems.
Liked the fact that there were no long queues. Keep it up.
is D some directed graph problem
I think that greedy will work fine here. Remove the last alarm clock while there is at least k alarm clocks in segment.
Did you use binary search in your solution?
No binary search is needed. Since times are <= 10^6, you can create a vector of bools from [1, 10^6] and iterate over windows of size m to simplify implementation.
D was DP+ segtree After sorting.. when u see that u are at a time ti such that there are >=k alarms within time ti-m+1, just turn of the ith alarm. maintain the sum using segtree
If you use a sliding window, you don't need a segtree.
I've solved D with FFT and made some optimizations to pass the TL.
How did you do it with FFT?
Greedy on time and sliding window may help you.
I think problem D is two pointers + data structures
How to solve F?
If the length of c is n, the maximum length of a and b is n or n - 1.
To calculate a, b, c in each case, we can use Hash. The hash value of a + b is the sum of hash value of a and the hash value of b.
And remember to check if there is some 0 at the beginning of a, b, c when the length of a, b, c is greater than 1.
Can you please explain, how are you using hashing? I am not aware about the concept of hashing. Also, how can you say the hash value of (a + b) is the sum of the hash value of a and the hash value of b?
Thanks.
How to solve problem D?
I thought of segment tree solution but was unable to get it accepted. :(
Edit -
My basic idea was to assign 1 (in the array) to the minutes when alarm clock rings and in each iteration, find the sum from i to i + m minutes, say it p.
If it is less than k, then no problem. Otherwise update the array from range L to i + m and make each element in it 0. It can be done by lazy propagation and about finding that value L (from where we have to update the range) , it can be done by simple binary search.
Can anyone tell me, what I was missing or was I wrong with my logic?
I solved it using BIT tree. Just maintain at each index how many clocks are there and while checking for any time i just see the number of clocks present between i and i+m time interval and if it is greater than or equal to k just update index i+m with negative value equal to abs(val[i+m]-(k-1)).
django28..I believe I have done exactly the same but just used segment tree instead of BIT like you.
Can you have a look at my code and tell me what I did wrong?
Code — https://paste.ubuntu.com/26194518/
I think it's somewhat greedy but not sure about that!
What i did was that first make an array of alarm point(as there are only 1e6 alarms and all distinct!) and then take a window of size m and if it contains more than k then i start removing from last on alarm(as removing this makes sense and help to optimize our answer for the next step). Finally slide the window and calculate the number of alarms thus removed.
Problem D. Change the statement without seeding an anouncement?????? consequence -> consecutive
Hints for D? I was thinking binary search but am not sure and couldn't get it to pass
A sliding window algorithm. And remember the greedy strategy, its always the best to turn off the last alarm clock.
Ohh allright thanks!
sliding window
I was also thinking about it for a while, but I don't know how can we check in O(n) that we can choose alarm clocks so that they don't intersect too much.
How did people manage to solve D in 5 minutes? =)
Is it some kind of a standart problem?
A sliding window algorithm did it for me. Hope it passes the systests.
UPD: It did. XD
I know what sliding window is, but I don't know how to solve this problem.
use greedy technique for that. Delete last alarm clock.
Why is it correct to delete the last one?
Because if another alarm clock intersects with the previous ones, it's better to remove an alarm ending at an earlier time instance compared to one ending later.
Cause, that will help the most. The first alarm clock will be the first one to leave the span of m minutes. So, there may be a case that there exists exactly k-2 alarms in the range starting from last alarm clock.
Cause that clock will be part of more up coming window.
This round is true Div.2 round: when most of the problems are solvable for Div.2 participants.
Why change the statement and not send a annoucement???? consequence -> consecutive Consequence ??? How can i know this...
Hey, this submission(33299805) says runtime error...while checking with Diagnosis in custom test, its says,
I don't understand.. Why this happened? it's ruined my mood & I have left contest.. Now, there will be a disaster in my rating. :(
Lol, can someone(MAYBE CF ADMINISTRATION) explain me why I can`t hack one submition twice?
I hacked once and got an "Invalid input" because of the EOL in the end. After I corrected my test CF says "Submit already challenged". LOL, REALLY??? So then I must know if the EOL is needed there before hacking????
Due to this issue I didn't get 200 points on hacks.
THX, CF.
So then I must know if the EOL is needed there before hacking????
Yes.
So why it is not mentioned on the hacking page, hah?
What is testcase 7 in F ???
Did you check for 0s at the beginning of a, b, c if their lengths are greater than 1?
Yes
EDITED
In Problem-E, my first submission got WA in pretest 9. But, then I relocated my long long ans = 0 variable at the top of main function and got pretest passed after submitting. Why did that happen? I was looking for the bug for such a long time, maybe like 30 minutes. Then I just gave up and then did the above thing on a whim and got accepted. but why?
declaring long long ans in main might have garbage value. oustide main is 0
I wrote long long ans = 0;
maybe you did ans += something; before there is any value on ans, the value of ans before declared, inside main is random, CMIIW
You also changed your comparator function.
The change in comparator function looks insignificant to me. Either way, the sorting will be the same
Is greedy work for problem E?
Yep. It is greedy.
It is rated?
Near perfect conduction of an announced rated round. Why even bother asking?
I am getting Wrong answer on pretest 8 for 2nd problem (B) My submission
Can someone please help? I used the Extended Euclid algorithm to solve it.
There is another "NO" case.
Suppose "X" is non-negative and "Y" is negative.
You obviously want to make "Y" non-negative by subtracting numbers from "X", right?
Here, there is a possibility of making "X" negative even though you manage to make "Y" non-negative.
In short, "X" and "Y" cannot be both non-negative in this case.
I solve that case looking for minimal non-negative "Y" in O(1) and thus checking non-negativity of "X"
Speed up this system testing, I can't wait to see how many problems will fail from the 6 : |
Speed up this rating updates, I can't wait to get my new COLOR xD
Very Good Contest! Great thanks to the author!
I got some issues hacking. From the second hack, it always navigates to the hack summary page without the hack popup where I can enter my hack case.
So I am not able to hack others in the same browser. I have to switch to a different browser or use a different computer. Did it happen to others?
Same Issue. Annoyed me a lot !! -_-
My solution (33309422) for problem C gets wrong answer on pretest 1. Whats wrong here ?
You have to print how mnay lines of output you have
Thanks. I feel so terrible for such a silly mistake...
It happens to all of us at some point; if you ever see a problem with a VERY early pretest (like 1, 2, or 3), you can use the fact that CF will judge the example test cases as the first pretests (at least in my experience they always have). So if you fail test 1, you can diff check with the sample output and find out that you have a formatting error.
Yep, I too didn't do that in my first attempt! Got a WA. :/
can someone please look into my code why it is giving RE on sample test(3).
code : https://ideone.com/8dFo4E
One doesn't simply code trie when the string lengths are ≤ 10.
yeah but i have wasted a lot of time in it! please help.
btw i didn't think that trie is making problem it's only when we have a string of length 1. if i remove all those then it runs fine. And when there are string of length 1 then builder is not working correctly. please help!
UPD: I have changed my MIND.. if you want to downvote me then you are welcome :)
Wow, how did you find that?
May be I was lucky :D
Damn, you must be really lucky and skilled to find those 2 submissions!
Lol. They're the same submissions. Think for a moment before slinging mud on others.
submission link is updated.
I still don't find them similar.
lol. Didn't even bother to change submission id
Edit: codeforces saves all revisions you know :P
Edit2: looks sufficiently different to me
submission link is updated.
those submissions aren't similar at all.
IS O(sqrt(ai)*n) sufficient to pass the tests in problem E ??
sqrt(ai) ~= 3.16*10**4 (max)
n = 2*10^5 (max)
no of steps ~= 6.3*10**9
extremely low chance of passing, unless the constant factor is really low
Because I've seen many solutions pass the tests even though they used O(sqrt(ai)*n) solutions !!..
link please?
I think the diagnosis process makes the system test so slow. But I am pretty sure that many of the contestants do not or less care the diagnosis result. So this is just my small suggestion, what about running the diagnosis only when the contestant wants? For instance, by clicking
run diagnosisbutton on submitted code. This may reduce the server load a lot, making system test faster, and contestants can know their ratings earlier, which most of the contestants care about. Can I share your opinion?Are you sure the diagnosis is even running? I could not see diagnostics after WA (on pretests and when submitting now)
33314427
Maybe WA does not run the diagnosis.
originally the blog said, it would run for WA and RTE, but seems so
My first Div.3 contest!
Good contest, comprehensible statements, short systest pending time.
Many thanks, although I lost my perfect chance to solve the last problem for the first time, just because I forgot checking the leading zeroes :<
That moment when Div.2 E is easier that Div.2 D... like way easier.
the E task should be D or even C
Can anyone plz point out my mistake in E, I wrote a pretty easy solution- http://mirror.codeforces.com/contest/898/submission/33306957
Thanks
My solution for D gives runtime error on testcase 3 but runs fine on my system http://mirror.codeforces.com/contest/898/submission/33302108 Help please!!!
changed int to long long as suggested by someone... still it gives runtime error :(
Hi, I think your problem is that you're doing ss.erase(it1) and then using it. "Iterators, pointers and references referring to elements removed by the function are invalidated."
I didn't test it but I think that is the problem, hope it helps!
yes, you are right.
auto it2=it1; it2--; ss.erase(it1); it1=it2;worked fine.For problem C I think my output for the first test case is correct ,can anyone tell me why my first test case output is wrong.
I really don't think this round is good. The rates of algorithms used in the contest are not in equilibrium. 3 problems(ABC) don't need any skill or algorithms, and C is just grand-grand-great simulation. And 2 problems(DE)are just greedy, which doesn't need advanced algorithms. Even DP and graph theory don't exist in problems. And the quality of the problems aren't high as well, here "quality" means the well-situated difficulty for Div. 2. (Because I can only AC around 2 problems before, but this time I can do 4 if I have a little more time)
I'm beginner and I'm glad to see such problems like A or B. No one in the entire world started walk right after birth. Those problems actually makes me think that I can solve more then just 1 or 2 problems in the next contest. And yeah, it keeps me motivated, and don't give up from CP. If the contest was too easy for you, move to div1 and try to beat tourist:)
Actually I don't think the round is too easy for me. As what I said, I can do 4 if I have enough time. I am still far from AK(solving all). But I just think it's much easier than most of the div2 contest before:) Maybe the round still has an advantage that it gives us encouragement. Maybe what I said in the last discussion is not fit, so I pay apologize about it. But if all of the div2 contests on codeforces are "encouraging rounds", what will it be like?
Can someone discuss their F solution ?
Editorial is already published
Good work! Very interesting tasks.
%zu printf specifier is not recognized... this cost me an accept in C :(
For Question B, if we do brute force according to editorial, we will get TLE on test 49 for Python...
Did you try PyPy?
oh yes now it passes!! Thanks so much!! So next time I want to submit Python code I should use PyPy as it runs much faster?
Yes. But there is some difference in Python and PyPy.So read the docs.
Hey guys, I didn't do well yesterday because I was stuck on Problem C for a long time. I used std::set to store the telephone number, and I iterated the set to check if they were suffix to each other, and I delete the elements while iterating and I got runtime error. Can anyone please tell me how the set works while erasing the elements. Thanks a lot.
I was getting the same error . So instead of deleting unrequired elements just store answers in some ans vector and output them later . For the error see this
https://stackoverflow.com/questions/2874441/deleting-elements-from-stl-set-while-iterating
Thanks for the website, it really helps. I used a vector to store the elements should be erased and delete them later to pass the problem during the test, it's another solution.
For Problem F,I use unsigned long long without modulo (let the hash overflow naturally) and Rabin-Karp Algorithm to check whether the answer is ok,the verdict shows TLE on test 77.However,if I add a modulo which is only 23333 (only about 2e4) and use the same way to check,it got accepted in only 78ms.So can I assume that you intend all the hashing algorithm without modulo to fail?I don't think it's good for a hashing problem,especially when I use Rabin-Karp to check and it still can't pass.:D
I think, during the contest someone passed pretests with overflow hash and someone just hacked this solution, as a result a counter-test for overflow hash was added in the final test set.