AtCoder Grand Contest 003 will be held on Sunday (time). The writer is DEGwer.
Let's discuss problems after the contest.
Also, we've just announced Code Festival 2016!
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.11.2024 00:13:50 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
I'm new to your site where to register in the contest?
Click "Sign up" at the top.
Thanks for holding those contests!
Would it be possible for you to maintain an official Google Calendar with contests, like TopCoder does, so that one can import it and never miss a round?
Yes: https://calendar.google.com/calendar/embed?src=atcoder.jp_evjr135c62bddnpd26lotmdicg%40group.calendar.google.com
Does it work correctly in all time zones? The next contest should be 12:00 UTC.
It's showing 9am here, which should be the correct time in my timezone. Thanks for the calendar!
Thanks for the great, great effort!!
Somehow, I currently see AGC 44 and ABC 168 absent in your calendar. Did something go wrong?
I also see this calendar: https://calendar.google.com/calendar/embed?src=bhjouir2tb8p5efpbcfbnh8610%40group.calendar.google.com&ctz=Asia%2FTokyo
… but I'd prefer your one, if possible!
Sorry, we recently removed the calendar because we tend to forget updating it, and we don't really need it given that now it's possible to check the schedules from clist.by (https://clist.by/).
By the way, we'll have lots of contests in the next 5 weeks — 3 AGCs and probably 2 ARCs (orange-circled contests are ARCs, including Nomura).
I'm looking forward to seeing you in the contest!
I solved last time's F (when upsolving) in around 10 minutes and had much more trouble with D/E, so I intended to start from the hardest problem now, but after reading it... no way.
Actually F is not hard if you notice that you don't have to deal with the complicated case(connected in both side)... But I didn't even notice that black cells are connected Orz
What is the intended solution for E?
Please check "Editorial" tab for intended solutions.
I can't find editorial in english, can u please provide me with the appropriate link , Thanks in advance :)
Just scroll down in the pdf
I solved it by expressing the array after each query as
previous arrays and some prefixes of the initial array, then as just prefixes of the initial array. I maintain a prefix of some array, find the first time this prefix was formed (the latest array before it that has length less than this prefix), then split it into a prefix of this smaller array plus its ≥ 1 whole copies. This can only be repeated 
times, since the length of this current prefix always decreases at least twice; the total time complexity is 
using good RMQ to find the last smaller element.
And I just noticed after looking for you in the scoreboard, sorting by name shouldn't be case sensitive...
http://pastebin.com/dr4fzuLT For B , any Test Case where greedy strategy of making pairs in increasing order fails?
N = 3, A = {1,2,1}
Answer is 5.
I missed the "all black cells are connected" condition in problem F and marvelled at the number of AC solutions while having exactly zero ideas how to solve it.
Does anyone have any clue how to solve this problem in general case?
And by the way, the problems were awesome, thanks a lot!
At least I couldn't find the solution in general case when I made this problem.
Can D be solved using some sort of inclusion-exclusion?
Testdata for problem D is too weak, my code takes more than 10 seconds in this case: generator.
Sorry, that's my fault. Generator contained some bug so there are no case that consists of around 100000 distinct primes, although I tried.
I am wondering whether this solution to E is correct:
Let's define B sequence as in editorial(increasing suffix minimums). Build a segment tree with min(N, B[0]) ones. Next, let's process B sequence.
In i-th step multiply whole array by max(1, B[i + 1]/B[i]) and then add 1 to range [1, B[i + 1] % B[i]]. We can then restore the answer by querying the tree : Sum[1,1], Sum[2,2] etc. In this solution time complexity is O(N log N + Q log N), so I think it's better than editorial one.
Tree can be build like in this editorial : https://discuss.codechef.com/questions/72277/addmul-editorial
B[i + 1] % B[i] can be very large.
You're absolutely right, thanks.
In C, I used two priority queues. I stored all even indexed elements in one and odd indexed in the other. The I alternatively started popping the first queue, if q1.top() <= q2.top(), I just pop it else I popped q2 and pushed q1.top() to q2 and incremented a counter variable.
I then printed the counter variable. This gave me WA in last 7 test cases. Although the intended solution is much easier, I just want to know what is wrong with my approach. Thank you.
begin sob story During contest, I submitted correct solution to problem E but with unneccesary cout statements. The grader gave me verdict TLE because I printed too many of these, but I assumed my program was too slow and went to problem F.
After contest commenting out 3 lines of cout gives AC.
(http://agc003.contest.atcoder.jp/submissions/847933,
http://agc003.contest.atcoder.jp/submissions/848807)
end sob story
But I personally think that the grader should give feedback on sample inputs.
Did you see the details during the contest? There are some WA in it.
Mmm, there are sample tests at the bottom. Weren't them there during the contest too? Btw, my condolences :|
You have no idea how many times this (or leaving a bruteforce/generator from debugging in the code) has happened to me. That's why I check all couts in my code before submitting and test it on samples. Sometimes, I still forget and get a WA, but it's been happening much less often lately.
Ok, looks like I am not yet experienced with these contests or AtCoder interface yet, I did forget to click details.
Did everyone who solved D used same approach as editorial?
I did.
How to solve D? I am not able to understand editorial.
In which part do you have a trouble? Computing Pair(t)? Something else?
What exactly are we doing after calculating pairs and norms ?
Consider a graph where each vertex corresponds to a number and there is an edge between two vertices if the product is cubic. This graph will be a set of complete bipartite graphs, so the size of max independent set is (total number of vertices) — (max matching). Max matching can be computed greedily by eliminating edges one by one.