Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

chokudai's blog

By chokudai, history, 12 days ago, In English,

We will hold AtCoder Beginner Contest 172.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

 
 
 
 
  • Vote: I like it
  • +93
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Is there any way to view current solve-count of problems, without having to reload standings? Reloading standings take too much time with my internet connection.

It would be nice to be able to filter the ranking page by "show fav only", just like contest standing.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    If by reloading standings you mean using the Refresh/Auto Refresh function (in the customize option in the standing page), then I think there is no other way. (Unlike CF, the problem list page of AtCoder does not show the current solve count.)

    I hope the Auto Refresh solves your problem (as it likely updates while you are solving other problems), but it still somehow needs to download the whole standing.

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

The most interesting and hard ABC I see.

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

They made problems hard this time seeing last time many solved D and E.

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

    D wasn't hard at all, it was just OEIS.

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

      What is OEIS? I wasn't able to solve it.

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

        OEIS is a website which has information about all sequences, This one was 1, 5, 11, 23

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

        On-Line Encyclopedia of Integer Sequences Google this or simply OEIS. https://atcoder.jp/contests/abc172/submissions/14775013 D in O(nlogn)

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

          it seems that you've successfully created an array div[n+1] , when n can be 1e7 .

          i am getting segmentation fault(core dumped) when i try to create an array of 1e7+1 integers in main() . i don't understand why! can you explain please ?

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

            There is something else wrong, array of size 1e7 is no problem.

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

              Man, I used Sieve of Eratosthenes to calculate no of divisors of each number from 1 to n. Here's my AC Code

              But I submitted it after the contest because when I run it on my laptop during the contest it didn't gave output to 3rd test case which was 10000000 because i thought it will give me TLE. Any possible reason for this?

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

                You would need to provide a link to the code and an understandable question.

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

                  Please read my edited comment

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

                  Sorry, that link does not show the code.

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

                  I edited the link, don't know what has happened with me today. Sorry man.

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

                  Are you sure that this works: ll arr[n+1]={};

                  Usually there is an 0 between the braces. For vector it works because it calls the default constructor, which initializes all to zero. But on array?

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

                  Yes, empty braces initializes the array with 0 values. I've done this many times. You can try this too, just to be sure.

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

                A local array (AKA an array created in a function scope) depends on the size of the stack. Default stack size is not enough to create such a huge size array.

                You have 3 options:

                1. Create a global array of max size and use it.
                2. Pass compiler flag to increase stack size.
                3. (I recommend this) Use vectors.
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Thanks for the suggestions. Also how to increase the stack size of function mentioned in 2nd option? Though I'll use global array now onwards. Just curious about 2nd option.

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

                  Assuming you are on Windows, passing -Wl,--stack=268435456 to the compiler will give same stack size as Codeforces gives.

                  On Linux, you can use ulimit.

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

              i got AC with this code, but it gave segmentation fault in my device. As far as I can remember i've done creating similar sized array before in my device. these type of unexpected behaviors are really dissatisfying :( hope i will get an explanation .

              thank you very much for your reply :)

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

                I cannot see anything wrong with that code, and its proofed by AC.

                So maybe/likely there is something wrong on your device, some wired compiler options or the like?

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

                  What's a wired compiler option? I've a dell laptop i3(5th gen) 64-bit. Don't know apart from this. But yes the problem is with the machine may be. Some people on this thread had same problem like me. Can't do anything now. (-_-)

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

                  If you run the code on your laptop you first compile it to a program. For this you use a compiler, and you call this compiler somehow. All compilers suppert uncountable optional parameters to do certein things.

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

                  Perhaps it might be. :( thank you for you kind replies.

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

                  Thanks for the help. I'll keep this in mind from next time :)

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

                  Its probably due to compiler. So whenever you want to test for large size arrays, use their system in Custom Invocation(for codeforces) or Custom Test (atcoder).

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

                Probably its due to compiler. Even I can't create arrays with large size like 1e7 on codeblocks. So, I usually test on their system if I use a large array.

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

                  I also got same problem to solve it I used vector. ll arr[1e7] = {0}; this is where I got the error. I use g++ as my compiler. Could there be a possible explanation to this why it did not work

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

                  Share your code.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  #include <bits/stdc++.h>
                  
                  using namespace std;
                  using ll = long long;
                  
                  int main()
                  {
                      ll n;
                      cin >> n;
                      ll arr[n] = {0};
                      ll ans = 0;
                      for (ll i = 1; i <= n; i++)
                      {
                          ll j = 1;
                          ll a = i * j;
                          while (a <= n)
                          {
                              arr[a - 1]++;
                              j++;
                              a = i * j;
                          }
                      }
                      for (ll i = 0; i < n; i++)
                      {
                          ans += (arr[i] * (i + 1));
                      }
                      cout << ans << endl;
                  }
                  
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Your code gives AC on their system. But due to large array size, as n can be 1e7, fails on some compilers.

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

                  So I found that local array declaration are done on stack. So this is nothing but stackoverflow so to solve it we can use vector or declare the array with MAX_N before the main function. Thanks for your help.

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

      Or you could just use sieve of erasthothenes to keep count

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

        Hey, I used sieve of eratosthenes but didn't get AC? How did you get it?

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

          witcher98

          Here is Code which uses Sieve

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

            I did same, But in my laptop the code was not printing out anything for 10000000 test case which I thought it must be a TLE. ;(

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

Really liked the Problem C.

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

    I am about to go into depression because of it. If there's something wrong in my logic at least provide better test cases.

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

    C was awesome

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

      Man I tried it so many times.

      Don't know where it went wrong.

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

        same but i got it right at last 1 minute i was taking lower_bound instead of upper_bound

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

          I used int instead of long long in C++! :-(

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

    indeed!!

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

      Try to solve it using prefix sum and binary search

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

      Test cases are perfect. But your solution doesn't consider all the books that can give the better answer.

      For example, Consider this test case-
      6 4 25
      5 15 1 1 1 1
      4 15 8 8

      Your answer- 3
      Correct answer- 6.(As we can read all the books in first stack within given k)

      I also couldn't solve it. It require a DP solution or some other solution explained by other coders. which I'm myself trying to understand :)

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

        Can the books be sorted also ? Or is the order fixed?

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

          No, they cannot be sorted. It says in the statement that you can only read the books from the top (The first element; this works more like a queue than a stack).

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

        Not quite DP.

        Calculate the prefix sums for the first array.

        Then try to 'read books' from the second stack. For each number of books read from the second stack, use binary search to calculate how many books you can read from the first stack.

        The answer is the maximum across the sum of books readable from both stacks.

        Submission

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

          I just don't know how to solve problems with prefix array, it never strikes me. 2-3 days ago education round D problem was on prefix sum array and today this one. I'll have to solve problem on this, thanks for the solution by the way. :)

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

How to solve E?

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

I think F is quite similar to 1325D - Ehab the Xorcist. Knowing idea of this problem could be a massive help.

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

    I didn’t find having solved that problem especially helpful. I would argue that the main challenge of F came from dealing with the condition of maximizing the first value without taking it above A[1].

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

      For me the useful idea is, $$$a+b=(a\oplus b)+2$$$(a & b)$$$ $$$. I didn't find this during that contest and thought it's quite tricky. The idea of digit dp is quite simple in my opinion.

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

        lol it doesn't require digit dp it was just x = a^b which is xoring boxes 2..n , y = a+b , a is A[0] , b is A[1] , then you just have to find the a&b which is w = (a+b-a^b)/2 , then the answer at first is w then you have to iterate from left to right on x and if you can add this bit to the answer without exceeding a then just add it. this is the solution briefly but you have to add the -1 cases inside

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

          Yeah, I messed things up a bit. Thanks for telling. :)

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

    I could infer we have to make xor of first two numbers equal to xor of the rest of the array. How to proceed further?

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

    Make prefix sum of array a and b try taking upto ith element in a then find remaining k if ith books in A are being read , with this remaining k binary search in prefix sum of array B to find maximum possible number of books you can read, do the same by taking ith index of array B also.

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

    Solved with partial sum and binary search
    My code
    hope it helps

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

