We will hold AtCoder Regular Contest 109.
- Contest URL: https://atcoder.jp/contests/arc109
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20201128T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: nuip
- Tester: yamunaku maspy
- Rated range: — 2799
The point values will be 300-400-500-600-700-900.
We are looking forward to your participation!
Could someone explain how to solve C?
Let $$$\mathrm{dp}[k][i]$$$ be the symbol of the winner for a tournament that starts from position $$$i \pmod{n}$$$ and has $$$2^k$$$ players. Hopefully the transitions are obvious.
https://atcoder.jp/contests/arc109/submissions/18471624 can you please help me find where my code fails ?/
Have you tried the following:
98% of WAs and REs can be resolved this way. I don't have time to delve into every code I'm sent, it's much harder to debug somebody else's code and being able to debug your own code is a valuable skill. It is also a very routine process that can be learned much faster than problem solving and algorithms.
Can you please share your code for generating smaller test cases
Is it really so hard to write a program that generates a random string of R, P and S?
A bit unrelated, in your code you use the
std::pow(double x)function to compute integer powers of 2. This is bad and will sooner or later give you WA because of precision errors; it's better to write your ownpowfunction that works on integers.Thanks!
If $$$k$$$ is small, you can repeat the string $$$s$$$ until its length is at least $$$2^k$$$ and then simulate the competition ($$$s_0$$$ with $$$s_1$$$, $$$s_2$$$ with $$$s_3$$$, and so on).
To solve for bigger $$$k$$$, observe that at some point the match results in the current round repeat themselves (just like how we repeated $$$s$$$ at the beginning). So if length of $$$s$$$ is $$$2m$$$ (even) then you know that the result of 1st match is the same as the result of $$$(m+1)$$$-th, $$$(2m+1)$$$-th, $$$(3m+1)$$$-th match. In the case of odd-length $$$s$$$, we double it to make it even.
Now after every iteration, you have a string which is the period of the string of results of the last round meaning you can reapply the algorithm above until $$$k=0$$$.
To simplify this further, I don't care about the parity of length of $$$s$$$ and always double it on every iteration. After every iteration, the length is divided by two anyway so the length remains constant throughout the algorithm.
Thank you for the explanation!
Players 1,2 do the first match, players 3,4 the second and so on. Let w(x,y) be the symbol of the winner of a match. Then after 1 round, the symbols of the remaining participants look like
w(s[1],s[2]),w(s[3],s[4]),w(s[5],s[6]),...
So we can implement that winner function as given in statement, and create the string of the next round in a loop k times. Then ans is s[0], since this is the last participant. Note that we allways need to create the string of the next round only up to the length of the original string, because then it repeats. Submission
Thank you for the explanation!
Can You Please Explain, why it repeats.
It repeats by definition of which hand is used by player i. If n is even, then it repeats after n/2 matches, because in each match two players are "used". If n is odd it repeats after n matches. So we are on the save side if we allways calculate it up to n.
Got it,thanks!
How to solve B and C problem?
B: Simplest strategy would be to buy n items, 1..n. But of course we can do better.
First we can buy the item n+1 and split it to 1 and n. This saves one buy. Second we can buy the item n and split it to 2 and n-2. Third we can buy the item n-1 and split it to 3 and n-1-3. ...
So we can save one buy as long as i+sum(1..i)<n. We can calculate that in a loop. Code
Can you prove optimality?
Well, no... We would somehow need to proove that this strategy gives to most possible splits.
Intuitivly it does because we allways buy the biggest possible item, which has from its size the best potential to be split into other items.
We just have to get a sum that is greater than n*(n+1)/2.
so let us say that we will take all elements after x in the list of (n+1) elements.
(n+1)*(n+2)/2-(x)*(x+1)/2 >= n*(n+1)/2
solving this we will get the answer.
(Just for proof purpose)
Well, The idea I use is quite straight forward. We want $$$1\,,2...N$$$ from $$$1\,,2...N,\,N+1$$$ so the problem can be formulated as we want $$$X_1+X_2+...+X_k>=N(N+1)/2$$$ such that $$$k$$$ is minimum and all $$$X_i(s)$$$ are different. So it's quite obvious that we pick Top(Max) $$$K$$$ numbers $$$(N+1)+N+(N-1)+...+X$$$ s.t. sum becomes at least $$$N(N+1)/2$$$. Clearly we can see that first few numbers $$$(1,2,...X)$$$ should be splitted from $$$(N+1)$$$ and remaining comes directly. So we can find maximum value of $$$X$$$ such that $$$X(X+1)/2 <=N+1$$$. And we can obtain such $$$X$$$ for ex. using Binary Search.
I saw tourist's code where he used binary search but could not get the approach.
It is based on the same formular, but not loop until n is reached, but instead binary search for the number of loops necessary. Which has obviously better complexity.
Binary search for the max number of elements you can get by breaking (n+1)th log. The max number of elements you can get is obviously by breaking it into smallest of pieces i.e. 1,2,3,4...
Now the sum of these elements should be less than or equal to (n+1). So binary search for 'x' such that (x*(x+1))/2 <= (n+1) i.e. sum of first x natural numbers less than or equal to (n+1).
After getting this, you can buy these 'x' elements with 1 coin, and the rest of (n-x) elements with (n-x) coins.
Total answer is (n-x+1).
Code
How to prove that this kind of strategy is always optimal.
I don't have a mathematical proof but this is why I thought this would work.
We can get first 'n' elements using 'n' coins. Which leaves us with (n+1)th log. Obviously now we would want to maximize the number of logs we can get through this because each log has SAME PRICE i.e 1 coin. So it doesn't matter what size you break it into, but the number of logs should be maximized.
An argument can be why shouldn't we break this into 'k' pieces and then try breaking some other log into some 'm' pieces. Say if n=10, we break 11th log to 5+6 and 10th log to 1+2+3+4. Now it leaves us with to buy 7,8,9,10. First observation that now we can't get 10. Because we broke 10 into smaller pieces. Anyhow even if we didn't, we can notice, the answer will always be greater than if we broke (n+1) optimally. I don't have the proof for this mathematically, but this was my intuition.
Here is a formal proof.
It's clear that we want to buy the longest set of logs, so we can reformulate the problem as choosing the largest $$$x \geq 0$$$ such that we can form {$$$1, 2, ..., n$$$} from {$$$x + 1, x + 2, ..., n + 1 $$$}.
Now if $$$x(x + 1) / 2 \leq n + 1$$$, the log of length $$$n + 1$$$ can be partitioned to form {$$$1, 2, ..., x$$$} and the rest can be directory formed from {$$$x + 1, x + 2, ..., n$$$}, so the largest such $$$x$$$ gives us a lower bound.
To form logs of lengths from 1 to $$$n$$$ we must satisfy $$$sum($$${$$$x + 1, ..., n + 1$$$}$$$) = (n + 1)(n + 2) / 2 - x(x + 1) / 2 \geq sum($$${$$$1, ..., n$$$}$$$) = n(n + 1) / 2$$$. However, $$$x(x + 1) > n + 1$$$ implies $$$(n + 1)(n + 2) / 2 - x(x + 1) / 2 < (n + 1)(n + 2) / 2 - (n + 1) = n(n + 1) / 2$$$, which implies the sum of the lengths of the logs is smaller than $$$n(n + 1) / 2$$$, so we can't form logs of lengths from 1 to $$$n$$$. This proves that largest $$$x$$$ that satisfies $$$x(x + 1) / 2 \leq n + 1$$$ is also an upper bound, which implies that this is also optimal.
Clean solution to D:
If we make the transformation to the centroid of the triangle, then each possible triangle corresponds to exactly 1 possible centroid location. These centroid locations form a grid with 4 points inside every 1x1 box (with uneven spacing, but this doesn't matter), on which you can move to any of the 8 adjacent points except diagonal through a corner.
After making this transformation and labeling the points by their row and column $$$(x, y)$$$ in the centroid grid, the answer is $$$\max(|x|, |y|)$$$, unless we're exactly on the diagonal that we can't move freely on, in which case you can add 1, unless you're already in the same 1x1 cell as your target.
(https://atcoder.jp/contests/arc109/submissions/18474121)
Can someone please explain, why after the transformation the answer is "After making this transformation and labeling the points by their row and column (x,y) in the centroid grid, the answer is max(|x|,|y|), unless we're exactly on the diagonal that we can't move freely on, in which case you can add 1, unless you're already in the same 1x1 cell as your target." ?
Try drawing some paths on the grid above, I think you should be able to figure it out.
A simpler problem to consider: how many moves does it take a king to move on a chessboard from $$$(0,0)$$$ to $$$(x,y)$$$?
Clean AF. applause
I solved E with finding the differences between the numerators (2^n * the answer array) and searching it on OEIS.
Could you please explain how to search it on OEIS specifically? I tried to do like this but I failed. One reason for this is maybe that I am not familiar with OEIS so can you help me?
Take the third sample as an example:
First multiply the answer array by $$$2^{19}$$$ and we get something like
$$$4980736,4980736,4980742,4980782,4981006,4982158,...$$$
Find the differences:
$$$0,6,40,224,1152,...$$$
Search $$$6,40,224,1152$$$ on OEIS leads you to A229580 with an O(n) formula. (It's easy to see that $$$ans[i]=ans[n+1-i]$$$ so we only calculate the first half)
This is kind of random, but why is ARC 109 missing the "Discuss" link that points to this post? (At https://atcoder.jp/contests/arc109, normally there's a "Discuss" tab that links to CF.)
B:
#include <bits/stdc++.h> #define ri register int #define ll long long using namespace std; ll n; int main() { scanf("%lld",&n); ll l=1,r=n; while(l<=r) { ll mid=(l+r)>>1; if((2*n+2)/mid>=mid+1)l=mid+1; else r=mid-1; } printf("%lld\n",n+1-r); return 0; }Why is this code correct? I cannot understand the division in the bisection method. "(2*n+2)/mid>=mid+1" has no error?There is a hack in problem F.
One of optimal solution :
44(b) -> 17(w) -> 18(w) -> 22(w) -> 23(w) -> 5(w) -> 43(b) -> 42(w)
Many submissions failed this testcase including tourist's(https://atcoder.jp/contests/arc109/submissions/18464249).
One correct submission by ksun48:(https://atcoder.jp/contests/arc109/submissions/18467968).
You can check the difference between my submissions.
(should be wrong)
https://atcoder.jp/contests/arc109/submissions/32177114
(should be correct)
https://atcoder.jp/contests/arc109/submissions/32177316
Can you update the testcases?maroonrk
I added your test (after_contest_1.txt).