Osama_Alkhodairy's blog

By Osama_Alkhodairy, 11 months ago, In English
Tutorial is loading...
code
Tutorial is loading...
code
Tutorial is loading...
code
easier implementation
Tutorial is loading...
code
Tutorial is loading...

Author: MikeMirzayanov

code (pikmike)
Tutorial is loading...
code (mohammedehab2002)
 
 
 
 
  • Vote: I like it
  • +132
  • Vote: I do not like it

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

thanks for the fast editorial :D

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

Wow editorial even before system testing!!

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

The problems were beautiful. Can someone please suggest some similar Project Euler questions to the $$$F$$$ ? It definitely feels like a standard question.

P.S. — Here are my solutions to this lovely contest in case anybody wants to refer my code.

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

It's the first time I have seen editorial coming out before testing. Thanks :D

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

https://codeforces.com/contest/1285/submission/68548219

why my solution fails on pretest 7? what is wrong in my appraoch.

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

    You initial ll ans = LONG_MAX. If answer more than LONG_MAX you get WA. You can use LLONG_MAX

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

can some help me with F classical problem

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

    There's an explanation in the editorial. If you have a more specific question, you should ask it. Simply asking people to explain the problem while there's already an explanation for you to read won't get you anywhere.

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

      Is g if Gcd of whole array

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

        g is the possible GCD of the answer. The answer is eventually going to be LCM(x, y)=x*y/GCD(x, y) for some elements x and y in the array. So, we ask the following question: if I know just the GCD of the two elements that have the max LCM, is it easy (computationally) to find out what the max LCM should be? The answer is yes, and so we iterate over all possible values of what the GCD can be.

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it -10 Vote: I do not like it

          Are we storing gcd of all possible pair

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

            You should try answering these questions yourself first. What would the time complexity be of storing the GCD of all possible pairs? Well, you would have to iterate over all pairs, which would be $$$O(n^2)$$$, so we're not doing that.

            I'll say that F is not an easy problem, and you should have some comfort with number theory and algorithms before tackling it. There are probably easier number theory problems you should tackle first.

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

F : CLassical? Press X for doubt

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

Why tutorial is not available for problem E ?

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

F accepted with a strange bitset solution 68535522

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

    F accepted with a more strangle bitset solution that I can't even calculate it's complexy :D 68657039 Can you help me calculate the complexy?

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

      Maybe O(能过) (

      In fact, I think my solution is $$$O(n^2\log n(\frac{1}{32}+\frac{1}{50}))$$$, where 32 is length of int, and 50 is some magic number. However, it passed.

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

        can please explain what method you have apply

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

        After some hard computing,the complexy that I calculate is O(n^2 log n*log log n/32) After adding some strange optimizations it passed.

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

        It is so hard to calculate it.I use some calculus knowledges to calculate the complexy,but since I'm only 13 and know very little about calculus,maybe I'm wrong.

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

For problem C: My Submission 68521316, I know I did some extra work still I feel that it should not give TLE. Can someone explain why it TLED on the very last case?

Test case 84: 963761198400

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

    because it has 6720 factors and may perform bad on worse than n^2 TC

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

    Maybe this number has 6720 factors, which is much more than any cases before. $$$6720^2log(N)$$$ could cause TLE.

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

    In fact if you iterate over the grater number in a pair of divisors and break immediately after finding an answer, your solution shall pass. Is is safe to approximate number of divisors of X by the cube root of X?

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

      I wrote this solution without thinking much knowing the n^(1/3) bound as discussed here. But as it failed on the very last test, It's better to find a better solution.

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

Can you share who is the author of each problem?

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

    ABCD: me

    E: MikeMirzayanov

    F: DeadPillow

    mohammedehab2002 is a solution author.

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

      OK, my guess was wrong.

      Strange that nobody stopped you from using C. A was nice though.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it -18 Vote: I do not like it

        What's wrong with C? Actually, in the beginning, we weren't aware of the easy implementation! The intended solution was the first one in the editorial.

        What was your guess though? :)

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

          I think I solved that one... 6 years ago? For the first time, I mean. Not sure that today was in first 5.

          My guess was that C was added by MikeMirzayanov to "balance the difficulty".

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

