We will hold AtCoder Regular Contest 173.
- Contest URL: https://atcoder.jp/contests/arc173
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240310T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: chinerist
- Tester: tatyam, maspy
- Rated range: — 2799
The point values will be 400-500-600-700-800-1200.
We are looking forward to your participation!
Excited!
Excited!
Too hard. Only solved ABC.
problem B is very simplified version of this problem (104730J - Путёвка на Острова Кука) this problem asks you to split 3n points in n non-degenerate triangles or report that it's impossible
Damn I got WA*2,AC*142 on E... ): ): ):
ABCD is so easy (for me) that I solved them in 1 hour.
How to do D?
Answer is Yes when the graph is strongly connected and either both positive and negative cycles exist in graph or neither of them exist in the graph.
And the graph is always strongly connected I believe. It says it in the problem given any node s you can reach node any node t which basically describes strongly connected graph.
I tried doing C by binary search and segment tree, but got TLE. I wanna know does the intended solution uses sparse table instead?
Oof, and here I was thinking that Sqrt-Decomposition could work :3
No, it only needs
std::set
and a little bit observation.Thanks, will try to figure that 👍
Sqrt how? Did you have any idea?
My approach could be implemented with segment trees as well. I'd just scrapped them earlier for some reason so went with SqrtDecomposition.
As is observable, the major goal is to find a pair of indices after(or before) $$$i$$$ such that the numbers are either both larger or both smaller than $$$p[i]$$$.
This can also be viewed as finding the first such pair, that, among all pairs after(or before) $$$i$$$, they are the first to not have $$$p[i]$$$ between the two numbers $$$p[j], p[j+1]$$$ (or $$$p[j-1], p[j]$$$).
I translated this into a problem of overlapping segments (looking at any +- pair, we see a segment) and used square root decomposition to optimize a little, basically — considering all adjacent pairs right before $$$j$$$ such that the overlap of their segments contained $$$p[i]$$$, $$$j$$$ is our index of interest as a solution candidate.
Though, apparently, that probably wasn't needed, given the $$$O(n)$$$ proofs that have been shown.
This task has simple implementation.
Assume, we are looking at some element $$$x$$$ in the permutation. There are elements that are smaller that it — we will mark them as $$$-$$$, and elements, that are greater — we will mark it as $$$+$$$. So we have this picture: $$$[-+--+x++--+-]$$$.
Now, when the answer is greater than $$$3$$$? Well, if we have $$$[-x+]$$$ or $$$[+x-]$$$ or $$$[-+x]$$$ or $$$[+-x]$$$ or $$$[x-+]$$$ or $$$[x+-]$$$. When the answer is greater than $$$5$$$? If we have $$$[-+x-+]$$$ or $$$[+-x+-]$$$ or $$$[+-+-x]$$$ etc.
So, now we see, that we need to find the smallest segment, that has $$$--$$$ or $$$++$$$ at one of its ends. We can stand at $$$x$$$ and just move to some direction and calculate number of $$$-$$$ and $$$+$$$. Once these numbers are not equal, we found a candidate for answer for this direction. Notice, that answer can be in one of two forms: $$$[...x]$$$ and $$$[...x.]$$$, where $$$.$$$ is one element. But the second form can't be for first and last elements, so we need to "if" it.
Why can we just iterate, without any optimization? Well, I don't know. I first tried to create a bad test, and thought, that worst answer is $$$O(n \cdot \log{n})$$$. Then I whote a stress, which, if I understood correctly, showed even $$$O(n)$$$.
Thanks, I think I had the same idea, but struggled a lot in debugging the ifs. I will try it again anyways.
Instead, you can store a set $$$S$$$ of $$$i$$$ such that $$$sign[i] = sign[i+1]$$$, and use the $$$j \in S$$$ closest to the left and the right of the index being considered. You can keep track of that set by testing positions in increasing order of $$$p_i$$$. You should also first test that $$$sign[x-1]$$$ and $$$sign[x+1]$$$ are opposite signs when testing $$$x$$$.
Of course, the first and last positions are special cases that can be solved by iterating.
This way the solution is clearly $$$O(n \log n)$$$ without much thinking/stress testing.
I think it is actually O(n), and it is what I did in contest as well.
The main observation is that if you an $$$x$$$ where the answer is very large, this means in your notation it will look like $$$[...-+-+-+x-+-+-+...]$$$ with many alternating + and -. But then, for each of those + or -, notice that the answer is always EXACTLY 3. For example, if I am looking at $$$-+-$$$, then the + has two numbers around it that are provably smaller, so if I take that window of 3, the + cannot be the median.
This means that you get an amortized O(n) solution if you just implement it in the most straightforward way!
https://atcoder.jp/contests/arc173/submissions/51137481
Why is this giving RE for A?
As many people just kept guessing and got the key conclusion in problem E, it would be much more interesting if we are actually required to prove the conclusion, but this can't be done in reality anyway. Still it's a very good problem and I liked the way to get to the result step by step.
What was your approach to E? I backtracked $$$n=6$$$, found out that we cannot construct $$$2^6-1$$$, then gave up lol.
The only countercase is when $$$n=6,10,14,\cdots$$$, in which case you can't use all elements.
I can confirm that spam submitting with random condition on N without proving works
can you please explain me the solution to E. I can not understand the editorial.
imo, B<C<<A
btw, AC A on 118min is NICE!
Out of first three problems, the problem A was the hardest for me. It has two topics, which I implement worst at all — the digit dp and the binary search.
I hope, one day, I will learn how to implement them.
Actually,neither of the topics is required. However,I do agree that A is harder than C,for i spend 80 minutes on A and only 30 minutes on C.
How did you solve A if you didn't use digit dp + binary search?
https://atcoder.jp/contests/arc173/submissions/51137481 Hi bro can u pls tell why this is giving RTE for A.. its working fine on local
There's too much code to debug but I noticed you're keeping hi as 1e13, that's not sufficient, you need to keep hi as 1e18
Yeah but when i increase it then only im getting RE. When i keep 1e6 it works fine
You don't need a dp array for it, you can pass a boolean strict variable and return directly when the strict is false, it saves a lot of recursive calls. Sharing my submission for ref https://atcoder.jp/contests/arc173/submissions/51142683
First, total number of neq numbers is $$$9^i$$$ for a number with $$$i$$$ digits. So you can determine the number of digits of the answer. Subtract the number of numbers which have fewer digits than the answer from $$$K$$$.
Then determine the number for each of the digits. For the $$$i$$$ th digit, iterate through $$$0$$$ to $$$9$$$, excluding the number which equals to the previous digit. Each number gives a contribution of $$$9^{i-1}$$$. Subtract it from $$$K$$$,until if subtracted, $$$K$$$ becomes smaller than $$$0$$$ and you get the answer for the $$$i$$$ th digit.
I never use digit dp in normal form because you can always fix the first smaller digit and then write dp without any restriction.
anyways this problem is much more easier check this code
How to solve B?
After bricking miserably on A and B, I proceeded to misread D and didn't realize that the edges were directed. D'oh!
That being said, I solved C by wishfully thinking that the sum of answers are not that large (probably in the order of $$$O(n)$$$). Checking if the answer could be a certain value $$$v$$$ is quite simple: if the current element is $$$x$$$, we represent each element $$$y$$$ as the sign of $$$y - x$$$. Then, all the subarrays with length $$$v$$$ must have sum $$$0$$$. Notice that all subarrays will have sum $$$0$$$ if the leftmost subarray has sum $$$0$$$ and the other subarrays are a cyclic shift of that subarray. We can check this by maintaining a hash in a segment tree.
Can anyone prove why the sum of answers is small, though?
The answer consists of 3 parts:
Consider subsequence of all points falling under case (3). Let $$$P_a$$$ and $$$P_b$$$ be two such consecutive points. Then, it can be proved that answer for both of the points does not exceed $$$b - a + 3$$$. Consider e.g. case $$$P_a < P_b$$$. Since $$$P_b$$$ does not fall under case (2), we have either $$$P_{b-1} > P_b$$$, or $$$P_{b+1} > P_b$$$. Consider e.g. case $$$P_{b+1} > P_b$$$, then $$$P_a < P_b < P_{b+1}$$$. This implies that $$$P_a$$$ cannot be the median of both segments $$$[P_a, \dots, P_{b-1}]$$$ and $$$[P_a, \dots, P_{b+1}]$$$ simultaneously. So, one of these segments would give the answer for $$$P_a$$$. (If the segments have even length, you might add element $$$P_{a-1}$$$ to them to obtain segments of odd length).
So, the answer for all such $$$P_a$$$ does not exceed the doubled distance between the leftmost and the rightmost of them, plus a constant overhead for each pair of consecutive such points. In total this is bounded by $$$5n$$$.
how to solve task A
Write a function which given a number K, let's you know how many numbers <= K exist which are Neq numbers. You can use digit dp for it.
Next, use binary search on this function to find the smallest number which gives K as the answer.
Is there any standard approach to solving problems like A?
Corner cases are fucking.
I think these tests should be put in the samples.
My solution for problem C is almost correct, but I didn't consider the case that $$$i = 1,n$$$, I got no points.
I hate this contest.
can confirm that stress test fixes this
I wrote an $$$O(m^2)$$$ sulotion for D and it got TLE at first. https://atcoder.jp/contests/arc173/submissions/51130486
what was your approach?
Congratulations! You've entered Hall of Fame!
I think B can actually be solved when $$$N = 10^5$$$. Correct me if I was wrong.
In the editorial we only need to brute force all the point pairs, consider these $$$O(N^2)$$$ lines and do the calculation in $$$O(N^3)$$$ time.
When the longest line $$$L$$$ (the line that can make answer smaller) exists, the points on $$$L$$$ need to be $$$\geq 2n/3$$$. So we can actually randomly choose some pairs to check rather than check them all. The possibility that two random points on $$$L$$$ is at least $$$4/9$$$. When checking 50 pairs, the possibility of misjudgment is less than $$$10^{12}$$$.
Here is my submission