My solutions to all the problems are outlined at this link.

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

can anyone tell the logic behind how to solve C?my all sample test cases were coming out right but still it was showing WA for many

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

Can someone plz explain the solution of problem C.....??plzz

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

    Problem C: It can be done using binary search. We will try to select (0, 1, 2, ... , n) elements from a[] and then the differnce that remains = k — prefix_sum[i]. Now, we will binary search the index in B[] in which prefix_sum1[j] is less than difference obtained above. The time complexity of this solution is O(n logm). My solution : https://atcoder.jp/contests/abc172/submissions/14766605

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

How to solve E and F?

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

    For E: Use the inclusion-exclusion principle. Solution

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

    for E: I solved it using inclusion-exclusion principle Submission

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

    F: From the nim-conclusion, the problem is equivalent to "given a, b, x, find k such that (a-k) xor (b+k) = x".

    Given an interval [l, r] where l is an multiple of 2^20 and r is less than l + 2^20, we can check in O(1) if there can possibly be an answer k in said interval. Once we find the interval with smallest l, we directly enumerate all values to check if there actually exists one.

    How do we check in O(1)? Notice that (a-l)>>21 and (a-r)>>21 must have a difference of at most 1, and likewise for (b+l)>>21 and (b+r)>>21. If there exists a pair (a, b), where a is one of [(a-l)>>21, (a-r)>>21] and b is one of [(b+l)>>21, (b+r)>>21], such that a^b=x>>21, then one exists.

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

      your algorithm is interesting. however, i can't understand the last part:

      if pair (aa,bb) exists and satisfies:

      1. aa belongs to [(a-l)>>21,(a-r)>>21]
      2. bb belongs to [(b+l)>>21,(b+r)>>21]
      3. aa^bb=x>>21

      then there is an answer.

      could you please explain it more in detail?

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

        Hey! I'll try my best to explain my logic here:

        Notice that for any i between l and r (l <= i <= r), then (a-i)>>21 must be either (a-l)>>21 or (a-r)>>21. Likewise, (b+i)>>21 must be either (b+l)>>21 or (b+r)>>21. Since in (a-i) xor (b+i) the first bits of (a-i) do not affect the other bits, we can regard them separately. Just taking the xor of the (almost) constant first bits, we can check if their could possibly exist an i in interval [l, r].

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

          now I can prove some of your claims to help me understand:

          (a-l)>>21 and (a-r)>>21 must have a difference of at most 1
          

          and

          any i between l and r (l <= i <= r), then (a-i)>>21 must be either (a-l)>>21 or (a-r)>>21
          

          proof:

          suppose l=x*2^k,r=(x+1)*2^k (which in your case k==20).

          (a-l)>>(k+1)
          =floor((a-l)/2^(k+1))
          =(a-l-d1)/2^(k+1) (where 0<=d1<2^(k+1))
          =(a-x*2^k-d1)/2^(k+1)
          =a/2^(k+1)-x/2-d1/x^(k+1)
          

          likewise,

          (a-r)>>(k+1)
          =floor((a-r)/2^(k+1))
          =(a-r-d2)/2^(k+1) (where 0<=d2<2^(k+1))
          =(a-(x+1)*2^k-d2)/2^(k+1)
          =a/2^(k+1)-(x+1)/2-d2/x^(k+1)
          

          hence,

          (a-l)>>(k+1)-(a-r)>>(k+1)
          =1/2+(d2-d1)/2^(k+1)
          

          because 0<=d1,d2<2^(k+1), -2^(k+1)<d2-d1<2^(k+1). thus

          (a-l)>>(k+1)-(a-r)>>(k+1)
          =1/2+(d2-d1)/2^(k+1)
          
          belongs to (1/2-1,1/2+1)=(-0.5,1.5)
          

          since (a-l)>>(k+1) and (a-r)>>(k+1) are both integer, thus (a-l)>>(k+1)-(a-r)>>(k+1) belongs to [0,1].

          • »
            »
            »
            »
            »
            »
            3 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yep, as far as I can tell that's correct.

            Once you find an interval [l, r] that can potentially contain an answer, you just iterate through the entire interval to check.

        • »
          »
          »
          »
          »
          3 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          so your main strategy is:

          1. search for higher bits of a' and b'
          2. fix higher bits of a' and b'
          3. search for lower bits of a' and b'

          am i right?

          • »
            »
            »
            »
            »
            »
            3 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, that is correct. This will give a total runtime of O(M sqrt(max(a))) where M is the number of higher bit matches. Although I don't know how to prove that M=O(1), it works very fast :) I'd be grateful if someone can hack my solution or prove that M is constant.

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

