### vovuh's blog

By vovuh, history, 3 years ago, 1165A - Remainder

Idea: vovuh

Tutorial
Solution

1165B - Polycarp Training

Idea: MikeMirzayanov

Tutorial
Solution

1165C - Good String

Idea: BledDest

Tutorial
Solution

1165D - Almost All Divisors

Idea: MikeMirzayanov

Tutorial
Solution

1165E - Two Arrays and Sum of Functions

Idea: vovuh

Tutorial
Solution

1165F1 - Microtransactions (easy version)

Idea: BledDest

Tutorial
Solution

1165F2 - Microtransactions (hard version)

Idea: BledDest

Tutorial
Solution Tutorial of Codeforces Round #560 (Div. 3) 560, Comments (68)
 » Still can't understand problem E. Why we take in reverse order array b ?
•  » » if we have two sorted sequence of numbers, let's say, $a_n$ and $b_n$ ($a_1 \leq a_2 \leq a_3 \leq ... \leq a_n$ and $b_1 \leq b_2 \leq b_3 \leq ... \leq b_n$) then the minimum sum of their multiplication ($a_i * b_j$) is $a_1*b_n + a_2*b_{n-1} + ... + a_n*b_1$ (you take the largest value of $a_n$ and pair it with the lowest value of $b_n$ and vice versa) this is known as the rearrangement inequality. https://en.wikipedia.org/wiki/Rearrangement_inequality
 » I was hoping that editorial will give a proof for greedy strategy in problem C. :(
•  » » But it's trivial
•  » » » I don't know. The one I know is very very complex and I am not even sure if it is correct. Could you please tell yours?
•  » » » » Consider the left-most pair that violates the condition. To fix this, we either remove one character from the pair, or one character to the left of the pair. Notice that whichever we do, the effect on the characters to the right of the pair is the same. So, we can always just remove one character from the pair.
•  » » » » » Hello can you please tell that in E question if first i were to multiply min a[i] with its corresponding max b[i] and then apply modulo function how would i do it? Like i want to do first: c[i] = a[i] * b[i] and then c[i]*(n-i)*(i+1) . What is the correct approach of doing modulo?
 » I can't understand problem C.Can any one explain this problem !
•  » » We have a string (lets name it s) which length is n. If we have any pair such that j = i + 1 and s[j] = s[i] and j is even ( j mod2 = 0), then delete these two letters from the s. And now we have a new string s. I hope yout got it
•  » » » Thank u brother
 » Is there any way to prove why a greedy solution works in problem C?
•  » »
 » In Problem E, how do we derive the formula for the number of times $a_i*b_i$ will appear in the final answer?
•  » » 3 years ago, # ^ | ← Rev. 3 →   This is the number of l and r such that a_i and b_i are going to contribute to f(l, r). There are i possible left borders (1,2,...,i),and n-i+1 right borders (i,i+1,...,n). We can choose those borders independently, so the number of ways of doing this is i*(n-i+1) according to the product rule.
•  » » » Thank u,I understand.
•  » » » can u please tell the approach we would use if we were allowed to reorder array 'a' also!Thanks in advance!
•  » » » » Then it is easy to see that we would pair the least a[i] and b[i] with the index that has the maximum frequency and the greatest a[i] and b[i] with the index that has the least frequency .. and this way we would ensure that the ans is always minimised. frequency of ith index = (i+1)*(n-i)
 » I have a question on F1. So far what I understand is that you buy the microtransactions on the last day of their sales, unless you can buy out all of the items on the current day. However I am confused since the last day of the sale might be far away, and it would be more optimal to use the current sale. For instance, if you have only have 1 item, and 7 microtransactions for it, with sales on day 5 and 10, this algorithm will not do anything until day 10, where it will buy all of the microtransactions that it needs to, and finish off on day 10.However, you could just spend 5 bourles on day 5, and then buy two transactions on day 9, to finish off the purchases on day 9, which occurs before day 10.Obviously either my understanding of the problem or tutorial is flawed and I would greatly appreciate it if someone could explain my mistake to me.
•  » » Binary search succeeds for day = 10, so we search over the range 1 to 9 and finally arrive at 9 to be the minimum day I think.
 » 54222326. Can't Understand, what is the problem in my solution in B?
•  » » If the Input is 1 5 5 then answer should be actually 3. But i think your sol'n will give 2 as answer.
•  » » » Right! Thank you...
 » In F the question doesn't ask us to keep the money spent minimum, so why don't we buy all type on the first day?
•  » » you need to have enough money
 » 3 years ago, # | ← Rev. 2 →   In problem E, I still don't understand why the value (ai * bi) occur i * (n — i + 1) times in the answer!Can someone explain it to me :'( ?
•  » » 21 month(s) ago, # ^ | ← Rev. 3 →
 » I got "Time limit exceeded on Test case 5" in the Remainder question. Can anybody some explanation.
•  » » Bro if u are using this step:"string h=h+s[i]" to push back a char s[i] in some string h then dont do it as it is inefficient try doing this as h.push_back(s[i]); I had this problem too though its punishment seems a bit too harsh
•  » » » Holy cow. It does work. Thanks!!
 » 3 years ago, # | ← Rev. 3 →   for problem C i am following a 2 pointer approach.In beginning both pointer points to element 0 r=0 l=0 next if s[r]!=s[l] i add this mair to empty string h else r++This is my code it times out for 5 th testcase since i am increasing" r "in every step it must be a O(n) solution and editorial too is O(n) dont know why it times out. #include using namespace std; int main(){ int n; cin>>n; string s; cin>>s; int l=0; int r=0; string h=""; while(r
 » looking at this editorial i am feeling like i could have easily done problem B,C,D but i don't know why i wasn't able to do them while the contest was running : (
 » Problem D(w.r.t. tutorial): why is it necessary to check that x is the correct answer?
•  » » Because you might have a case where you constructed the possible answer x from minimum and maximum but when you factorize the x you have some different values than the given array. Eg- A=[2,3,4,6,8]You will say x=16 but 3 will never be a factor of 16. So we can't form an answer from that.
 » 3 years ago, # | ← Rev. 2 →   could anyone explain F about its second example? why it is not 21? 21 = 3(on sale) + 2 * 9(not on sale)
 » Getting TLE on test case 10 in problem E ... My solution is in JAVA ... Anybody please help me out
•  » » It's bec of the Arrays.sort (dual pivot quicksort algorithm which has n^2 in worst case scenario), so must use mergesort or collection library. It happened with me too :( here you can see.
•  » » » Thanks
 » Problems were wonderful .But problem A as first problem of div3 doesn't go . Problem D , There no need to be sorted only take minimum and maximum element by an array . My solution https://github.com/joy-mollick/Codeforces-B-C-D-Problem-Solutions/blob/master/D%20-%20Almost%20All%20Divisors.cpp
 » In problem E val[i] should be a[i]*i*(n-i+1) but why is it multiplied by (i+1)*(n-i)?
•  » » You're approach would've been okay if the whole array was considered everytime. But that is not the case here. The problem statement wasn't able to make it clear but what we have to do here is, we have to minimize the sums of all the subarrays of the array. For this problem, you don't require to figure out how many subarrays the array will have. An array [1, 4, 3] has 6 subarrays. , [1,4], [1,4,3], , [4,3], . For this problem we have to calculate how many times a particular index will be in a particular subarray. Take the array above for example. Here the element 4 occurs in a total of 4 subarrays. The element 3 in 3 subarrays and the element 1 in 3 subarrays. This is calculated using the formula [i * (n — i +1)] The approach here is very simple. Take one thing in mind here, we only have to change the order of the second array. The first array will be the same. And each element in the first array will occur [i * (n — i +1)] times. So first you multiply each element in the first array with [i * (n — i +1)]. Put these in a separate array and sort that in Ascending order. Then sort the second array in descending order. Now if you multiply each element of the two sorted arrays the final value will be minimum. Don't forget to mod the answer each time.
•  » » » Thanks!
•  » » Because array index starts from 0.
 » In problem E, why are we taking the extra term i*(n-i-1)?
•  » » Because it is a double summation.When you'll simplify it,you'll get that term.Think like: The no. of sequences(l,r) of which (ai*bi) is a part .'l' can be chosen in 'i' no. of ways whereas 'r' can be chosen in 'n-i+1' no. of ways (all possible combinations are valid).So each term will have contribution i*(n-i+1).
 » I still don't understand why the solution of D use vector> val(n).What's the use of val[i].second here?
 » Problem D solution, if i change the for iterationfor (int i = 2; i*1ll*i <= x; ++i){~~~}for (int i = 2; i*i <= x; ++i){~~~}erase "1ll" makes TLE in TC2 why does it happens? I think just overflow the range of expression in (int-long) does not make execution time longer, makes wrong answer but this in this case, makes TLE
•  » » Because you declared i as int and i*i can lead to overflow that gives negative result for (i*i) then it would never be greater than x. (i*i <= x) loop runs always that is why you have to put 1LL*i*i it will convert into long long Hope you get it.
•  » » » oh!! i understand it thank you!
 » Regarding Problem C My code gives TLE . I've seen the editorial but I can't seem to find the problem in my code which leads to TLE. Here is the link to the code : https://ideone.com/fY10V4
•  » » Hey!! I checked your solution for quite some time and it looks O(n) . Even I am not sure where you're going wrong.
 » Can anyone please tell me where I'm going wrong for the problem F1?https://codeforces.com/contest/1165/submission/54405888
 » F can be solved in $O(n + m \log m)$ using BST or segment tree 54494060 . The time complexity is independent of the range of $d_j, k_i, sum(k)$ if they can be stored in 64 bits integers.I came up with the solution because I didn't see the sentence "sum of all $k_i$ is not less than $1$ and not greater than $2\cdot10^5$" at first.
»
3 years ago, # |
Rev. 4

in problem d why set is causing problem?? can anyone check my code??

# define ll long long

int main() { ios_base :: sync_with_stdio (false); cin.tie (NULL); ll q; cin>>q; while(q--) { ll n; cin>>n; ll arr[n]; ll mn=INT_MAX; ll mx=INT_MIN; set se; for(int i=0;i<n;i++) { cin>>arr[i]; se.insert(arr[i]); mn=min(mn,arr[i]); mx=max(mx,arr[i]); } se.insert(1); ll fact=mn*mx; se.insert(fact); int pos=1; for(int i=1;i<=sqrt(fact);i++) { if(fact%i==0) { if(se.find(i)==se.end()) { pos=0; break; } if(se.find(fact/i)==se.end()) { pos=0; break; } }

}
if(pos==0)
cout<<-1<<endl;
else
cout<<fact<<endl;
}

}

•  » »
 » I explained problem E in detail in my Youtube video, enjoy. https://www.youtube.com/watch?v=ThjkHw6vxv8
•  » » I can't understand problem B. Can you please explainthe problem with the test cases??
 » for d why can't the answer be the lcm of given divisors??
•  » » 3 years ago, # ^ | ← Rev. 4 →   Because lcm of given divisors is the min number that is divisible by all the given divisor but the problem is to find the min number x that has ONLY 1, x, and given divisors as its divisors. - for example, 4 6 lcm(4, 6) is 12 but the divisors of 12 include 2, 6, 3, 4, 1, 12 not only 4, 6, 1, 12
 » Why My Solution for Problem C in Java giving TLE?
 » I can't understand problem B. Can anyone explain me the problem with the test cases. I still don't see the solved code after seeing the editorial it is not clear to me.plz help me
 » 3 years ago, # | ← Rev. 2 →   why solution (http://codeforces.com/contest/1165/submission/54829482) is giving wrong answer(for problem E).
 » Can anyone help me with problem e bcoz i am not understanding after the first summation of a[i]*b[i] i.e. summation(f(l,r))? how did we get val[i]=a[i]*i*(n-1-i)?
 » 3 years ago, # | ← Rev. 3 →   In problem E code, Is there any reason why vector of pair is used ? The code works also if we use vector long long ?
 » 2 years ago, # | ← Rev. 2 →   What's wrong with this approach for problem E: Multiply the smallest element of 'a' to biggest of 'b' for each element in 'a'.Let us define dp[i] as the sum of all subarrays ending at i. Then dp[i]=f(0,i)*(i+1)-g(i-1);where g(i) is f(0,0)+f(0,1)+...+f(0,i)so answer will be sum+=dp[i] for all i.
 » 2 years ago, # | ← Rev. 3 →   Hello, i have a question for Problem D: In test case #6: 13 802 5 401 4010 62 2 12431 62155 310 10 31 2005 24862 the expected answer is : -1, when the correct answer should be 124310, could someone explain what am i missing ? Thanks
•  » » The answer -1 is correct. If the value for n is odd, it means that the number can be represented as d[n/2]*d[n/2], where d is its divisors array. Thus we need to add the d[n/2] element again in the array, and then sort it. In this case, the added element will be 401, which can't be true, because 401*401 is not equal to 2*62155`. So the result is -1
•  » » » I think you're overkilling the explaination here.The main reason that lcm of all number does not work is due to the fact that LCM might have extra divisor other than what are given in the initial array.For example: In the test number #6 : d[] = 13 802 5 401 4010 62 2 12431 62155 310 10 31 2005 24862The LCM is 124310, But if you check the divisors of this number those are: [2 802 5 10 4010 62155 12431 401 2005 310 155 24862 62 31], Hence there is this one extra (155) number present in the list of divisor, whereas it's not there in the d[].Hence, It's not a suitable answer, and no answer if suitable for d[] for that matter.I hope this helps.
 » What's wrong with my code in problem E: https://codeforces.com/problemset/submission/1165/131039333