no coments

Typical "friendly" person in cf

it is good

We waited around 6 weeks before our problems were first reviewed, but after that we haven't waited much for everything else

What app/website you're using? Good day to you.

The last div1 round was at a time that was much friendlier to Chinese, but not to me. Fair turnaround, I guess.

What are you talking about, you can see problem statements 12 hours ahead of us.

OK they delayed it 5 minutes for you

Yes. It is rated for everyone whose rating is less than 1900 and also if the user is unrated, it is rated for them too.

I'm not an ICPC finalist, but I will happily receive a hat if you want xD

So?

I don't even know that guy dude! ... neither a single connection between us

Check this out!!

GFG is saviour :)

They both know GFG ;)

My code that failed pretest 4 broke with this:

3 4 1

1 2 3

1 2 2 3

1 4

Sorry, my bad. I offered the problem, and it coincides.

.

My idea: I found product of digits of Some integers from 1 to n that they have the greatest digits(kinda integers have more 9), in this way:

if n=d₃d₂d₁d₀ for every digits greater than zero in n except d₀ like d₁ i subtracted one from d₁ and digits on the right of the d₁ turn to 9 which product of them are d₃*d₂*(d₁-1)*9

like if n=1099 they are 1099,1089,099 or if n=100000 they are 100000,99999

i didn't know how to explain better https://codeforces.me/contest/1143/submission/52059415

Just precalc)

This solution is kind of dp, but looks more like brute force.

One can notice that the number of different possible products is not really big. For example, I considered that for a d-digit number there should be around $$$9 ^ d / d!$$$ distinct products. Then, I just did a recursion memorizing the products already computed.

Solution

In F, when you convert all points in the input $$$(x, y)$$$ to $$$(x, y - x^2)$$$, then the problem reduces to finding the number of lines that pass through atleast a pair of points where no points are strictly above the line, instead of parabola (since, the new equation becomes $$$y^l = bx + c$$$ from $$$y - x^2 = bx + c$$$). This is just the size of the upper convex hull of the transformed points. (Need to take care of the case with lines of same x coordinates, i.e vertical lines)

You want to pick some position in the range [l, r] and $$$N-1$$$ times repeat: if you're currently at $$$a_j = p_i$$$, then jump to the next $$$a_k = p_{(i+1)\%N}$$$ (for the smallest possible $$$k \gt j$$$); at the end, you shouldn't be at $$$j > r$$$. The rest is just simulating this efficiently with precomputation and RMQ.

This will probably work
For each position find r[i] — first position of next value in permutation(p[2] for p[1], p[1] for p[n] and so on). Now for each position calculate R[i] — min pos where subsequence exists using r and binary jumps, and answer for each query is just checking if minimum of R on segment <= r.

My solution was to first find the largest $$$l$$$, for every $$$i$$$, such that there is a subsequence in $$$[l, i]$$$, which is a cyclic shift of permutation. For finding this $$$l$$$, what we can do is add an edge from each ind $$$i$$$ to the nearest ind $$$j$$$ in left, such that $$$a_j$$$ is the left element of $$$a_i$$$ in the permutation. Now, we can easily find $$$l$$$ for each $$$i$$$ using the approach of binary lifting. Once, we find $$$l$$$ for each $$$i$$$, we maintain a segment tree, which gives a maximum $$$l$$$ for a range. So, for query $$$[ql, qr]$$$, if the maximum $$$l$$$ in the range is greater than or equal to $$$ql$$$, then subsequence exists.

Why is NK / gcd wrong?

same T_T

It was (i assume, since this is how i fixed it) n=100000 k=100000 so that n*k overflows if you use int for intermediate results.

It definitely wasn't clear to me as well and lost some time because of this.

take every node that have zero respect child and insert it in array and then sort array and print , get pass in test case wish will not failed on main test

What's the problem with this statement? It is relatively short.

Let $$$b$$$ be an integer between $$$0$$$ and $$$9$$$ inclusive. Then the position $$$\pmod{11}$$$ of $$$10a+b$$$ in the sequence is uniquely determined by $$$b$$$ and the position $$$\pmod{11}$$$ of $$$a$$$ in the sequence.

Consider an inadequate number x with $$$k+1$$$ digits, or in other words $$$x \in [10^k, 10^{k+1})$$$. It turns out that following information is sufficient to know whether $$$10x+l$$$ is inadequate:

1) d1: Number of inadequte numbers $$$<10^k$$$
2) d2: Number of inadequate numbers $$$<10^{k+1}$$$
3) c: Index of x in a list of inadequate numbers mod 11

