### vovuh's blog

By vovuh, history, 18 months 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

• +32

 » 18 months ago, # |   -6 Still can't understand problem E. Why we take in reverse order array b ?
•  » » 18 months ago, # ^ |   0 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
 » 18 months ago, # |   0 I was hoping that editorial will give a proof for greedy strategy in problem C. :(
•  » » 18 months ago, # ^ |   0 But it's trivial
•  » » » 18 months ago, # ^ |   0 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?
•  » » » » 18 months ago, # ^ |   +4 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.
•  » » » » » 17 months ago, # ^ |   +1 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?
 » 18 months ago, # |   0 I can't understand problem C.Can any one explain this problem !
•  » » 18 months ago, # ^ |   0 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
•  » » » 18 months ago, # ^ |   0 Thank u brother
 » 18 months ago, # |   0 Is there any way to prove why a greedy solution works in problem C?
•  » » 18 months ago, # ^ |   0
 » 18 months ago, # |   0 In Problem E, how do we derive the formula for the number of times $a_i*b_i$ will appear in the final answer?
•  » » 18 months ago, # ^ | ← Rev. 3 →   +1 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.
•  » » » 17 months ago, # ^ |   0 Thank u,I understand.
•  » » » 11 months ago, # ^ |   0 can u please tell the approach we would use if we were allowed to reorder array 'a' also!Thanks in advance!
 » 18 months ago, # |   0 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.
•  » » 17 months ago, # ^ |   0 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.
 » 18 months ago, # |   0 54222326. Can't Understand, what is the problem in my solution in B?
•  » » 18 months ago, # ^ |   0 If the Input is 1 5 5 then answer should be actually 3. But i think your sol'n will give 2 as answer.
•  » » » 18 months ago, # ^ |   0 Right! Thank you...
 » 18 months ago, # |   0 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?
•  » » 17 months ago, # ^ |   0 you need to have enough money
 » 18 months ago, # | ← Rev. 2 →   0 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 :'( ?
•  » » 2 months ago, # ^ | ← Rev. 3 →   0
 » 17 months ago, # |   0 I got "Time limit exceeded on Test case 5" in the Remainder question. Can anybody some explanation.
•  » » 17 months ago, # ^ |   0 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
•  » » » 17 months ago, # ^ |   0 Holy cow. It does work. Thanks!!
 » 17 months ago, # | ← Rev. 3 →   0 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
 » 17 months ago, # |   0 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 : (
 » 17 months ago, # |   0 Problem D(w.r.t. tutorial): why is it necessary to check that x is the correct answer?
•  » » 17 months ago, # ^ |   0 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.
 » 17 months ago, # | ← Rev. 2 →   0 could anyone explain F about its second example? why it is not 21? 21 = 3(on sale) + 2 * 9(not on sale)
 » 17 months ago, # |   0 Getting TLE on test case 10 in problem E ... My solution is in JAVA ... Anybody please help me out
•  » » 17 months ago, # ^ |   0 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.
•  » » » 17 months ago, # ^ |   0 Thanks
 » 17 months ago, # |   0 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
 » 17 months ago, # |   0 In problem E val[i] should be a[i]*i*(n-i+1) but why is it multiplied by (i+1)*(n-i)?
•  » » 17 months ago, # ^ |   0 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], [1,4], [1,4,3], [4], [4,3], [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.
•  » » » 17 months ago, # ^ |   0 Thanks!
•  » » 13 months ago, # ^ |   0 Because array index starts from 0.
 » 17 months ago, # |   0 In problem E, why are we taking the extra term i*(n-i-1)?
•  » » 17 months ago, # ^ |   0 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).
 » 17 months ago, # |   0 I still don't understand why the solution of D use vector> val(n).What's the use of val[i].second here?
 » 17 months ago, # |   0 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
•  » » 17 months ago, # ^ |   0 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.
•  » » » 17 months ago, # ^ |   0 oh!! i understand it thank you!
 » 17 months ago, # |   0 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
•  » » 17 months ago, # ^ |   0 Hey!! I checked your solution for quite some time and it looks O(n) . Even I am not sure where you're going wrong.
 » 17 months ago, # |   0 Can anyone please tell me where I'm going wrong for the problem F1?https://codeforces.com/contest/1165/submission/54405888
 » 17 months ago, # |   0 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.
»
17 months ago, # |
Rev. 4   0

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;
}

}

•  » » 17 months ago, # ^ |   0
 » 17 months ago, # |   +1 I explained problem E in detail in my Youtube video, enjoy. https://www.youtube.com/watch?v=ThjkHw6vxv8
•  » » 17 months ago, # ^ |   0 I can't understand problem B. Can you please explainthe problem with the test cases??
 » 17 months ago, # |   0 for d why can't the answer be the lcm of given divisors??
•  » » 15 months ago, # ^ | ← Rev. 4 →   0 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
 » 17 months ago, # |   0 Why My Solution for Problem C in Java giving TLE?
 » 17 months ago, # |   0 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
 » 17 months ago, # | ← Rev. 2 →   0 why solution (http://codeforces.com/contest/1165/submission/54829482) is giving wrong answer(for problem E).
 » 17 months ago, # |   0 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)?
 » 15 months ago, # | ← Rev. 3 →   0 In problem E code, Is there any reason why vector of pair is used ? The code works also if we use vector long long ?
 » 9 months ago, # | ← Rev. 2 →   0 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.
 » 8 months ago, # | ← Rev. 3 →   0 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
•  » » 5 months ago, # ^ |   0 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