4qqqq's blog

By 4qqqq, 2 months ago, In English

A. Divan and a Store

Solution

B. Divan and a New Project

Solution

C. Divan and bitwise operations

Solution

D1. Divan and Kostomuksha (easy version)

Solution

D2. Divan and Kostomuksha (hard version)

Solution

E. Divan and a Cottage

Solution
 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

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

Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Is the dynamic programming approach used in D1 a known concept?

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

    I'm not sure what you mean by "known" here, but the idea isn't too insanely extraordinary, at least for D1.

»
2 months ago, # |
  Vote: I like it +30 Vote: I do not like it

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?

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

    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)

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

    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.

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

    It is the result of Mertens' theorem.

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

    I see this problem before, but instead of counting the maximum sum, we need to count expect value of the sum. Can you help me with this :(((

»
2 months ago, # |
  Vote: I like it +114 Vote: I do not like it

Imagine statements were this short

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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://codeforces.com/contest/1614/submission/137071970

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

For the second question, my approach seems to be $$$O(Tn)$$$

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

$$$cnt_i$$$ is the amount of $$$a_i=i$$$.

Really? I think $$$cnt_i$$$ is the amount of $$$j$$$ such that $$$a_j\bmod i=0$$$.

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

That feeling when you wasted 4 attempts on problem C because of wrong modulo :’)

»
2 months ago, # |
  Vote: I like it -25 Vote: I do not like it

What's the f**k!

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

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.

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

    I think we shouldn't focus on 10 years time, that's of no use.

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

      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!

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

My solution in Problem B was clearly of time complexity O(nlogn) and I still got TLE!

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

    You are storing index of each a[i] using a hashMap. Suppose that there are many a[i] which are identical in that case at some point the List map.get(i) will reach a limit and will have to increase its size and cost of that is o(N) which will make it a quadratic equation. That is one thing I see.

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

    Use an ArrayList of Integers and Collections.sort(), it's always O(nlogn). Arrays.sort() is O(n^2), although docs say it is O(nlogn).

»
2 months ago, # |
  Vote: I like it +47 Vote: I do not like it

Terrible editorial for D1 and D2 with no code ? Its very confusing,probably some translation error

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it +30 Vote: I do not like it

    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

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

      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 ^_^

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

      Thank you

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      In D2, we have to compute cnt too, but computes it takes O(ClogC). So is the real complexity of D2 O(ClogC)?

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

      I don't understand. If $$$a = [10, 15]$$$ , $$$dp_5 = 5 \cdot 2 = 10$$$, but clearly the answer for such $$$a$$$ is $$$20$$$

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

Can’t understand E’s solution. Can anyone explain more detail?

»
2 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Here are the video Solutions for problems A-D1 In case you are interested.

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

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.

»
2 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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)

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

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

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

Still unsure about how to tackle D. Any hints?

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

Can anyone help me to understand jiangly solution for the problem E: https://codeforces.com/contest/1614/submission/137002860

What is the variable v and what the erase function does?

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

    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 the erase part, 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

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It's really nice explanation. As you mentioned, we have to loop for primes in advance to avoid double counting.

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

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

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

    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.

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

      if you see my submission you can see that i have sorted the array using the stl sort function

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

        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.

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

I didn't understand the approach for problem D1, can someone please give a more clearer picture

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

1

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

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

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

    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.

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

      still can't wrap the idea around my head.. i think i'll come back to this problem later

      thanks for replying!

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

      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!

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

        Or-ing all gives all possible set bits i.e x

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

Has anyone submitted problem B in Java? I'm getting tle on testcase 4.

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

I understood the solution proposed for C but why O(NlogN) solution doesn't pass for problem C?

Submission: 137045013

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Submission for D2

Could anyone please explain what's wrong in my code? I wonder why it were be Runtime Error. thank u guys.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me why i am getting tle https://ide.codingblocks.com/s/646213

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

What is the dp solution for problem C?

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

..