We will hold AtCoder Beginner Contest 391.
- Contest URL: https://atcoder.jp/contests/abc391
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20250201T2100&p1=248
- Duration: 100 minutes
- Writer: sotanishy, toam, physics0523
- Tester: math957963, cn449
- Rated range: ~ 1999
- The point values: 100-200-300-400-450-500-600
We are looking forward to your participation!
The first AtCoder race in this lunar year!
Good luck!
As the weakest one of all the pigeons, good luck!
Good luck and have fun!
Good luck and have fun!
Now it is Spring Festival in China. Happy new year!
this contest was brutal
Is F some kind of a well-known problem or it's just really simple? Didn't solve it, but 1k+ submissions is quite a lot for F.
https://github.com/joric/interviewbit/blob/master/programming/graph-data-structure-and-algorithms/smallest-sequence-with-given-primes.md
can anyone explain the solution for E?
Create a dp and use recursion , the recursion takes l and r as input (the left and right indices within which the answer is to be computed) and then returns the max appearing element in that range and how many elements need to be swapped to reverse that max appearing element , if l + 1 == r at any stage , meaning there is only one element in the string , then what should be the answer ?? Clearly, the max appearing element is the s[l] — '0' (the only element left in the string) and to reverse this max element we need to reverse this element itself , so the min number of elements to reverse is 1 , for example if (l = 1 , r = 2) at any stage then we are only trying to compute the answer for s[1] , so lets say s[1] = '1' , then answer is (1 , 1) else its (0 , 1) , now for each iteration , compute the answer for its 3 subparts , lets say mid = (r — l)/3 , then for each iteration , compute it for (l , l + mid) , (l + mid , r — mid) and (r — mid , r) , now there are 2 cases :
1] All three of these subparts give the same max element
2] any two of the three elements give the same max element
Case 1 is pretty simple : if all these 3 parts give the same answer , then to reverse the max appearing element , you need to take the 2 minimum counts from these 3 (counts means the min number of swaps required in those subparts , i.e we are returning a pair<int,int> in dp , representing the max appearing element and counts)
Case 2 is also simple : if any 2 of these 3 elements are returning the max appearing element then we need to swap any 2 of these 3 in order to reverse the max appearing element at this stage , so just check which 2 of the 3 are returning the same max element and take the min. counts from those 2. Here's my submission , feel free to ask further doubts. https://atcoder.jp/contests/abc391/submissions/62319929
Is D really so easy to implement? I keep getting WA on 21 testcases :(
Help me out please. Where am I going wrong? Submission
Yep, It was kinda implementation , I did this !!
Yeah it's very easy with priority_queue and your code is too difficult to understand. (maybe just for me?)
Here's my solution!
Choose the lowest blocks in each column and their move-away time is the altitude of the highest one among them!
But some blocks will have to wait in the last row no? So during that time the upper blocks will also have to wait and so on?
Yes.
But if there's no blocks in a column, the blocks was't moved away won't move away forever. The
while
will break so their move-away time is stillINT_MAX
.This fact simplifies the implementation significantly:
Let
col[i]
be the row-indices of all blocks in columni
, sorted in ascending order. The time at which the k-th row disappears is the maximum of the k-th element, among all columns, i.e.max(col[i][k]) for all i=1..W
.I did exactly that
https://atcoder.jp/contests/abc391/submissions/62305146 can you help with what's wrong in this code? i implemented similiar approach of what you said, or can you share your code please
I don't think is necessary to use maps and sort, it makes the code more complicated, i didn't use them at least. Just try to answer, when will the first row dissapear, and after that, when will the rowi+1 dissapear knowing when the rowi dissapears. Also the problem inputs X first, and then Y, maybe that is a problem.
Yeah pretty much same. I was having some complications while implementing the simple solution so I just commented everywhere which made is easy here I think it's one of the most readable at in my opinion
So ,is rank 1 legit?
Why does everyone think E is easier than D but I do not think so?
For me, E is a simple divide and conquer problem. But I didn't bother to try D despite having 1 hour left, because of its complexity.
G seems like a too well known problem for 200+ submissions.
I went through all of the Indian Submissions and almost all seem AI generated. Hopefully the admins take strict action.
Yeah I realised that when I saw low rated people solving G within 20 minutes and most of my friends not being able to solve it.
anyone who was able to solve problem D with priority queue? (at each column)
https://atcoder.jp/contests/abc391/submissions/62291264
u can think the block i with first pos (Xi,Yi) will be disappear after Yi. Then consider do it in loops and get the max of Y. (sorry for poor English)
Thanks for this, but am i not doing the exact same thing? -Link
is there someone indea using ai so banned by atcoder?what's his name?
Please help me modify this code. I spent a long time debugging it during the exam.
Quality problems(which I start to struggle from) starts with E. E seemed like implementation heavy and I was not very fond to address the string of size upto 1e7 in my recursion so after 20 minutes on it I left it. I start F. I did almost completed it, but time's up.
I am new to Atcoder and I have a question. How do you guys attempt Atcoder? Do you start from F and G and go in backward direction so that you have maximum time for quality problem or I am just slow and rusty and most people are at the start of a new skill or you select any problem which seems interesting from A to G? How you make sure you do that most quality and get the most value out of a contest? Or is it that currently I am really slow?
why is the editorial of problem D with complexity O(n log n)? it can be solved in O(n)
as for the code:
with complexity O(n+q)
in fact, we don't need to sort
Hey i have a question. I have heard lots of people talk about how good the ABCs are ? Can anyone tell me why they are good ? Thanks. I am a newbie so dont know a lot of stuff
check this: video by maroonrk
Thanks this was helpful
How to do E ?
I have commeneted above who had some doubt in the same problem , you might read that comment if you want...
https://mirror.codeforces.com/blog/entry/139033?#comment-1243014
Can anyone tell how to solve the problem C please ?
You just have to track where pigeon are kept... https://atcoder.jp/contests/abc391/submissions/62469951
Record the number of pigeons in each nest and the place of each pigeon at the same time.
I don't konw F. Why it's enough to look at ijk <= K? Who could teach me why.
Say length is n, indexing is 1 and f(x,y,z) is the actual computation for tuple (x,y,z) and you sorted it in descending order then f(i,j,k) will be always be more than f(i+1,j,k), f(i,j+1,k) and f(i,j,k+1). So essentially going from any i to i+1 decreases the value of overall of f.
For each i, there are j∗k possibilities and they are actually maximum because of sorted property. I hope it helps. Example take i = 1 and j, k = n then there are n2 arrays
F is easy, but I didn't solve it during the contest qwq