Автокомментарий: текст был обновлен пользователем 4qqqq (предыдущая версия, новая версия, сравнить).

Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).

Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).

Is the dynamic programming approach used in D1 a known concept?

Why is the runtime for D2 log(log(n))? Does does the average number between 1 and n have about log(log(n)) unique prime factors or something? Why is that?

Imagine statements were this short

Here's an $$$O(n\log n)$$$ solution for E (with $$$O(\log n)$$$ query time). For a given sequence of $$$k$$$ temperatures, let $$$f(T)$$$ be the answer for the query $$$T$$$. Then we have $$$f(i+1)=f(i)$$$ for $$$2k$$$ different values of $$$i$$$, and $$$f(i+1)=f(i)+1$$$ for all other values of $$$i$$$. (I won't prove this, but you can try it out for yourself.) We solely have a data structure that stores the $$$2k$$$ values of $$$i$$$ for which $$$f(i+1)=f(i)$$$. On receiving $$$T_i$$$, we add $$$a$$$ and $$$b$$$ to the data structure, where $$$f(a)=T_i-1, f(a+1)=T_i, f(b)=T_i, f(b+1)=T_i+1$$$.

Answering a query reduces to determining how many stored values are below $$$T$$$. I used a PBDS and binary searched to handle insertions which means the complexity is actually $$$O(n\log^2n)$$$ but in principle this can be made into $$$O(n\log n)$$$.

Implementation: https://codeforces.me/contest/1614/submission/137071970

$$$cnt_i$$$ is the amount of $$$a_i=i$$$.

Really? I think $$$cnt_i$$$ is the amount of $$$j$$$ such that $$$a_j\bmod i=0$$$.

That feeling when you wasted 4 attempts on problem C because of wrong modulo :’)

Problem C solution before contest : https://math.stackexchange.com/questions/712487/finding-xor-of-all-subsets

In question B, it is given how the businessman will travel for first 10 years(5256000 minutes) only. And it is asked to choose the cordinates such that it minimises the time for walking within first 10 years only, no info. about what to consider if he can't visit every building in that time, what to print in that case the minimum time < 10 years by visiting only some good buildings or just try to minimise the time only if buildings can be travelled within 10 years or something else can't decide.

Terrible editorial for D1 and D2 with no code ? Its very confusing,probably some translation error

Can’t understand E’s solution. Can anyone explain more detail?

Here are the video Solutions for problems A-D1 In case you are interested.

Submission for C

Could anyone please explain what's wrong in my code? I applied the exact same approach as in the editorial. Thanks in advance.

In E2, you can also write the following. Let's iterate the first number. It is clear that all subsequent gcds are divisors of this starting number. So you can do dp not on all numbers, but on divisors. And it works for $$$O(n*countDivider^2)$$$. If not iterated by the same number, then it is TL48). But you can sort all the numbers in descending order and make a cutoff in time (it is clear that the number in the answer will not be the smallest). And it's already OK)

“where $$$cnt_i$$$ is the amount of $$$a_i=i$$$. ”

I think $$$cnt_i$$$ is the amount of $$$j$$$ such that $$$a_j \text{ mod } i=0$$$.But I cannot understand how to get $$$cnt$$$ in $$$O(C \log\log C)$$$ time.

There's an easier way to solve problem E. Let's say $$$f_i(x)$$$ is the temperature in the morning of the $$$i+1$$$-th day when the temperature is $$$x$$$ in the morning of the $$$i$$$-th day. Then for the query $$$x$$$ on day $$$i$$$ we just output $$$g_i(x)=f_i(f_{i-1}(f_{i-2}(...f_1(x)...)))$$$. Assuming that we've been able to solve for $$$g_{i-1}(x)$$$, we just need to solve for $$$g_i(x)$$$ in terms of $$$g_{i-1}(x)$$$.

Firstly we can observe $$$\forall x_1 \le x_2,1\le i\le n,f_i(x_1)\le f_i(x_2)$$$, and then we can derive that $$$\forall x_1 \le x_2,1\le i\le n,g_i(x_1)\le g_i(x_2)$$$.So we can use binary search to find two positions $$$a,b(a \le b)$$$ satisfy $$$g_{i-1}(a-1)=T_{i-1},g_{i-1}(a)=g_{i-1}(b)=T_i,g_{i-1}(b+1)=T_{i+1}$$$, then $$$\forall x < a,g_{i}(x)=g_{i-1}(x)+1;\forall x>b,g_{i}(x)=g_{i-1}(x)-1;\forall a \le x\le b,g_i(x)=g_{i-1}(x)$$$. So we just need to insert $$$a$$$ and $$$b$$$ into some data structure which can support querying how many values are less than x.

