We will hold Panasonic Programming Contest 2025（AtCoder Beginner Contest 427）.
- Contest URL: https://atcoder.jp/contests/abc427
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20251011T2100&p1=248
- Duration: 100 minutes
- Writer: MMNMM, cn449, evima
- Tester: toam, kyopro_friends
- Rated range: ~ 1999
- The point values: 100-200-350-425-500-525-625
We are looking forward to your participation!
hopefully can go outside of beginner zone today
update: out of beginner zone
In question C, is it necessary for the graph to be connected? Not mentioned in the question but my solution which should only work for connected graphs is accepted.
Bad round
E is totally SHIT
Not bad. Decent round, decent problems. How to solve $$$F$$$?
Considering Meet-in-the-Middle. In fact there's only $$$O(1.618^{N})$$$ subsequences satisfying the conditions. Meet-in-the-Middle with $$$O(1.618^{N/2})$$$ can pass.
I had to push hard enough to make my MITM pass, changing map to unordered map helped and i am not sure why :)
Who can explain why this algorithm is $$$O(1.618^{N/2})$$$? Thx.
In fact when you have $$$n\ge2$$$ numbers last, you have two choices:
choose this number, then you have $$$n-2$$$ number to choose.
Don't choose this number, then you have $$$n-1$$$ number to choose.
So the number of solutions of $$$n$$$, like $$$fib_n$$$, is $$$O(1.618^n)$$$.
Sorry for my poor prounce because I'm not well in English.
Gosh, I thought Alice and Bob operate $$$K$$$ times in total by mistake. This wasted me 10 minutes :(
So do I :(
Wonder why my meet-in-middle for problem F getting TLE. It only takes <250ms when I locally tested the extreme data.
Submission
upd: It passed after I changed map to unordered_map. Please make n=40 or n=50 instead of 4s time limit next time :(
Could you please explain your approach?
DFS Search for left $$$\frac{n}{2}$$$ elements, calculate sum and store them into map.
DFS search for right $$$\frac{n}{2}$$$ elements, calculate sum and check map to update answer.
Besides, maintain a flag to prevent choosing adjacent elements at the barrier.
Although $$$\frac{n}{2}=30$$$, the number of valid subsequence isn't very much, since we have the limit of not choosing adjacent elements.
Same for me. No idea why it makes such big difference in this case. Spent quite a while on it
With $$$N=40$$$ or maybe even $$$N=50$$$, $$$O(2^{N/2})$$$ also passes, removing the most essential observation part...
You can anyways do it without the observation by dividing into 3 segments.
How will you combine the 3 segments contribution?
like if you divide it into N=1 to 15, 16 to 30, 31 to 60, find out the non-adjacent subsequences for each, when combining what matters is whether left or right end of the segment are included in subsequence or not, then you can combine easily.
How do you combine easily?
Yeah how will you combine "easily"? I could not find any idea of combining 3 splits, we have 3 variables and we need to fix atleast 2 of them. I would appreciate if you could provide a working code.
You know what i just realized that my time complexity bound still needs the fib observation, i am dumb.
you can also use vector and lower_bound instead of map, it is generally almost always faster
Bad I feel so difficulty.
F<E.
E is just BFS, while F is MITM DP. Why so many people think E>F?
You can hardly see a $$$O((nm)^3)$$$ BFS in a contest. On the other hand, mitm is more popular.
Do you call every problem that eventually can be solved just using bfs, a "just BFS"?
I solved more BFS than MITM in contests. So, probably it's more intuitive for me. Also, I find DP a bit harder than BFS. So, this might be just me. But I get your point.
Because E is harder to implement, while both problems are straightforward.
For me, in F it was harder to think about the boundary condition than implementing E.
In E, I assumed that the trash removal process would comprise of atmax 8 steps (2 in each direction, steps means removing in the direction till I cannot or the there are no trash). This is 39/43. Is there any counter example? Submission
UPD: Found :)
Anyone would help me?4WA on E. It almost kills me to find the BUG.
Submission
Maybe this can help you.
Good contest but many cheaters ranked high:
plz ban them atcoder_official to maintain a good competition environment thank you
why DEF are all search problems ???
i suppose it's meaningless to set many search problems (although some of them are tricky), and there should be more data structures or math problems, or there are no difference between the performance of who has already trained for some years and who has just learned some basic algorithms, and the rating system is also meaningless then.
Why you think D is a search problem? In my opinion, it's a dynamic programing problem. However, I think that D is more difficult than E,F:(
Or could you share your search solution about D?
upd: he tells me that he used Memoization Search and he thought it's a kind of search.
You are right, but why C,D,E,F are all brute forces problems?
how D??!!!
i try to use dp[t][u] which means the chess in node u and round in t player (t=0 Alice and t=1 Bob),
and init dp chess on node 'A' dp[0 or 1][u] = (s[u]=='A').
Then i try to do:
if t==0 (Alice turn), dp[0][u] = OR of dp[1][v] for all v next to u
if t==1 (Bob turn), dp[1][u] = AND of dp[0][v] for all v next to u
i repeat this K times thinking it simulates K moves each player.
But it gives WA on some tests. I feel like it only simulates one step per player, not full K steps.
how should i change my dp or transitions to handle each player moving K times properly?
You can assume dp[t][u] which means whether the player in round t wins when the chess is in node u,then the problem is solved.
Submitted D with 1 second left only to be TLE'd in a single test case due to the use of set instead of unordered_set :( also what is this C lol I used a randomized algorithm to solve it lmao
you can just force every biparition of the nodes in 2^10
:( that's pretty straightforward and unfortunately I didn't see it
Why does D need set or unordered_set?
Mine only used a DP.
My Implementation
I tried some weird reversed path approach that required the usage of a set, couldn't think of something smarter or simpler because of lack of time :/ anyways, good solution by you, your code is way smaller than mine
ABC247E I’m solving ABC427 E – Wind Cleaning and 4 test cases keep failing; can anyone give me a hint about the edge cases I’m missing?
I think that in those cases T becomes dirty by already removed trash.
Is possible to solve problem C for bigger $$$N$$$? how large can $$$N$$$ be?
No. This is a max-cut problem, which is NP.
WORST PAIN EVER
so next week you will become 1 dan.
The time limit for F should be 5 sec. 4 sec is too strict.
I am not able to get any ideas about C? Any hints??
Try every combination of black and white. This part tries at most 2^10 possible combinations.
Note that you have to erase the edges between black and black, white and white. Just take the minimum of all the possible combinations.
The idea for G is really new to me (that we find an equivalent sequence). Is it something general in disguise? If not, can you share some problems on similar ideas?
About E: Why the efficiency of map and unordered_map differs so much?
map amortized time is O(logn). unordered_map amortized time O(1).
why map is amortized? isn't it just O(nlogn)?
This user submitted 4 completly different code in the last 20 minutes. And these, especially the last submission, are very strange.
https://atcoder.jp/contests/abc427/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=sry0417
I think he use AI.