Moreover this information is sufficient to recalculate this information as well for k:=k+1 and x:=10x+l in case 10x+l is inadequate.

Everything heavily relies on fact that $$$11 | 0+1+...+10$$$.

This is already sufficient to solve this problem in $$$O(n^2)$$$ since in constant time you can determine whether number after appending some digit is inadequate.

Moreover it turns out that number of inadequte numbers < 10^k falls into a cycle 9, 10, 9, 10, ... and if you look at formula keeping information about c then knowing that (d1, d2) is either (9, 10) or (10, 9) you can deduce that it actually doesn't matter what out of these two pairs (d1, d2) is, new value of c just becomes (l+c(c-1)/2+10)%11. This means that if you fixed some beginning position in our string and processed some digits, we need to keep only one number (between 0 and 10) to determine whether after appending new digits our number stays inadequate. This allows you to write O(n*11) dp.

You don't have to remove the root. Since it doesn't have a parent it cannot disrespect its ancestors.

But this time you are looking at the solution from the beginning, you just need to see it. Rewrite $$$y=x^{2}+bx+c$$$ as $$$y-x^{2}=bx+c$$$ and you are done.

Funny problem, thanks to authors. Actually, I liked all of todays problems, more or less.

Even if you write 10**6 as a recursion limit,Python won’t increase it more,than 10000-20000(I don’remember the exact num)

because it can be 799999999, which gives a larger product.

maybe 799999999?

Because it's 799999999

Congratulations on making it to the Red level! I've noticed you've been an active member since quite a time. You deserved it.

You were pretty adamant in doing contests.

Добавил проверку индекса для vector (-1 является очевидно недопустимым) и получил полное решение. Я знал об этом до отправки, но G++ 17 игнорирует такое обращение по индексу, поэтому код работает правильно и без проверки.

You're not :-)

Precalc or dp. Precalc: link

Your code uses quadratic time in a case like this:

n 2n 1
1 2 3 ... n
1 1 1 ... 1 1 2 3 ... n
1 2n

Where the sequence first has n copies of 1, and then the integers from 1 to n.

The queries can be whatever. What happens is that while construct_nextn(i) is not called for i that are already checked, none of the n ones ever get marked as checked before being handled. So for each of the ones, your code goes through the entire n-length loop in construct_nextn(i). Therefore the code does O(n^2) work in this instance.

Let's denote $$$S$$$ as starting point, $$$L$$$ as moving length, $$$R_{i}$$$ as $$$i+1$$$ th restaurant met. $$$R_{0}$$$ is the closest restaurant to point $$$S$$$, and $$$R_{i}$$$ is the closest restaurant to point $$$S+L$$$. You can check 4 scenarios for $$$i$$$ in $$$[0, n]$$$.

Scenario 1: $$$S \rightarrow R_{0} \rightarrow R_{1} \rightarrow ... \rightarrow R_{i-1} \rightarrow R_{i} \rightarrow S+L$$$ : $$$a + b + i*k = l$$$

Scenario 2: $$$R_{0} \rightarrow S \rightarrow R_{1} \rightarrow ... \rightarrow R_{i-1} \rightarrow R_{i} \rightarrow S+L$$$ : $$$a + l = b + i*k$$$

Scenario 3: $$$S \rightarrow R_{0} \rightarrow R_{1} \rightarrow ... \rightarrow R_{i-1} \rightarrow S+L \rightarrow R_{i}$$$ : $$$l + b = a + i*k$$$

Scenario 4: $$$R_{0} \rightarrow S \rightarrow R_{1} \rightarrow ... \rightarrow R_{i-1} \rightarrow S+L \rightarrow R_{i}$$$ : $$$a + l + b = i*k$$$

In each scenario, calculate $$$l$$$. Then the number of stops for that case is $$$\text{gcd}(l, nk)$$$. Of course you should not calculate when $$$l \le 0$$$.

Assume you didnt't call vector.clear() after moving children to the parent of current node, space complexity will be O(n^2) which will get MLE.

In fact, vector.clear() makes its size = 0, it doesn't deallocate the memory reserved by it, so it's the same memory as if you didn't call clear :)

At least in my solution (which es the same formula), x is the amount of restaurants you travel through.

That's because if $$$x$$$ is grater than $$$n$$$, then in each jump will be at least $$$x \cdot k > n \cdot k$$$, which means that it is more then circle length. And so the place where you will get after the jump is the same as if the jump was $$$k \cdot (x - n) + c$$$.