How to solve F?

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

https://atcoder.jp/contests/abc172/submissions/14745041

Can anyone help me why this is wrong?

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

E had a solution quite similar to Placing Rooks

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

what is wrong in my solution of problem C https://atcoder.jp/contests/abc172/submissions/14763812 getting WA on 10 test cases.

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

    Here greedy solution doesn't work as you might get a better solution picking the higher one, Consider the following case, N = 3, M = 3, K = 5, A = [1,2,3], B = [3,1,1], here you can pick the whole B array and answer will be 3

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

      We can sort A and B and then apply greedy? But still, I am getting wrong.

      Update : Sorry I misunderstood it

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

      Ohh yes, now I get it, thank you so much

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

problem E can be solved by IEP. The closed form answer is:

$$$\left(M!+\sum_{k=1}^{N}(-1)^k\binom{N}{k}(M-k)!\right)\frac{M!}{(M-N)!^2} $$$
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    What is IEP?

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

      Inclusion–exclusion principle

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

        But how you got to that?

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is it an special algorithm ? or a technique which we use in math?

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

          Yep, basic combinatorics. But it can be applied to hard problems.

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

does E has something to do with derangements?

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

I am new in Atcoder. I did't see any English editorial for the problems. Is there any English tutorial available?

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

    For International Readers: English editorial will be published in a few days.

    It's written in editorial

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

    will take some time for the translation.

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

    They generally come out a day later.

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