For D, how does recursively solving for each of the groups ensure that we will reach an optimal answer?

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

    We are iterating over bits from higher to lower bit. Now it is known that 2 ^ i > 2 ^ i — 1 + 2 ^ i — 2 + ... + 1

    There can be two cases,

    1. We will be able to get 0 on i th bit of our minimum value.
    2. We will get 1 on i th bit of our minimum value, no matter what.

    Just handle these cases.

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

      But then how is the complexity of code not 2^n

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

        The recursion depth won't be greater than log(a). Now notice that, when we handle the 2nd case, one might think that we will consider the same set of numbers twice. But it is not, because, these two cases are actually complementary set (Because if a number is in L set, it won't definitely be in R set), so we will end up considering each number at most log(a) times.

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

    delete

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

      1300+ now, how long it will take me to get 1600+?

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

        ? what do you mean by saying it?

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

In problem C how can they say there can be atmost 11 prime?

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

    2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 > 10 ^ 12

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

Why does the complexity at problem D is O(Nlog(a)) instead of O(N*2^(log(a))) = O(N*a) ?

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

Problem B, 10, 10 5 -12 7 -10 20 30 -10 50 60

The maximum tastiness for Adel is 110, the sum of the array is 150, why is the answer No?

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

    Nevermind, I found my own mistake.

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

      what was the mistake? I still don't know why the answer is No

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

        [20 30 -10 50 60] if you sum them up, they are 150 so Adel's max is 150. My mistake was, whenever my program encountered a negative number it wouldn't add them up and it would start over from 0. It should sum them up if the sum is greater than 0.

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

Solution without any difference array or binsearch — 68562620

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

for(int i = 0 ; i < (1 << n) ; i++){ ll a = 1, b = 1; for(int j = 0 ; j < n ; j++){ if((i >> j) & 1) a *= f[j]; else b *= f[j]; } I know they are bitwise operator and left shift and right shift but what it is doing can someone tell

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

please explain f classical problem

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

Anyone can teach me or give me a link to understand bruteforce please? Thanks in advance.

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

Your F is easy to optimise to $$$\mathcal{O}(V \log V)$$$, where $$$V$$$ is the upper bound on the input values.

For any input number $$$a$$$, we can add its divisors into our input numbers, as using $$$a$$$ over them cannot make the LCA smaller. This is easy to do in $$$\mathcal{O}(V \log V)$$$ time.

Then it suffices to find the two coprime numbers with maximum product, as if the optimal answer uses numbers $$$a$$$ and $$$b$$$, it could just as well use the coprime numbers $$$a$$$ and $$$\frac{b}{gcd(a, b)}$$$ instead. Then we do not need to loop $$$g$$$, and doing what is described in the editorial for $$$g = 1$$$ takes $$$\mathcal{O}(\sum_{i = 1}^{n} \sigma_{0}(i)) = \mathcal{O}(V \log V)$$$ time.

Submission: 68564248

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

    Okay this is so cool! I'll try to compile the other solutions I know here.

    There's an $$$O(V^2)$$$ idea: for each number $$$a_i$$$ we can repeat the following: keep a list of all the numbers in the array, and take the largest element in the list; let's call it $$$m$$$. You can maximize the answer with $$$LCM(a_i,m)$$$, and then every multiple of $$$GCD(a_i,m)$$$ is useless because it can never give a better answer, so you can erase them from the list and repeat.

    If instead of the list you keep a 0/1 array that tells you which elements exist in the list, you can optimize all these operations with bitset to achieve an $$$O(\frac{V^2}{32})$$$ solution.

    Credits: FSTForces

    There's also a good randomized solution based on this trick. Choose a random permutation, and then the expected number of indices that increase the answer is $$$O(log(n))$$$. So, for each element in the permutation, if you can check whether it could increase the current answer and the check is positive, you can just try LCMing it with every single element in the array, since there are only $$$O(log(n))$$$ elements that will give a positive check! To perform this check, you can iterate through the divisors $$$d$$$ of $$$a_{p_i}$$$, and then you want to check if there's an element $$$a_j$$$ such that $$$\frac{a_{p_i}*a_j}{d}>ans$$$ and $$$GCD(a_{p_i},a_j)=d$$$. Which is equivalent to $$$a_j>\frac{ans*d}{a_{p_i}}$$$ and $$$\frac{a_j}{d}$$$ is coprime with $$$\frac{a_{p_i}}{d}$$$. The editorial describes how to count the number of elements coprime to an element in an array. This problem is the same but for a suffix.

    We also received a ton of heuristics that, together, are probably unbreakable.

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

Is there anyone who has solved problem D with DP Please share your algo :)

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

