We will hold AtCoder Regular Contest 170.
- Contest URL: https://atcoder.jp/contests/arc170
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240121T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: nok0
- Tester: maspy, Nyaan
- Rated range: — 2799
The point values will be 400-500-600-700-800-1000.
We are looking forward to your participation!
gl! btw 400-500-600 seems challenging!
is $$$C$$$ prefix-sum dp?
O(N^2) dp, where dp[x][y] = # of ways to do the first x elements with y distinct numbers.
Feeling stupid for messing 7 times on B :)
D was very nice.
How to do D?
My idea was that let y be the number that Bob will choose, then among all the pair of element in Alice's array which has difference less than y (to satisfy one inequality condition) chose the one that has maximum sum and if that sum is less than y then Bob wins. Check this for all y. This passed 42/56 test cases
Same idea same wa
Consider this case:
For every value that Bob can choose, Alice can choose two of her numbers to make a triangle.
So you would assume that Alice wins. But Alice has to choose one of her numbers first, which gives Bob a winning strategy:
wow! Really thanks
ahh i see, thanks!
B can be reduced to Rectangle Union Area
49545573
There's a simpler and faster solution for problem E (the complexity is the same, but without matrix operations).
The solution is the same as the official editorial until the last step. Here we need to calculate the sum for every pair of positions, the probability of them being equal in the LR sequence.
Let's say we fix the two positions $$$x \lt y$$$. Now, what we choose before $$$x$$$ and what we choose after $$$y$$$ doesn't matter. For the part from $$$x$$$ to $$$y$$$, there is a probability of $$$p$$$ that a character stays the same as the previous one, and $$$1-p$$$ otherwise.
If we want $$$x$$$ to be equal to $$$y$$$, then there should be an even number of positions where the character differs from the previous one, so it boils down to the following problem:
There is a $$$01$$$ sequence of length $$$m$$$, where each position is $$$0$$$ with probability $$$p$$$ and $$$1$$$ with probability $$$1-p$$$. Calculate the probability that this sequence has an even number of $$$1$$$. The answer to the original problem when we fix $$$x,y$$$ is the answer to this problem when $$$m=y-x$$$.
Let $$$q=1-p$$$ and a polynomial $$$f(x)=(p+qx)^m$$$, then we need to calculate $$$\sum_{i=0}^m[i\bmod 2=1][x^i]f(x)$$$. Using the well-known trick to split the even and odd coefficient, this number equals to $$$\frac{f(1)+f(-1)}2$$$, as the odd coefficients will be eliminated while the even ones are counted twice. So the answer to this problem is $$$\frac{1+(2p-1)^m}2$$$.
Now back to the original problem, after iterating through all pairs of $$$(x,y)$$$, the answer is $$$\sum_{x=1}^{n-1}\sum_{y=x}^{n-1}\frac{1+(2p-1)^{y-x}}2$$$. Now we fix $$$y-x$$$ first, then we need to calculate $$$\frac12\sum_{i=0}^{n-2}(n-i-1)(1+(2p-1)^i)$$$. This can be calculated in $$$O(\log n)$$$ time after some deduction to the geometric series sum.
can anyone explain the approach of A please?
There are only 2 kind of disparities possible :
To clear disparity of type
BA where s[i]='B' and t[i]='A', there are two options to either have sequenceABorBBafter the occurrence ofBA. Since, we need to minimize our operations we will preferABoverBBbecause by doing so we will eliminate two disparities with 1 operation while latter will remove only one disparity.To remove
BAyou can maintain a stack for it whenever you encounterABpop it and doans++.Now we would still be remaining with some
ABs but insufficient number ofBAso now we will search for typeBBafter the last occurrence ofBA. Since theBBafter the lastBAwill able to convert all theBAs toBBand doans++.Similarly, do it for
ABbut now iterate and maintain a stack form the end.Here's a link to my submission : (https://atcoder.jp/contests/arc170/submissions/49550689)
Can anyone give counter test for B https://atcoder.jp/contests/arc170/submissions/49553730
Looks like we have similar idea that got wrong, I also would like to know what's wrong https://atcoder.jp/contests/arc170/submissions/49558825
I got AC , i have wrongly thought that when we have getting more element at index i compared to any index from 0 to i-1 then i just increased directly from (i*(curr_value-last_value)) but at different index we have different values we cannot directly subtract it , so i have iterated over it using set.I found it by testing Ac code of JagguBandar
Input 8 3 3 8 1 3 5 2 5 Output 13
Can you share your AC code.
https://atcoder.jp/contests/arc170/submissions/49564497
Here, a small input
6
4 4 6 6 4 2
Your code output shows 4
Testcases are posted here after contest by atcoder
okay
How is this solution accepted for B? Isn't the time complexity O(n^2) at the least?
#49543170
Let W the biggest number of different values allowed for A (here 10).
By pigeon principe each subarray of length >=2W+1 must contain 3 indices of equal value (which is a particular case of arithmetic progression).
The solution you mention is in O(n M²) where M is the biggest possible size of a window without any arithmetic progression and M<= 2W=20 by the precedent argument.
Ok thanks
Can someone explain which corner case I missed as I got 2 WAs.
https://atcoder.jp/contests/arc170/submissions/49543465
3 BAB BBB
thanks man.
AtCoder, please provide test cases after contest, its very difficult to check all corner cases after contests also
They do.
When I was thinking of the problem D, I came up with using random.
Distinctly, the N^2 log N algorithm is common.
And after that, I considered using random. In more detail, I ramdomly chose 100 num (I called it as x) and checked if there is j satisfies (a[i],a[j],b[x]) is possible to form a triangle.
My program (https://atcoder.jp/contests/arc170/submissions/49557854) was accepted, but I wonder if anyone could hack it.
My English is not good, please forgive me for some naive syntax errors.
Thanks for your reading!
In the editorial of C , it is mentioned that when M >= N — 1 and N >= 2 , the answer is M^c , c -> number of zeroes. I don't think it is quite right. for eg. take S = 00100 , and M >= 5. As per above answer shall be M^4 , but it is actually (M-1)^4. I guess you meant (M — 1)^c ?
I finally upsolved A. Damn was it hard !!
I'm disappointed the official editorial don't provide "counter exemple" testcase to understand parentheses trick.
Example:
I'm also disappointed no code solution is provided. Since ABC335, the editorial are often incomplete, i.e. with textual explanation and solution code.
Complete editorial is essential to upsolve and keep motivation.
I realized that in E you can just use Berlekamp directly on the answer and the recurrence even has size at most $$$4$$$...
You can probably pass by calculating the first $$$8$$$ terms in $$$2^n$$$ or even by precalculating this recurrence offline. Now I find it more interesting that so little people ACed this problem
My code: https://atcoder.jp/contests/arc170/submissions/49586277 I was really about to bash the genfunc when I realized that this will just give me $$$O(1)$$$ linear reccurence