for problem E, assuming fixed A is [1,2,3...,n], ans = C(m,n) * n! * G(n, m)

which G(n, m) means given 1 ~ n for A, using 1 ~ m for B that satisfy the condition

then G(n, m) = (m — n) * G(n — 1, m — 1) + (n — 1) * ( G(n-1, m-1), G(n-2, m-2) )

G(0, m) = 1, G(1, m) = m — 1

when n == m, G(n, n) = D(n), which is derangements

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

    Can you please explain how you got that recursive relation

    or any link related to that derivation would be nice

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

      Assuming A is [1,2,3,...,n]

      When looking at what G(n, m) should be, let's imagine what the last number, x, in B should be.

      There are (m - n) ways to select x greater than n, leading us to a position where our new size is n - 1 where we still have (m - n) available numbers greater than the size (we lose the number we selected, but we gain n as a choice) This gives us the (m - n) * G(n - 1, m - 1) part of the formula

      There are (n - 1) ways to select x < n. From here, we have 2 options:

      1) select the xth number in B to n.

      This leave us with a new size to fill of n - 2, and there were still (m - n) numbers available that are not in A. This gives us the (n - 1) * G(n - 2, m - 2) part of the formula

      2) select the xth number in B to be something other than n

      Here we can imagine that x is our new 'last number', but instead of being unable to select x for it, it cannot select n for itself. Every other number works the same, so this is the same as G(n - 1,m - 1), giving us the (n - 1) * g(n - 1, m - 1) part of the formula

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

    Is there a way to solve the problem without blindly using any memorized formulas? Some form of dp? What would be a useful definition of dp[i]?

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

      Yes? It's just Principle of Inclusion-Exclusion.

      Let $$$S_k$$$ be number of permutations with $$$>= k$$$ positions fixed (as given permutation).

      $$$S_k =$$$ (no of ways to choose set of $$$k$$$ positions) * (no of ways to permute $$$(n - k)$$$ positions from $$$(m - k)$$$ elements) = $$${n \choose k} * {m - k \choose n - k} * (n - k)$$$.

      Then, Derangements $$$= \Sigma_{i = 0}^{n} (-1) ^ i * S_i$$$

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

      It looks to me that G(n,m) is easy to turn into a dp, since you always decrease m by the same amount you decrease n, so you can disregard m and just keep track of n in each state.

      Submission

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

    During the contest, I was able to derive this formula

    G(n, m) = (m — n) * G(n — 1, m — 1) + (n — 1) * (n - m + 1) * G(n - 2, m - 1)

    I am sure this recurrence is correct but this form didn't let the computation to be in O(N)

    Thanks for sharing the formula @mickeyandkaka

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

I have a solution to the D problem with time complexity O(n).

$$$F(n) = \sum_{k=1}^n (\dfrac{k}{2} \times \left\lfloor{\dfrac{n}{k}}\right\rfloor\times \left\lfloor{1+\dfrac{n}{k}}\right\rfloor)$$$

Code (C++):

Read(&n);
for (int i = 1; i <= n; ++i) { ans += (lf(i) / 2) * (n / i) * (1 + n / i); }
printf("%.0Lf\n", ans);
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Why does it work?

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

      because OEIS

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

      number 2 appears as the divisor in (n / 2) numbers from total n numbers

      In 2,4,6, ... number 2 appears as a divisor exactly one time,

      So our answer will increase by

      2 * 1 + 4 * 1+ 6 * 1 + ...

      2 *( 1 + 2 + 3 + .. + n / 2)

      Do the same for 1 to n

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

