We will hold AtCoder Regular Contest 180.
- Contest URL: https://atcoder.jp/contests/arc180
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240629T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: maroonrk
- Tester: maspy, yuto1115
- Rated range: — 2799
The point values will be 400-600-600-700-800-1100.
We are looking forward to your participation!
$$$\dfrac{\text{ARC Round} = 180}{\text{ABC Round} = 360} = \dfrac{1}{2}$$$
Yes, it's not fun. Downvoted.
Regular Contests are harder than Div2, right?
It seems so for me
ofc bro!
Hope I can get positive delta!
B and C are both ez to implement, but need some brave observation(guessing). Like them.
Solved ABD.
I am excited about it.
Excited for this contest, good way to start the weekend!
I wish you get exactly +5 :P
Just joking, gl and hf!
Finally reached 1Dan! (according to ac predictor)
Congrats!
D <<< B
Really? We can bruteforce B. N only 500. I stucked on problem C.
I think B<<<<D. B is easy to construct the answering pairs when you guessed the number of operations.
Guess is really not easy for me xD.
But D just needs a little observation and it's a trivial ds problem :)
Agree, I solved ACD.
I could only do O($$$n^4$$$) for B :(
You can do
O(N^2 log(N))First, you can only swap all numbers with index l where l <= N-K. And you want to swap from the smallest number first (the more small number on right hand side, the more operation you can perform).
Then, for each index l, you just need to collect all possible index to swap. Then swapped it with l from the biggest to the lowest.
Ohhhh, I got my 3rd rk145 in arc! So unbelievable!
Passed B by guessing a greedy approach according to the sample output.
was the greedy approach to swap $$$(i,j)$$$ with min difference and minimum $$$a[i]$$$?
Yes
Well, I swapped $$$(i,j)$$$ such as $$$a_j$$$ is the biggest and $$$a_i$$$ is the smallest.
I think that problem C is solvable in $$$O(n^2max|A_i|)$$$
Submission
Yeah, mine is also $$$O(n^2max|A_i|)$$$. My submission
$$$dp_{i,j,0/1}$$$ means that for $$$A_1,A_2,\dots,A_i$$$, sum of chosen numbers is $$$j$$$, and whether the last chosen number equals to $$$j$$$ (true-->0, false-->1)
Same here.
Atcoder Rubbish Contest 180
Not rubbish, but Atcoder Regular Counting 180.
Spent $$$1.5 hr$$$ on Problem A trying to find DP solution.
Failed miserably.
Problem B looked doable and spent the rest of the time on it.
Missed AC by meagre $$$33 s$$$
was B that easy? i spent an hour and had no idea at all tried several things, but could not get the solution!!
Problem E was one of the best problems I've ever seen, I think it's really cool.
It was completely out of my imagination that $$$[x^n]f(x,y)=c_ny^{(A+1)n}$$$. Are there any implicit reasons for this form or is it just randomly coming to your mind? orz
Okay, I guess that if you believe it's a polynomial of $$$y$$$ (otherwise this problem would seem impossible to solve?) and then you can get this thing real quick.
But noticing that the $$$1$$$ in the formula is actually the upper bound of $$$x_i$$$ is also hard
orz maroonrk
I think it's pretty easy to see that $$$a_n(y)$$$ is proportional to $$$y^{(A+1)n}$$$ (assuming the definition of $$$a_n(y)$$$ is as I mentioned below maroonrk's post).
Recall that $$$a_n(y)$$$ is an integral of a homogeneous function $$$e(x_1,\dots,x_n,y)$$$ of degree $$$nA$$$ over the $$$n$$$-dimensional box $$$(x_1,x_2,\dots,x_n,y)\in [0,y]^n\times \{y\}$$$. In simpler terms, if we scale all of $$$x_1\dots x_n,y$$$ by a factor of $$$r$$$ then the value of $$$e$$$ scales by $$$r^{nA}$$$.
Suppose we have evaluated $$$a_n(y_1)$$$ for some real $$$y_1$$$ and want to relate it to $$$a_n(y_1r)$$$ for some positive real $$$r$$$. Consider the one-to-one mapping from points in the original box $$$[0,y_1]^n\times \{y_1\}$$$ to the new box $$$[0,y_1r]^n\times \{y_1r\}$$$ that scales element-wise by $$$r$$$. The value of $$$e$$$ scales by $$$r^{nA}$$$ after applying the one-to-one mapping. Also, the volume of the new box is a factor of $$$r^n$$$ larger than the volume of the old box. Multiplying these two factors gives that $$$a_n(y_1r)=r^{n(A+1)}a_n(y_1)$$$, from which it follows that $$$a_n(y)$$$ is a polynomial in $$$y$$$ of degree $$$n(A+1)$$$.
I think you can still solve the problem even if $$$1$$$ in the formula was some other constant $$$c$$$. It would just add one extra step. Compute $$$h(z)$$$ in the same way as before, then replace $$$[z^N] \exp h(z)$$$ in the answer with $$$[z^N]\exp (ch(z))$$$.
$$$x^A$$$ term can be interpreted as $$$x$$$ having $$$A$$$ children that are leaves. So the problem is about counting something on tree of $$$n(A+1)$$$ non-root vertices, and that's the intuition behind the observation.
https://atcoder.jp/contests/arc180/editorial/10317
I think the definition of $$$a_n(y)$$$ in the editorial is off by a factor of $$$y^n$$$. From the way it is currently defined it is proportional to $$$y^{An}$$$, not $$$y^{(A+1)n}$$$. Instead of the expected value, it should be the $$$n$$$-dimensional integral.
You are right, and I fixed it now. Thanks for pointing it out.
Can someone detail problem D?
Problem A: I could understand how inverting even letters would help find out patterns like A, BAB, BABABAB etc.
But for this example ABAB we can just make this whole AAAA when last B will not go isn't very obvious. Any more reading material on perhaps a simple topic
"In competitive programming, a well-known technique is using parity to perform inversions. Let’s apply it to this problem."
Couldn't find anything online.
Exactly! I didn't find/understand anything online for that question. Would be great help if someone can explain the intuition behind the question.
Here's how I make the observation for problem A.
Consider string ABAB. There are 2 different operations we can perform, which are reduce ABA B and A BAB. Notice that either way, the resulting string would be AB. So, there are 2 different string you can make for ABAB --> ABAB and AB.
Try with longer string, ABABA. Different operations you can perform are ABA BA , A BAB A , and AB ABA. Whichever you choose, the resulting string is the same, ABA. You can choose either to perform the operation again or not. Finally, there are 3 different strings you can get, ABABA, ABA, and A.
Up to this point, you can infer the pattern if the strings are alternating (ABABABAB... or BABABAB....).
What happened when we find 2 consecutive characters, such as ABAB AAAA. You will notice that you can reduce ABABA to (ABABA, ABA, A) with the above methods but you can't change the last substrings (AAAA).
Therefore, the number of possible strings you can have depends on the alternating characters.
For example: BBABABAABABAAAABA. You can separate this string into several alternating substrings. B | BABABA | ABABA | AA | ABA. Ignore non alternating substrings such as B and AA. Find the number of different substrings you can create for each alternating substrings and multiply it to get the result.
Can some one explain problem C how the Dp state changes
thanks for the contest, liked the problems!
However, maroonrk please remove your template when providing c++ implementation for the editorial. it is really annoying to scroll through 1000 lines of code to reach the actual part, code is supposed to be clear for the editorial.
Is there any DP solution for problem A ?
If anyone has solved, please share once...
Thanks
Actually the problem was based on the fact that whenever you are seeing a continuous alternating pattern no matter on which part you apply that operation you will end-up with same string in each case so it totally depends on size of alternating pattern only. So all you need to do is find all continuous alternating pattern and multiply and then take % here is my solution
Can someone explain the solution for Problem B? Thanks in advance.
Please share some thoughts on C. I am not able to catch up the editorial.
The way I thought about the problem: $$$dp[i][j] =$$$ number of ways to have the operations end in sum $$$j$$$ at index $$$i$$$. The transitions are relatively simple here, we can choose to not include $$$i$$$, which is $$$dp[i][j] = dp[i][j] + dp[i-1][j]$$$.
Or we can choose to include $$$i$$$ which is $$$dp[i][j + a[i]] = dp[i][j + a[I]] + dp[i-1][j]$$$. The tricky part here is there is actually a single situation in which we will accidentally count an already included prefix.
This is when $$$j == 0$$$ and $$$a[i] \neq 0$$$ because suppose two situations:
We include $$$i$$$: Now our operations will end with sum $$$a[i]$$$. Our prefix is $$$[... a[i]]$$$
We don't include $$$i$$$: Now our operations will end with sum $$$0$$$. Our prefix is still $$$[... a[i]]$$$.
Thus, at $$$i$$$ these situations both have the same prefix, however, if sometime in the future we utilise an operation, the resulting array for both cases will be different.
For example if we choose some $$$a[k]$$$ such that $$$k > i$$$, then it is easy to see $$$[...a[i], a[k]] \neq [...a[i], a[k] + a[i]]$$$
So lastly when we transition for $$$dp[i][j + a[i]]$$$ when $$$j == 0$$$ and $$$a[i] \neq 0$$$ instead of adding to $$$dp[i][j + a[i]]$$$ we create a separate array $$$cnt[i][j]$$$ and $$$cnt[i][j + a[i]] = cnt[i][j + a[i]] + dp[i-1][j]$$$. Then we also must handle the transition $$$dp[i][j + a[i]] = dp[i][j + a[i]] + cnt[i-1][j]$$$.
Lastly when considering $$$cnt[i][j + a[i]]$$$ we would also not like to overcount prefixes for the same $$$x = a[i]$$$. This is because if at two different indexes, $$$a[i] == a[j]$$$, we cannot use the same prefixes.
Sample Code: https://pastebin.com/3xp2cxpB
I don't know the complexity of my solution to B https://atcoder.jp/contests/arc180/submissions/55022803
Perhaps the data is missing some case or perhaps this code happens to be faster than it seems