We will hold Japan Registry Services (JPRS) Programming Contest 2024#2 (AtCoder Beginner Contest 364).
- Contest URL: https://atcoder.jp/contests/abc364
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240727T2100&p1=248
- Duration: 100 minutes
- Writer: yuto1115, cn449
- Tester: sotanishy, toam
- Rated range: ~ 1999
- The point values: 100-200-250-425-475-500-600
We are looking forward to your participation!
My planned post contest discussion stream
Fun fact: 1115449 is a prime number!
ACAM in ABC362, then Steiner tree in this round?????? Will ABC365 have a poly multipoint eval as G?????????
imo specific case of NP-Hard problem isn't bad. Or have this G appeared before?
Yes, there is a similar (template) problem on luogu. Someone passed it in 2 min and they probably copied their code.
Scream if you love dynamic programming
It is not a good habit to present old questions in new competitions.
Problem G coincides with a problem from BOI 2016 (link), so it wasn't hard to copy-paste my previous code :)
Last ABC, problem G was a blatant template for ACAM and now it's just a blatant copy of another problem? atcoder_official, if you can't set Gs, then don't. It's better to have a contest with 6 problems than blatantly copying another problem.
In the BOI problem, you are given all $$$k$$$ important cities upfront. Additionally, the constraints on $$$n, m, k$$$ differ substantially. Of course, solving the BOI problem makes it easier to solve G, but it's not an exact copy. I think it's perfectly fine to have this level of similarity. For example, a friend pointed out that I solved 152E - Garden, a problem from 2012 with a similar solution. I could copy-paste parts of my code had I remembered that problem, but I didn't. If you still remember an old problem and realize that the current one is similar then you deserve to have an easier time solving it.
what is the problem with this solution for e?
https://atcoder.jp/contests/abc364/submissions/56054692
when he eats the last sweet it can actually exceed x or y , sowhen updating dp you should actually check that j <= x for example not j + sweet <= x .
oh fucking shit! thanks (by the way, doesn't it say exceeding, meaning it should be < ?)
Yes but he stops after eating it
Can someone, please, tell, how can I link my cf Id to my AtCoder account?
UPD: I got the answer
can you tell how to do it?
Settings -> General Settings -> (there is a box to fill)
can someone explain me why this submission to E didn't pass?
https://atcoder.jp/contests/abc364/submissions/56063726
Just try to run this testcase:
n = 2, x = 3, y = 4 a=(4,2) b=(2,2)
Thanks sir
my solution for E got passed but ideally it should give Runtime error can anyone tell me why
https://atcoder.jp/contests/abc364/submissions/56052731
Why the problem E and C were almost same, but their input style was different ?
If you read through the problems you'll find that although C and E have similar themes of eating, C is greedy whereas E is DP. It's two completely different problems, and I think both were good problems.
I think they meant the formatting of the input themselves are different. One was all A then all Bs, the other being pair of A,B. I didn't notice this during the contest and somehow passed all samples.
Actually same as me, this contributes one WA for me...
hey why GREEDY doesnt work in E but for c it works only differ is max and min so why ? also ,
How maintaining minimum total saltiness when choosing exactly k dishes solves the problem.
Basically, how to transform from O(NXY) to O(N^2Y)
I don't know if this dp technique has a name, but it's pretty well-known.
Let's say we have a dp where $$$dp[i] = x$$$, which means that the optimal value at state $$$i$$$ is $$$x$$$. This is not solvable this way when $$$i$$$ is very large.
If $$$i$$$ is very large and $$$x$$$ has a reasonable limit, say, $$$1\leq i\leq 10^9$$$ and $$$1\leq x\leq 10^5$$$, one way to go about it is to swap the dp state and the result. So the new dp would be $$$dp[x] = i$$$, denoting that optimal value $$$x$$$ is possible using state $$$i$$$.
It’s called state shuffling. There isn’t a lot of articles explaining it though.
Can someone Please tell why this Solution of E is giving WA. I have thought it for hours but unable to figure it out. https://atcoder.jp/contests/abc364/submissions/56048006
2 3 4 4 2 2 2
answer is 2, but you answer is 1. because you can eat 1 after 2.
Thanks a lot. Got the flaw in my approach
any recursive/memo (dp) solution for E
https://atcoder.jp/contests/abc364/submissions/56216266
really a good approach i have solved many dp problem but this type of approach i did't know before btw thanks
My F's solution is failing on 3 testcases, can someone help me understand why?
My Idea — instead of connecting l--i+n,l+1--i+n...r--i+n, connect l to i+n then connect l--l+1, l+1--l+2, l+2--l+3... I maintain minimum and maximum index a node is connecting to skip iterating from l to r, and just jump certain number of nodes.
Link to submission