C was way harder than D for me , i dont know if its me or the problem.

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

What is wrong with [this] solution for C?(https://atcoder.jp/contests/abc172/submissions/14772857)

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

I used 2 pointers instead of binary search in problem C. That was easier to implement in my opinion.

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

Really liked problem E! Good contest!

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

is there any English editorial in atcoder? i am new at Atcoder

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

    For International Readers: English editorial will be published in a few days.

    but you can use google doc translater (its not accurate but you can understand the logic)

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

O(sqrt(n)) solution for D:

ll fun(ll n){
   ll x=(n*(n+1)*(2*n+1))/6;
   return x;	
}
void solve(){
    //input
   double n;
   cin>>n;
   ll i;
   ll sum=0,sum1=0;
   for(i=1;i<=sqrt(n);i++){
	   sum+=i*(i+floor(n/i))*(floor(n/i)+1-i)/2;
   }
   ll ans=2*sum-fun(sqrt(n));
   cout<<ans<<endl;
}
»
11 days ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

Here is my solution to C.

#include <bits/stdc++.h>
using namespace std;

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long n, m, k;
	cin >> n >> m >> k;
	vector <long long> a(n), b(m);
	for (auto &i : a) cin >> i;
	for (auto &i : b) cin >> i;
	long long i=0LL, j=0LL, count = 0LL;
	while (i<n && j<m) {
		if(a[i] <= b[j]) {
			k -= a[i++];
		}
		else {
			k -= b[j++];
		}
		if (k >= 0LL)
			++count;
		else break;
	}
	bool state = true;
	while (i<n) {
		k -= a[i++];
		if (k >= 0LL)
			++count;
		else {
			state = false;
			break;
		}
	}
	if (state) {
		while (j < m) {
			k -= b[j++];
			if (k >= 0LL)
				++count;
			else break;
		}
	}
	cout << count << '\n';
}

Can anyone tell me why the above code gets WA in 10 test cases. Isn't the problem solvable by 2 pointer kinda technique?

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

    Try a case like :-

    1 2 120 101 110 10

    The correct answer should be 2 by reading the books from array B which take 110 and 10 minutes(collectively a value less than or equal to 120), but your solution gives 1(by picking 101 from array A instead).

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

      Ahh, so that means greedy will not give the optimal solution right?! Any help on how to solve the problem? The English editorial is going to take some days to come :(

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

        Since it is clear from the statement that we have to pick books exactly in the order as how they appear, the first intution can be to construct prefix sum arrays for both arrays A and B(say, arrays, prefA and prefB). Why? Because, having two prefix arrays (one for A and other for B) means that, we can find out the time to read books upto the ith book(included), in O(1) for both the arrays A and B, separately. Now, the only part remaining is to search efficiently, the maximum number of books we can read in <= K mins. We can do a binary search since, prefix arrays are always sorted. One approach could be to fix the number of books we can take from array A (0,1,2...N) one by one and if for any of these values, the time taken i.e., prefA[i] is <= K, we do a binary search on prefB to see how many books can be picked from array B, and keep updating the answer, accordingly. Hope it helps :)

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

why greedy fails for C? at each step pick up the minimum of the two.

UPD — Got it.

Testcase

UP2 — Thank you for so many testcases :)

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

Can any one tell why C fails using two pointer approach and any test case for the same.

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

This is a nice explanation of how inclusion-exclusion principle can be used to find the number of derangements. It can be extended to solve E.

Edit: Look for the proof under the formulae section.

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

//why my code is giving wrong answer please help please give solid test cases

in question C: Tsundoku


#include <bits/stdc++.h> #include<algorithm> #include<cstring> #include<string> using namespace std; typedef long long int lli; #define mxint 1000000007 const int mod = int(1e9+7); long long int t[2000001]; /* int gcdExtended(int a, int b, int *x, int *y) { // Base Case if (a == 0) { *x = 0; *y = 1; return b; } int x1, y1; // To store results of recursive call int gcd = gcdExtended(b%a, a, &x1, &y1); // Update x and y using results of recursive // call *x = y1 - (b/a) * x1; *y = x1; return gcd; } */ int main() { long long int n ,k,m; cin>>n>>m>>k; long long int s1[n],s2[m]; for(long long int i=0;i<n;i++) { cin>>s1[i]; } for(long long int j=0;j<m;j++) { cin>>s2[j]; } long long int i=0,j=0,count=0; while(k>0) { if(i!=n&&j!=m){ if(s1[i]<=s2[j]) { k=k-s1[i]; if(k>=0) count++; i++; } else if(s1[i]>s2[j]) { k=k-s2[j]; if(k>=0) count++; j++; } } else if(i==n&&j==m) { break; } else if(i==n&&j!=m) { k=k-s2[j]; if(k>=0) count++; j++; } else if(j==m&&i!=n) { k=k-s1[i]; if(k>=0) count++; i++; } } cout<<count<<endl; }
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i wonder why this solution WA : https://ideone.com/VIzSXP

