To solve this problem, let's use the following greedy algorithm.
Let's sort the prices of chocolate bars in increasing order, after which we will go from left to right and take chocolates that have a price not less than $$$l$$$, but not more than $$$r$$$ until we run out of money.
The number of chocolate bars that we took will be the answer to the problem.
The resulting asymptotics in time: $$$\mathcal{O}(n\log{}n)$$$.
Obviously, the more often we have to go to the $$$ i $$$ building, the closer it should be to the main office.
This implies a greedy algorithm. Let's put the main office at $$$0$$$ and sort the rest by $$$a_i$$$. Then we put the most visited building at a point with a coordinate of $$$1$$$, the second at $$$-1$$$, the third at $$$2$$$, etc.
The resulting asymptotics in time is $$$\mathcal{O}(n\log{}n)$$$.
C. Divan and bitwise operations
Let's count for each bit how many times it will be included in the answer.
Let us now consider the $$$i$$$-th bit. Note that if no number contains the included $$$i$$$-th bit, then such a bit will never be included in the answer. Otherwise, each of the subsequences contains $$$i$$$-th bit even or odd number of times. If a bit enters an even number of times, then we should not count such a subsequence, because the bitwise exclusive OR for this bit will be zero. If the bit enters an odd number of times, then we must count such a subsequence, because the bitwise exclusive OR for this bit will be equal to one.
It is stated that the number of subsequences in which the $$$i$$$-th bit enters an odd number of times is equal to $$$2^{n - 1}$$$. Let's prove it.
Divide the numbers into two sets $$$A$$$ and $$$B$$$. In the set $$$A$$$ there will be numbers whose $$$i$$$th bit is off, in the set $$$B$$$ there will be numbers whose $$$i$$$-th bit is on.
Note that the numbers from the set $$$A$$$ do not affect the answer in any way, because $$$x\; XOR\; 0 = 1$$$. Thus, whichever subset of $$$A$$$ we take, the $$$i$$$-th bit will not change its parity. There will be $$$2^{|A|}$$$ in total of such subsets.
Let $$$k = 1$$$ if $$$|B|$$$ is even, or $$$k = 0$$$ if $$$|B|$$$ is odd. In order for the $$$i$$$-th bit to enter the subsequence an odd number of times, you need to take an odd number of elements from the set $$$B$$$. This number is equal to $$$C_{|B|}^{1} \, + \, C_{|B|}^{3} \, + \dots \, + \, C_{|B|}^{|B| - k} = 2^{|B| - 1}$$$.
Thus, the $$$i$$$-th bit is included in exactly $$$2^{|A|}\cdot 2^{|B|- 1}= 2^{n - 1}$$$ subsequences, which was required to be proved.
Then the solution to this problem turns out to be very simple: let $$$x$$$ be equal to the bitwise OR of all elements of the sequence (or, the same thing, bitwise OR of all given segments), then the answer will be equal to $$$x\cdot 2^{n - 1}$$$ modulo $$$10^9 + 7$$$.
The resulting asymptotics in time: $$$\mathcal{O}(n)$$$.
D1. Divan and Kostomuksha (easy version)
Let's solve the dynamic programming problem. Let $$$dp_i$$$ be the maximum answer for all arrays, the last element of which is divisible by $$$i$$$. Let's calculate the dynamics from $$$C$$$ to $$$1$$$, where $$$C$$$ is the maximum value of $$$a_i$$$. Initially, $$$dp_i = cnt_i \cdot i$$$, where $$$cnt_i$$$ is the amount of $$$a_i = i$$$. How do we recalculate our dynamic programming? $$$dp_i = max(dp_i, dp_j + i \cdot (cnt_i - cnt_j))$$$, for all $$$j$$$ such that $$$j$$$ $$$mod$$$ $$$i = 0$$$ (i.e. $$$j$$$ is divisible by $$$i$$$). In this dynamic, we iterate over the past change of our $$$gcd$$$ on the prefix, and greedily add all possible elements.
The resulting asymptotics in time is $$$\mathcal{O}(C\log{}C)$$$.
D2. Divan and Kostomuksha (hard version)
To solve $$$D2$$$, we can notice that to recalculate the dynamics, we can iterate over all such $$$j$$$ that differ from $$$i$$$ by multiplying exactly $$$1$$$ prime number. Also, to speed up the solution, we can use the linear sieve of Eratosthenes to find primes and factorization.
The resulting asymptotics in time: $$$\mathcal{O}(C\log{}\log{}C) $$$.
Let $$$ans_{temp}$$$ the current answer for temperature $$$temp$$$. Before all days, $$$ans_{temp}$$$ is considered equal to $$$temp$$$.
In order to respond to a request with a temperature of $$$x$$$, we will just need to output the value of $$$ans_x$$$. But how to maintain $$$ans$$$? With the help of an implicit tree of segments, at the vertices of which the minimum and maximum will be stored, as well as the variable $$$add$$$, which will contain the value that needs to be added to the current vertex (that is, such a variable that is needed to perform lazy operations on the segment tree).
At the beginning of the next day you get the temperature $$$T$$$. Now we need to change the current answer for some $$$temp$$$. We need to find such $$$ans_{temp}$$$ that $$$ans_{temp} <T$$$ and add $$$+1$$$ to them, and then find such $$$ans_{temp}$$$ that $$$ans_{temp} > T$$$ and add $$$-1$$$ to them. All this is not difficult to do, just starting from the root of the segment tree and stopping at the moments when:
- the maximum of the current vertex is less than $$$T$$$ — here we add $$$+1$$$;
- the minimum of the current vertex is greater than $$$T$$$ — here we add $$$-1$$$;
- the minimum of the vertex is equal to the maximum of the vertex (and, therefore, the $$$T$$$ itself) — here we do not add anything.
The resulting asymptotics in time: $$$\mathcal{O}(n\log{}T)$$$.
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?
I'm not sure what you mean by "known" here, but the idea isn't too insanely extraordinary, at least for D1.
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?
I think it's related to https://en.m.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes
And prime seive where inner loop is only over primes has this many iterations:
n/2 + n/3 + n/5 + n/7...
(Factor out n)
The answer to you question is yes, the numbers from 1 to n have in total O(nloglogn) unique prime factors (this is result from classic sieve of erasthothenes for listing prime numbers). So each number has on average loglogn unique prime factors.
It is the result of Mertens' theorem.
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://mirror.codeforces.com/contest/1614/submission/137071970
Really? I think $$$cnt_i$$$ is the amount of $$$j$$$ such that $$$a_j\bmod i=0$$$.
I have same doubt.You found?
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.
I think we shouldn't focus on 10 years time, that's of no use.
If that info. is of no use it should not be there in the problem statement. I could not solve the problem just because someone has not used correct wording to explain. Anyways now i get it that i should not give any importance to story part. Thanks for replying!
FOR the test case of
5 1 1 1 1 1
we can place the coords as [-2,-1,0,1,2] and total cost will be 14.But they have total cost as 18,I dk why.....
Terrible editorial for D1 and D2 with no code ? Its very confusing,probably some translation error
Correct me if I'm wrong, but there seems to be multiple errors in editorial of D1.
Let $$$dp[i]$$$ be the maximum answer for all arrays, the last element of which is divisible by $$$i$$$.
should be
Let $$$dp[i]$$$ be the maximum answer if we can pick from the whole array, and every element of the resulting array is divisible by $$$i$$$.
Initially, $$$dp[i]=cnt[i]⋅i$$$, where $$$cnt[i]$$$ is the amount of $$$a[i]=i$$$.
should be
Initially, $$$dp[i]=cnt[i]⋅i$$$, where $$$cnt[i]$$$ is the number of elements in $$$a$$$ that is divisible by $$$i$$$.
Edit: Unfamiliar with comment formatting
and the complex is O( C logC ) , or it will be change ? I could not implement editorial logic so can you sher your code ? THNX ^_^
Yes, it is still $$$O(C log C)$$$, since $$$\frac{n}{1} + \frac{n}{2} + ... + \frac{n}{n} = O(n log n)$$$. You can see it in my implementation. https://mirror.codeforces.com/contest/1614/submission/137105361
Edit: Still unfamiliar with Codeforces comment format
In D2， we have to compute cnt too, but computes it takes O(ClogC). So is the real complexity of D2 O(ClogC)?
Thanks bro, i was confused with cnt part. How to extend this logic to D2
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.
https://mirror.codeforces.com/contest/1614/submission/137112248
This passes
The size of vector v is m not n.
I'm still confused could u explain more?
the for-loop is m-size, so there may be more than n element in the vector, up to 2^n.
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?
A useful video was posted here.
My code for D1 and D2 is here. It's with detailed walkthrough and some insights that I found useful. I've personally spent a long time on this, so hope my work does help you~
Can anyone help me to understand jiangly solution for the problem E: https://mirror.codeforces.com/contest/1614/submission/137002860
What is the variable v and what the erase function does?
I think the thing he's trying to do is maintain "how many numbers less than $$$x$$$ are removed/merged", while $$$v$$$ is the minimum number alive.
For instance, if
T = {1, 1, 0}, $$$v$$$ would first increase to 1, then stays at 1, finally go down to 0. And for theerasepart, the segment tree will hold 1 at position 0 after the first operation (which means $$$v+0$$$ has 1 temperature merged into it).See my submission for more details. 137180586
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.
It's really nice explanation. As you mentioned, we have to loop for primes in advance to avoid double counting.
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
You have to sort the array first then where he visits most should be -1 then 1 then -2, so on. But you didn't sort anything.
if you see my submission you can see that i have sorted the array using the stl sort function
You are printing the coordinates in the wrong order. You have to print it in the order they are given in the input, not in the order they are after you sorted them.
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
Yes you are right! also as Editorial says you have to just take Bitwise OR of an array(Still if you don't have but you have their Bitwise OR) Even You can do that after making Array with those conditions and then you'll see that you are doing same thing.
still can't wrap the idea around my head.. i think i'll come back to this problem later
thanks for replying!
Let's suppose that you have recovered the array for which you will have to firstly group all the intersecting ranges first because if two ranges intersect then you have to assign the intersecting variables such that they satisfy the OR value of both of the ranges. [This is going to take at least nlogn since to find the intersecting ranges you are going to sort the array of ranges by the first value].
Example input: a, b, c
1 2 X
2 3 Y
You will have to assign a value to b such that the OR of both of the ranges is satisfied.
Since you have recovered the array now, to calculate the coziness of the array you will have to generate all the subsequences of the array which is not possible under the given constraints.
Let's stop for a moment and think what are the operations being performed:
1. OR operation inside the ranges. We have already explored the OR operation through which we recovered the array somehow, but finding coziness from the subsequences is not possible under the given constraints.
2. XOR operation inside the subsequences of the array and then their summation for the coziness value. Try to explore what is actually happening during the calculation of the XOR values and then of the coziness value.
[Hint: Consider each bit individually while calculating the XOR.]
yes. this is what i thought, except i didn't know how to calculate the sum of all XOR subsequences before reading the editorial.
why does OR-ing all the elements yields x tho?? (in the editorial)
thanks for the reply!
Or-ing all gives all possible set bits i.e x
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 :(
Uhm... My friend helped me understand the C's editorial so I do not need help anymore. Sorry for this inconvenient.
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])$$$.