any other approach for problem D ??

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

    You can solve it using trie :)

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

      Nice! One question, maybe it's because I don't know enough about trie. Do you know why people call the function "search" (example below is solve) with search(1, 30) or search(0, 29)?

      Example: Code

      I don't understand why the guys are using 29 (or 30) and not any other number. I think this is kind of Level of the tree. Can you help?

      Thanks!

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

        Because the max number in the array will be ($$$2^{30} - 1$$$)

        and in the trie we traverse on bits so we have maximum 30 bits to traverse on it, think about binary representation.

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

          I get it now. Thank you!

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

          Can i Know how the size like 'trie[10000006][2]' has been defined.

          why 10000006 ?

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

            you have at max $$$10^5$$$ numbers and each number could make 30 child(number of bits) and for each one of them 2 values are assigned to them(which is 0 or 1)

            So at the end you need $$$10^5$$$ $$$*$$$ $$$30$$$ $$$*$$$ $$$2$$$

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

      Yup.

      Code If anyone's interested

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

Not understanding the editorial of E, can some one elaborate more on the approach? thanks!

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

    Yes, I also don't really understand the solution after the part about building the initial union of all segments.

    Any help is much appreciated thanks.

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

      I was also a little confused before I read the code.

      Instead of building the initial union, the code get()s all the right borders of the union, ls, and the initial number of segments, cur.

      And while you process() the intervals(i.e. scanning them), you check if there is there is exactly a open segment $$$x$$$ before the current right segment, and if there is, ++ans[x](the difference if you remove x). Otherwise, the current right border would not appear in any answer.

      Finally, you solve() the question by checking if removing segment $$$x$$$ will remove a right border in ls, then adding ans[x] to cur.

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

        Thanks!

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

        can you please explain what does it mean by "adding update" in the editorial of E?

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

Can anyone find the mistake in my code? I got the wrong answer on test 63 and I have no idea how to fix it. 68545474

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

Please correct me if I'm wrong but in the code for D above

Isn't the line

if (l.size() == 0) return solve(r, bit - 1)

meant to be

if (l.size() == 0) return solve(r, bit - 1) + (1 << bit)

EDIT: Sorry, I misunderstood the problem statement I thought we were supposed to find the value of X.

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

Thanks for an excellent set of problems and a timely well-written editorial!

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

In problem C, why are there at most 11 distinct primes?

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

Can anyone suggest some other problems similar to Problem D?

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

I didn't understand the part where we said that bit will be 1 if both groups will be non-empty. Will anyone give me an example to understand that part of the problem D

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

    Consider 5,6,7 the answer is 2.

    The 3rd bit in all of them is set, therefore, we can set the 3rd bit in X to make sure that the 3rd bit in the answer is 0.

    The 2nd bit is set in 6 and 7 but not in 5 so no matter we set it in X or not it will be set in the answer because when we XOR it with them there will be a difference between X and at least one of them.

    Now 5 is in one group and 6,7 are in another. In the group that consists of only 5 we have the 1st bit set to 1, therefore, we set the 1st bit in X to 1. So X should be either 5 or 7 and the answer is 2.

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

      could u tell me whats wrong in my code , i mean i am using dp for each bit of X with 0 and 1 reflecting the on and off state Code?

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

    If both groups are non-empty then we perform 3rd return statement and look carefully there is addition of 2**i for ith bit

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

    << from editorial : If both groups aren't empty, whatever value we assign to the current bit of X, we will have this bit on in our answer. >>

    Let n=2, two numbers are 9(1001) and 5(0101) . And we are considering the 3rd bit (counted from 0). On the value of x ..

    if we on that bit .. (so x=1000 now) after xor two numbers will be 1(0001) and 13(1101), ans=13 if we on that bit .. (so x=0000 now) after xor two numbers will be 9(1001) and 5(0101) , ans=9

    the 3rd bit is ON in either cases . Hope u got it.

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

