vovuh's blog

Codeforces Round #560 (Div. 3) Editorial
By vovuh, history, 6 years 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

Comments Comments (30)
| Write comment?
»
6 years 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 ?

→ Reply
»
6 years 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. :(

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But it's trivial

    → Reply
    • »
      »
      »
      6 years 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?

      → Reply
      • »
        »
        »
        »
        6 years 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.

        → Reply
        • »
          »
          »
          »
          »
          6 years 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?

          → Reply
»
6 years 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?

→ Reply
»
6 years 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?

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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?

→ Reply
»
6 years 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 :'( ?

→ Reply
»
6 years 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?

→ Reply
»
6 years 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

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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)?

→ Reply
  • »
    »
    6 years 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).

    → Reply
»
6 years 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?

→ Reply
»
5 years 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.

→ Reply
»
5 years 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

→ Reply
»
5 years 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??

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Of course we can. But there is a special case when X = p * p, then divisors array = {p}, in this case just take lcm = p^2.

    → Reply
»
5 years 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)?

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

    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

    → Reply