Vovuh's blog

By Vovuh, history, 5 months ago, In English,

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
 
 
 
 
  • Vote: I like it
  • +32
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Still can't understand problem E. Why we take in reverse order array b ?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was hoping that editorial will give a proof for greedy strategy in problem C. :(

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But it's trivial

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand problem C.Can any one explain this problem !

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any way to prove why a greedy solution works in problem C?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem E, how do we derive the formula for the number of times $$$a_i*b_i$$$ will appear in the final answer?

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

54222326. Can't Understand, what is the problem in my solution in B?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If the Input is 1 5 5 then answer should be actually 3. But i think your sol'n will give 2 as answer.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 :'( ?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got "Time limit exceeded on Test case 5" in the Remainder question. Can anybody some explanation.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; string s; cin>>s; int l=0; int r=0; string h=""; while(r<n){ if(s[r]!=s[l]){ h=h+s[l]; h=h+s[r]; l=r+1;

}
r++;

} cout<<s.length()-h.length()<<endl; cout<<h<<endl;

} `

EDIT: Got it using "h=h+s[l]" this step is inefficient to do we should try doing this as h.push_back(s[l]); which is more efficient

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 : (

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D(w.r.t. tutorial): why is it necessary to check that x is the correct answer?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

could anyone explain F about its second example? why it is not 21? 21 = 3(on sale) + 2 * 9(not on sale)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Getting TLE on test case 10 in problem E ... My solution is in JAVA ... Anybody please help me out

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E val[i] should be a[i]*i*(n-i+1) but why is it multiplied by (i+1)*(n-i)?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because array index starts from 0.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, why are we taking the extra term i*(n-i-1)?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I still don't understand why the solution of D use vector<pair<long long, int>> val(n).What's the use of val[i].second here?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D solution, if i change the for iteration

for (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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey!! I checked your solution for quite some time and it looks O(n) . Even I am not sure where you're going wrong.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me where I'm going wrong for the problem F1?

https://codeforces.com/contest/1165/submission/54405888

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

}

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I explained problem E in detail in my Youtube video, enjoy. https://www.youtube.com/watch?v=ThjkHw6vxv8

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can't understand problem B. Can you please explainthe problem with the test cases??

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for d why can't the answer be the lcm of given divisors??

  • »
    »
    3 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why My Solution for Problem C in Java giving TLE?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

why solution (http://codeforces.com/contest/1165/submission/54829482) is giving wrong answer(for problem E).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In problem E code, Is there any reason why vector of pair is used ? The code works also if we use vector long long ?