For problem F ,I used an amazing greedy algorithm ,of course it is wrong ,But why I got TLE instead of WrongAnswer? https://codeforces.com/contest/1285/submission/68568056

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

    ok... , I only let 3000=2750 it got WA instead of TLE.

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

    Be careful ,man .Don't expect to pass a problem without the proper solution.

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

Can someone tell me why this solution is getting timed out for question C? https://codeforces.com/contest/1285/submission/68565564

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

    In for loop use long long instead of integer the variable is overflowing and it is giving TLE

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

1) https://codeforces.com/contest/1285/submission/68534255 2) https://codeforces.com/contest/1285/submission/68585814

Why the 1st code gives wrong ans for test 7 while the 2nd code works fine ?
( only difference between the two is initial value of ans, LONG_MAX doesn't work while 10^12 works)

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

    Value of LONG_MAX is equivalent to INT_MAX. You should have used LLONG_MAX. Try to print all of them and compare.

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

Can someone explain how the complexity for problem F is derived?Won't we be looping over a number's divisors multiple times each time it enters the routine to calculate the maximum product of two coprime numbers (to find if there still is a number coprime to it in the stack)?

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

Can someone explain me the time complexity of problem D ...I came up with the similar approach but was not able to find the time complexity !!!TIA

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

    In each iteration, we are iterating over the array and splitting the array into two subarrays so if the size of the left subarray in the ith iteration is $$$b_i$$$ the recurrence relation in the depth of $$$i$$$ will be $$$T(n) = T(b_i)+T(n-b_i) +cn$$$. Now if you draw the recursion tree, you'll see that the sum of all $$$T(n)$$$ on the same depth is $$$O(n)$$$. The depth of the tree is $$$log(max(a_i))$$$ which is less than 31 and the running time is $$$O(nlog(max(a_i)))$$$.

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

I dont understand solution 1285B what editorial coder is doing is checking the sum if less than zero or not at any point of time...but how abt case 7 4 3 -1 answer should be No.. Right??

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

    Yes the answer should be no, as adel could pick 7+4+3=14>13 That's why the author calculated the cummulative sum in reverse order as well

    A simple mathematical proof could be as follows:

    consider:

    1. sum => sum of the whole array
    2. prefix[i] => sum of the array from index 0 to i
    3. suffix[j] => sum of the array from index n-1 to n-1-j
    4. sum[i:j] => sum of the array from index i to index j

    then

    • sum[i:j] = sum — (prefix[i-1]+suffix[n-j-2]) if i>0 and j<n-1

    or

    • sum[i:j] = sum — prefix[i-1] if j==n-1

    or

    • sum[i:j] = sum — suffix[n-j-2] if i==0

    then from these equations, u can see that if any cummulative prefix sum or cummulative suffix sum is less than or equal zero then

    sum[i:j]>=sum and the answer is NO

    otherwise

    sum[i:j]<sum and the answer is YES

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

      Wow Man really thankyou....There isn't any good work than helping a beginner. Thankyou so much. I got the logic there.

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

define finish(x) return cout << x << endl, 0

what does this line do?

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

    It creates the alias for printing a single value $$$x$$$ to stdout and exiting with exit-code 0. For ex, finish("test") will print "test" and terminate program. It's not used in solutions above.

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

Can someone explain me F? I didn't quite get it

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

In problem B, why my solution is giving WA? My Submission:https://codeforces.com/contest/1285/submission/68610213 I simply made a segment tree and excluding the node which contains the whole interval [1,n],I checked for all other node if they have sum>=sum of all elements..

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

    {3 -1 3 -1} breaks your solution, because you check all (not all, some of them) segments with length equal to power of two, but answer is [3 -1 3]

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

      Ok ..now I get it...silly of me not to think of the cases..once again thanks a lot!!!

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

can someone tell what will be the output for problem B for case 9 9 9 -1 9 9 9 and why because im not able to connect with the editorial and the problem

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

    Answer would be "YES" because no matter what sub-array is chosen, there will always be a positive sum left out from the left or right part of the array (elements which are not part of the sub-array). Thus total sum will always be greater than the sub-array sum. In general, if there exists a prefix [1, i] or a suffix[j, n] whose sum is <= 0, then that suffix or prefix can be dropped and the remaining array will have sum >= total sum.

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

what will happen in 2nd question if the first and last elements of array is zero

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

    Answer comes out to be "NO" because the other guy can just select the interval [2,n-1] and get sum=sum of all elements.

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

    another similar approach use maximum sum subarray concept on a[1:len(a)-1] and a[:len(a)] and take the max of the two and max(a[0],a[len(a)-1])

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

just a general question guys. do you think that the level of this round was lower than other div2 rounds? just wanted to know so as to analyze my performance. by the way thanks to the authors and editorial writers for the round

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

This is an alternate approach for E:

Let us store the segments sorted (first by start, then by end) in seg[1...n]

Define p(i) : Number of segments in union of segments 1, ..., i

Define me(i): max{ seg[1].end, ..., seg[i].end }

Obtaining both of these is not a difficult task and can be performed in O(n)

Now, we process the segments in order: n down to 2 while maintaining a set called V whose definition is: When we start processing segment i, V contains the union of segments i+1...n in sorted order (V contains segments which are union of seg[i+1]...seg[n]). When we start processing segment n, V is empty. It must be clear that at any point V contains segments which are pairwise disjoint.

To calculate the number of segments in union if segment i is removed, find the number of segments in V whose start is greater than me(i-1). This can be achieved by binary search. Let this number be x. Update answer as max(answer, p(i-1) + x). The reason for this is: From segments 1...i-1 the max end point is me(i-1). This covers all segments from V which have start <= me(i-1). The rest of the segments in V are x in number.

To make it clear, we first process segment n (and update V to include segment n) then process segment n-1 (again update V to include segment n-1) and so on. We do not process segment 1. For segment 1, the answer is simply the size of V after processing segments 2...n.

Updating V: After processing segment i, we need to update V. Let (l, r) = seg[i] and segments in V be (l_1, r_1), ..., (l_k, r_k). It must be clear that the segments in V are pairwise disjoint. Also, l <= l_1 <= l_2 ... <= l_k. To add (l, r) to V, keep removing segments from beginning whose l_i <= r (and while doing so, update r = max(r, r_i). Finally you will have (l, r) such that it is disjoint from each segment in V. Add this (l, r) to beginning of V.

I have omitted some minor details.

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

    looks like you haven't tested this algorithm yourself, because i have implemented the exact same logic but this solution gets TLE, i just can't make out.

    Can someone please help find whats wrong here : My Submission

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

      Have you implemented it correctly? My implementation runs in 124ms

      Please, don't make assumptions 68618583

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

        i figured out the error in my code, fixed it and got it AC, thanks for the nicest and simple solution compared to the editorial

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

        Could you please explain why int x = (int) (upper_bound(v.begin(),v.end(),pair<int,int> (me[i-1],INF)) - v.begin() ); is wrong for finding out x? @xvenom99

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

    I really like this natural solution. Thanks a lot.

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

Whoops, sorry, guys, I reread my editorial for E and it seems that I was too tired to write anything :) There are some nice comments detailing it, but I updated mine anyway. Hopefully, now it's easier to get what was going in my head when I wrote the solution. The part with sweepline still sounds pretty complicated but I guess I can't explain it better without doing an entire lecture on what sweepline actually is. The code should be pretty clear, refer to it maybe.

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

    can you explain the meaning of "adding updates" to me please?

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

In problem D, I'm having trouble understanding, why we split the integers into groups according to the MSB. I understand, that if there any 2 bits different, the answer will have bit 1 at that place but what's the thought process behind splitting them into groups for the remaining bits?

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

A solution for 1285D - Dr. Evil Underscores with trie with an idea like the editorial but more understandable 68656872

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

For E (Delete a Segment), I try the following:

  • attempt to find a line segment 'A' that ends at a position covered by only one line segment 'B'.
    • If 'B' touches another line segment 'C' at some point after it stopped touching 'A', then 'B' is the target segment to be removed.
    • This also increases number of continuous segments by 1
  • If no such B exists
    • just find a segment that is part of a union containing more than one segments and remove it and the number of continuous segments remain same as initial
    • else removing any segment decreases one of the disjoint segments and so final number of continuous segments = initial — 1

Can someone tell me if something is wrong with this approach? I seem to be failing at a test case: 68633455

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

can someone explain this statement from problem F

"That because this number together with a number smaller than x can never give a better product than that of a greater or equal number together with x"

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

    We consider numbers from largest to smallest, so after a number x we will consider numbers < x. Also we keep on adding numbers to the stack in the process. Since we add numbers to the stack in decreasing order, the number of the top will be the smallest, and the number after that will be second smallest and so on.

    So, for a particular x, after we pop the stack we will get a larger number on the top, which will get us a better answer for that x. Also we don't need the popped number, say y, anymore; since y * (some_number_smaller_than_x_which_will_get_considered_in_next_steps) will always be less than x * (some_larger_number_than_y_which_appeared_after_popping_out_y).

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

I failed to implement the sweep line solution on problem E, so instead of that, I just wrote a simple prefix sum and got accepted, lol.

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

    Could you please explain how you did it? I am unable to understand the editorial.

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

For problem D whats wrong in this dp solution:

Code

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

For problem F: if anybody else is confused with Mobius function in the editorial (like I was), it's not necessary. Just use inclusion-exclusion by itself, see my submission. Imho, editorial would be much easier if Mobius function was not mentioned at all.

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

Can someone please explain the problem D. I wasn't able to understand it from editorial.

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

For F, I used to be a little confused about the formula about the number of elements in the stack coprime to $$$x$$$, and I wrote a short expain for this part. I hope it can help someone.

Define $$$S$$$ as the number of elements in stack.

Write $$$d = p_1p_2...p_k$$$ if we can, where $$$p_i$$$ are distinct primes.

Consider $$$cnt_d$$$ as the set of multiples of $$$d$$$ ($$$|cnt_d|$$$ is equal to $$$cnt_d$$$ in tutorial), $$$|cnt_d| = |cnt_{p_1}\cap cnt_{p_2}\cap ...\cap cnt_{p_k}|$$$, where $$$p_i$$$ are distinct primes.

Hence, $$$S-f(x) = \sum_{k>=1, p_i|n} (-1)^{k-1}|cnt_{p_1}\cap cnt_{p_2}\cap ...\cap cnt_{p_k}|$$$, Consider it by using inclusion-exclusion over all factors of x.

By the definition of Mobius function, $$$\mu(d) = (-1)^k \Rightarrow$$$, $$$S-f(x) = \sum_{d>1, d|n} -\mu(d) |cnt_d| \Rightarrow f(x) = S+\sum_{d>1, d|n} \mu(d) |cnt_d| = \sum_{d|n} \mu(d) |cnt_d|$$$, ($$$\mu(d) = 0$$$ for all $$$d$$$ can not write as $$$d = p_1p_2...p_k$$$).

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

Can someone please explain me problem C 1285C - Fadi and LCM..?? What I understood from the problem statement is that the answer is that minimum no's pair which is max of its respective pair. if x = 24...the pairs whose lcm is 24 are :- 1. (1, 24).....max(a, b) = 24 2. (3, 8)......max(a, b) = 8 3. (4, 6)......max(a, b) = 6

now the minimum of max(a, b)'s is 6 so the answer should be (4, 6). Is it like this???

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

In Problem C, for n = 4 why is a = 2 and b = 2 is incorrect?

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

Osama_Alkhodairy Are there a db solution for E? I mean I solved it using recursion with Memoization after sorting the segments by their startpoints then their endpoints, the state is (idx: the current index,taken: did I delete a segment yet or not,max: the maximum endpoint so far) Isn't this qualifies the problem for dp tag? I added it but when I checked the tags of the problem a minute ago someone deleted it And I just wanna make sure that my thinking is right before adding the tag again.. so please back me up here or point out why this is not a dp/Memoization solution.

the complexity of the above algorithms is O(n*log(n)) for sorting the segements then O(n*2*2) for the recursion with Memoization, I know that max is between -1e9 and 1e9 but because where are going to delete one segment only so we don't expect more than two different values in the state. note that there is an overhead depending whether we are going to store max in a map or in unordered_map like I did.

my solution

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

Can anyone explain why choosing coprime pairs in C gives the optimal answer? I mean can anyone prove it mathematically or logically??? Osama_Alkhodairy

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

    Since the problem requires you to minimize max(a, b), so if a and b are not coprime then there is a smaller answer when you divide both a and b by their GCD

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

Problem D tutorial is great. But it haven't understood one thing that why we are taking min(ansOn, ansOff)? If ansOn is 5(101) and ansOff is 8(1000) then why are we taking 5?

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

wish i can make a so beautiful code like yours

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

In the problem 1285C - Fadi and LCM solution is provided. But in prime-factor related solution can you explain if((i >> j) & 1) a *= f[j]; else b *= f[j]; ?? Thank you.

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

    Enumerate these 11 prime numbers to determine whether there is a prime number in this state. If there is one, assign it to A. otherwise, give it to B. in the solution, if GCD is not 1, the common prime factor can be ignored without affecting LCM, so as to minimize max (a, b)

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

I found this AC submission of problem F from a friend of mine which was submitted from vjudge. The code looked very simple and we were puzzled by how it gave correct output. But we stumbled upon an input where it gave a wrong output.

Input:

5

53508 53508 53508 1248 1078

The output should be 672672, but this code prints 588588

I guess the test cases were weak to pass such a submission :/

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

can someone explain to me question D ? i cant understand the editorial

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

For 1285C — Fadi and LCM, why are we only considering co-prime numbers?

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

In Div2 B, what's wrong with using Kadane's algorithm to get the maximum subarray sum?

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

    bez this algorithm also take sum of all elements to find max subarray sum ,which we dont want

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

    I modified the existing dp approach to find the maximum subarray sum. Here's my submission.

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

    It may be a bit late but you can use kadane's algorithm with slight modification in code to solve Div2B first create an array with 0th to the n-2th element of the original array in it then use kadane to find the sum of maximum sum subarray of this newly created array let this be ans1. Then create a second array with 1st to n-1th element of original the array in it and again use kadane to find the sum of maximum sum subarray in it let this be ans2 then ans = max(ans1, ans2) is Adel's tastiness compare it with the total sum of the original array and you are done. Note by creating two different arrays we ignore the possible case in which both first and last element (total original array) was picked kadane's algorithm.

    Code — Submission

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

E can be solved with biconnected components as well.

The segments can be viewed as nodes in a graph. Split the segments in events. When you meet a starting event,connect the current node with the last node in the set and add the current node to the set. When you meet a ending segment connect the current node with the first node in the set and the current node with the last one in the set.

The key of the set should be represented by the time when you added the node and the node itself.

After you create the graph, do biconnected components and find the node which is in the most components. The answer should be the number of connected components — frequency of the node — 1.

There are some edge cases related to duplicates or that the frequency of the node is 1.

https://codeforces.com/contest/1285/submission/72275496

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

How we compute the value of X in question D if ask in question?

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

My submission using divide and conquer in Python I have written a python solution to this problem and compiled using PyPy. For test 6, I instantly get TLE, without any output. Can anyone find the mistake I have made in this solution?

I have replicated the c++ code shared by him in python (see 19:00 mark) Youtube video

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

Amazing how "& could turn a TLE to an AC!

My solutions for Problem D...

TLE Code

AC of the above TLE Code with just "&" (Pass by Reference) [826ms]

Another AC using Vector [405ms]

Same code, using Vector runs in 405ms , where as using set runs in 826 ms. Fascinating!

Vector vs List

Gotta say Problem D had pretty Tight Time Constraints! Loved it!

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

Problem E — "x is also in lfnf[j] because" — shouldn't this be lfnw[j] ?