We will hold AtCoder Beginner Contest 405.
- Contest URL: https://atcoder.jp/contests/abc405
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20250510T2100&p1=248
- Duration: 100 minutes
- Writer: Nyaan, yuto1115, ynymxiaolongbao
- Tester: sotanishy, sounansya
- Rated range: ~ 1999
- The point values: 100-200-300-400-475-525-625
We are looking forward to your participation!
I found it very hard to improve my AtCoder rating at the time I reached 2000.
I have to go to evening self-study session every Sunday night, which just the same time as ARCs are running :(
I am still struggling to reach 2000, my highest rating is 1911 and now I am only 1700+, and still dropping.
I'm too bad at counting problems :(
How to solve $$$E$$$?
break it into two cases which one will come first in sequence banana or grape
Where is your mother, the problem author of G?
I use combination to calculate the answer, the total time complexity is $$$O(n^{1.5})$$$. But I got TLE as a result.
Why do you treat the constant factors so hard? Maybe you are in need of family members?
In fact, the answer is (sum of sz[i])! / mul(sz[i]!) so you only need to maintain 2 things, making it faster than calculating C(N, K).
But the difference of calculating the answer is not the main part of this problem.
What's more, many people got TLE because of constant factors though they didn't use comb to calc the ans.
I agree with that, this problem should be extended to around 4-5 seconds for other languages also.
BFS got TLE in D, anyone help?
are you sure? mine
gosh, I BFS the whole matrix from every 'E' and did time-wasting things to ensure the
shortest distance, I didn't even think about it
But that is necessary isn't it ? We need to find the nearest emergency exit, not any exit. The official solution also does plain bfs, but how do they ensure that we are always pointing towards the nearest exit ?
Since the bfs runs on an unweighted graph, the first time any bfs comes to a particular node is the shortest distance from some 'E' to that node.
It's like, imagine a turtle exiting each 'E' node, labelled 'E1', 'E2' etc for each unique 'E'. Now, at each node, it divides into as many turtles as there are possible routes emerging from that cell (4 at max, if there are no walls and all surrounding cells are unvisited). They obviously maintain the same label 'Ei'. Now, since all the turtles left each 'E' at the same time, the FIRST turtle reaching a particular cell bearing some marker 'Ei' signifies the shortest distance.
someone please help me with E. I have never done something with placements type thingy.
C(n + k — 1, k — 1) for putting n same balls into k different buckets(allow none)，mine
Can you explain a litttle bit more of your idea
This is my way of thinking:
The first observation is that bananas (b) and grapes (g) will come to the right of all apples.
Suppose that there are x oranges to the right of the last apple. Now, you first need to arrange a — 1 apples before the last apple. The no. of ways to do this is C(a + o — x — 1, a — 1). Now, to the right of the last apple, x + b + g positions remain. On fixing the positions of bananas, the positions of oranges and grapes will also get fixed. This would be C(x + b + g, b).
Iterate over x = 0 to o and add C(a + o — x — 1, a — 1) * C(x + b + g, b) to the answer.
Who wrote E ???
If there are $$$a$$$ apples, $$$o$$$ oranges, $$$g$$$ grapes, $$$b$$$ bananas:
We let $$$n=a+o+g+b$$$.
If we have determined the positions of apples and bananas, the positions of grapes and oranges are also determined.
Besides, for every valid way to put the apples and bananas, we can also find a valid way to put grapes and oranges.
Therefore, we can let $$$i \in [a,n-g-b] $$$, which means the last position in all the apples.
So, for each $$$i$$$, the answer is $$$C_{i-1}^{a-1} \times C_{n-i}^{b}$$$, as we can put apples in $$$[1,i-1]$$$(the position $$$i$$$ must be placed with an apple), and put the bananas in $$$[i+1,n]$$$.
My Submission
Thanks, understood it easily! Easier than I was assuming
Who can tell me why my program was wrong!!!
idk what you're doing.
inv[i]is just $$$ fact_i^{mod - 2} $$$Why isn't the submit button working? I'm selecting a language and it is automatically removing the selection of the language and giving me error
I solved F in an offline way with BIT. 1 pass from left to right to find segments [A, B] such that A < C < B < D. 1 pass from right to left to find segments [A, B] such that C < A < D < B.
What is the solution provided by the editorial? Seems like a pretty common technique. Anyone has deeper materials on that topic?
someone please help me with problem G. Why my program is wrong? I've tasted it in many test cases but I cannot see the mistake
https://atcoder.jp/contests/abc405/submissions/65704475
I have a problem on G.
There is 10 wrong answer in my submission.
HELP
my submission
Because sometimes your nums frequency can be negative, and then what is his inversed elements?
you should revise your implementation of the MO algorithm so that there are no negative frequencies
I learned Mo’s algorithm + square-root decomposition in G :)
Was it the new record by number of participants? ~685x20
My original account disappered after this competition without notice.If there is anyone know that's why?
original Atcoder account
can anyone tell is my approach wrong or my implementation is not correct for problem F
for finding the number of intersected line i m subtracting sum of line segments that completely lie on either side of the arc (made by the queried line segment) from the total number of line segments using Merge Sort Tree
Submission