someone helps :((

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

    consider the sequence on desk1 as $$$(1,2,3,4,8)$$$ and on deks2 as $$$(10,1,1,1,1,1,1,1,1)$$$ for $$$k=18$$$. Your $$$ans$$$ is $$$5$$$ but it's 9.

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

Problem C: I am not able to understand why my code is wrong https://atcoder.jp/contests/abc172/submissions/14775455

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

Can anyone validate my approach for the question C. I have used a 3d vector(dp solution). I know it will definitely give TLE becasue of the high constraints, but for the smaller inputs is it a right approach https://atcoder.jp/contests/abc172/submissions/14783835

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

In c,the logic of not getting ac using greedy is almost like coin change dp problem(you may pick the largest coin but it doesn't ensure that the number of coin will be minimized).Here,we may pick the top book with the minimum value but it doesn't ensure that that we can read the maximum book.

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

    Can you give a test case where my approach might fail?

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

No English Editorial.

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

I am new to cpp, so not sure whats the problem. The code gives WA in one test case and RE in one. Rest all is accepted. Any help would be nice.

#include <bits/stdc++.h>

#define ll long long
using namespace std;

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    ll A[n]; ll B[n]; ll preA[n+1]; ll preB[m+1];
    preA[0] = 0; preB[0] = 0;
    for (ll i = 0; i < n; ++i) {
        cin >> A[i];
        preA[i+1] = preA[i] + A[i];
    }
    for (ll i = 0; i < m; ++i) {
        cin >> B[i];
        preB[i+1] = preB[i] + B[i];
    }
    ll max = 0;
    ll index = m;
    for (ll i = 0; i <= n; ++i) {
        ll totalLeft = k - preA[i];
        if (totalLeft < 0){
            break;
        }
        while (preB[index] > totalLeft){
            index--;
        }
        if (index + i > max) {
            max = index+i;
        }
    }
    cout << max;
}

»
11 days ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it
C using upper bound
»
11 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Can somebody explain the solution for problem E, I am not able to understand it.

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

https://atcoder.jp/contests/abc172/submissions/14775983 can anyone help in C I used sliding window and binary search but getting wrong answers on 4 tcs .UPD-I found the bug

»
11 days ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it
Easy solution of D just by loop for time limit 3 sec
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can go even simpler than that
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for giving us more simpler way.

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

        The removal of the array decreases the execution time dramatically. First solution gave me 847ms, while the second was only 82ms.

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

Hey can anyone help me out where I did wrong in problem C https://atcoder.jp/contests/abc172/submissions/14753662 Thanks in advance

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

    You implemented a greey solution which does not work well. Consider first stack of books all 2, ie 2 2 2 2 ... and the other one starting with 3, ie 3 1 1 1 1 1....

    So you will read all 2-books, but never a 1-book.

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

Does anybody know why my approach to prob D gives TLE? I ran the Sieve storing, for each number, its prime factors (instead of "crossing off" the number, I stored the prime it's a multiple of.) This should be NloglogN. Then, for each number, I compute the exponent of each of it's prime factors via prime factorization (I already know all of it's prime factors, so this should be NlogN, since we can divide the number at most logN times) in order to get the number of divisors.

Note that this approach works; I don't get any WA, only some TLEs.

Does anybody have any clue?

Thanks!

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

Can someone help? Why is this code giving WA?

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

    Try this testcase:

    3 4 8

    4 10 11

    5 1 1 1

    Your output:1

    Answer:4(Whole second array 5+1+1+1=8)

    Two pointer would not work. I hope you got the mistake.

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

can somebody please explain me problem E with statement and how princple of inclusion exclusio works here

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

    Here is my solution with some comments about what is going on (on a best effort basis).

    Solution
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Although C can be solved with prefix sum and binary search, is it solvable using DP?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it