Here is my Implementation:137124792

Still unsure about how to tackle D. Any hints?

Can anyone help me to understand jiangly solution for the problem E: https://codeforces.me/contest/1614/submission/137002860

What is the variable v and what the erase function does?

I was having a lot of trouble understanding editorial for D2, finally figured it out. Sharing my code here in case anyone is also confused like I was. 137185957

The tricky part is actually calculating cnt[i] in O(CloglogC), you have to be very careful with double counting. As a simple example, say your array is [2, 4, 6, 12]. Here 12 is divisible by both 2*2 and 2*3, so while computing cnt[2] you might double count it.

for B question i did the exact same thing assigning the main office coordinate to 0 next -1 next 1 then -2 and so on but i still it says my answer is wrong for test case 1 can anyone identify what's wrong in my code it would help me a lot

link to my submission code

i'm lost.

in problem C we have ranges and the bitwise OR of each element in range.

suddenly we're counting each bit of all elements? we don't even know the array, right? why don't we need to recover the array?? i'm confused.

can someone please ease my confusion :( i need help

I understood the solution proposed for C but why O(NlogN) solution doesn't pass for problem C?

Submission: 137045013

What is the dp solution for problem C?

Could anyone give me a proof about the time complexity of the solution for E? Thanks a lot.

Sorry for my poor English.

Problem C is hard to understand. Help me :(

Editorial for D1 isn't written very well, here is a (hopefully) better explanation:

Let us assume that we know the optimal reordering of the array $$$a$$$ (which produces maximum score). From this array, let us build the gcd-prefix array $$$g$$$ (where $$$g[i] = gcd(a[1], a[2], a[3] \dots a[i])$$$).

Also, for simplicity ahead, I will be calling $$$g[i]$$$ as the “corresponding gcd element” of the $$$a[i]$$$ in some places ahead (just to emphasise that presence of $$$a[i]$$$ at its position causes $$$g[i]$$$ to obtain its value).

Now what will $$$g$$$ look like? It looks something like:

x x x x (x/a) (x/a) (x/b) (x/b) (x/b) (x/c) 1 1 1 (where $$$a$$$ and $$$b$$$ divide $$$x$$$ and $$$x/a > x/b$$$)

The key observation to make is that in the optimal ordering, if $$$a[i]$$$ was causing $$$g[i]$$$ to be, say $$$x/b$$$ it is not possible to move $$$a[i]$$$ to some position $$$j (j < i)$$$ such that it would have produced $$$x$$$ or $$$x/a$$$ over there (Because otherwise that would mean our array is not optimal, as $$$x/a > x/b$$$), so this implies that any $$$a[i]$$$ whose corresponding gcd element is $$$x/b$$$ cannot be a multiple of $$$a$$$ or $$$x/a$$$.

Another way to state this: In optimal ordering, it is not possible to move the ith element $$$a[i]$$$ to some position $$$j < i$$$ and increase its corresponding gcd element such that corresponding gcd element of the rest of the elements remains the same.

So now let us try building our solution using this fact, and with the help of dynamic programming.

Let us define $$$dp[x]$$$ as the maximum sum we can get if the gcd of all the elements we chose till that point is $$$x$$$.

Now you might be intuitively thinking that this state does not seem complete, as the number of elements (and which elements) we have chosen is important and yet I make no mention of it. The thing is we do not need to, as by our observation we can see that in $$$dp[x]$$$, we must have picked all the multiples of $$$x$$$, as otherwise their corresponding element will be $$$<x$$$ and that wont be optimal.

How to do transitions? Now as $$$max(a[i])$$$ is small, we can build an array $$$occ[i]$$$ using a sieve like approach which will represent the number of factors that i has in the given array.

When transitioning from $$$x$$$ to some $$$x/a$$$ we can see that we basically use all the multiples of $$$x/a$$$ (except multiples of $$$x$$$ as they will already have been used). So: \begin{equation} dp[x] = max(dp[i.x] + (occ[i.x] — occ[x]).x) \end{equation}

Finally, our answer will be $$$max(dp[i])$$$.