chokudai's blog

By chokudai, history, 2 months ago, In English

We will hold AtCoder Beginner Contest 190.

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

We are looking forward to your participation!

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

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

I'll be discussing the problems right after the contest, at https://twitch.tv/AnandOza

Good luck everyone!

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

... and I will release the usual screencast with commentary on my YouTube channel at https://www.youtube.com/c/NikitaSkybytskyi so that you can catch it later if you miss the stream or just like the overcomplicated explanations :upside_down_face:

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

Starting soon!

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

This is my first contest. I have to say ABC is better than Div. 3.

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

It's better to swap E and F

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

How to solve E? I solved F but not E.

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

    dp[mask][pos] is the gem you visited and the last gem you use.

    We can first do bfs k time to calculate the Cij, the do the normal 2^k * k^2 bitmask dp.

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

    how to solve F? got TLE at 2nd TC

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

      You can use fenwick tree to calculate inversion for k=0, and then as the given sequence is a permutation all you have to do is find the contribution the ith element is making to the ans when the ith element is put in back of the array...Here is the link to my solution

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

    Build a graph with the edges, for each of the K gems, find the shortest path to other K gems(BFS). Now, you have basically have to chain the K gems in an order(a permutation) s.t. the sum of distances from one gem to the next is minimum (DP+bitmask).

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

    You can observe that if all the $$$c_i$$$ are not part of a component then answer is no , otherwise we can always form some ans . Now notice that k <= 17 so we can use dp over subsets . $$$dp[mask][j] = min(dp[mask][j] , dp[mask\oplus j][i] + dist[i][seq[j]]);$$$
    Now we are trying to form $$$mask$$$ that ends with $$$c_j$$$ and just before $$$c_j$$$ , we had visited $$$c_i$$$ and $$$dist[i][seq[j]]$$$ tells the minimum distance from $$$seq[i]$$$ to $$$seq[j]$$$

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

    It is about E:
    How to prove the solution of the first loop of $$$dp[mask][j]=min(dp[mask][j],dp[mask⊕j][i]+dist[i][seq[j]])$$$?
    I think if solve from shorter to longer it is simple.
    But i saw that all of solution is from [0 , 1<<k) or (0 , 1<<k).
    Update: I known that because if i have a subset j the i^(1<<j) is solved before cacluate i.

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

How to solve C? Greedy algorithm doesn't work.

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

I solved $$$D$$$ with the help of oeis. Can someone help me on how to approach such problem as I would never be able to find connection between number of odd divisor and what the problem asked?

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

    Can you please share the link of OEIS you referred to?

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

    How you solved D?

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

    Formula for sum of first k element of arithmetic series whose first value is $$$a$$$ and diffrence between two consecutive element is $$$d$$$

    $$$S_k = (k / 2) (2 * a + (k - 1) * d)$$$

    here $$$d$$$ = 1 and $$$s_k = n$$$

    $$$n = (k / 2) (2 * a + (k - 1))$$$

    $$$n = (k * a) + (k * (k - 1)) / 2$$$

    $$$n - k * (k - 1) / 2 = k * a$$$

    $$$(n - k * (k - 1) / 2) / k = a$$$

    now just check if $$$a$$$ is an integer;

    we will go over all possible value of $$$k$$$ for given $$$n$$$ and check if $$$a$$$ is an integer or not.

    submission link

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

      I think you mean $$$(n-k*(k-1)/2)/k=a$$$

      Thanks, I understood

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

      why did u do *2 in the ans?

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

        for each arithmetic series starting at $$$a$$$ and ending at $$$b$$$.

        $$$a, a + 1,.., b - 1, b$$$

        there is one another series like this

        $$$ -(a - 1), -(a - 2),...,(a - 2), (a - 1), a, a + 1,.., b - 1, b$$$

        so here you can see negative values will cancel out positive values and it will become same as original series.

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

      btw, why is the condition for the for loop (k * (k + 1)) / 2 <= n but not (k * (k — 1)) / 2 <= n ?

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

        for arithmetic series(not starting from negative values) of length $$$k$$$, minimum sum we can get is $$$k * (k + 1) / 2$$$. This series goes from $$$1$$$ to $$$k$$$.

        we have to make sure this sum doesn't exceed $$$n$$$

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

        You can also use :

        $$$ k*a = n - k(k - 1)/2 >= 1 $$$

        so that

        $$$ k(k - 1) <= 2(n-1) $$$
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      If we go one step further...

      n/k — (k-1)/2 = a

      Which means k should be divisor of n and in order to make LHS = RHS, (k-1)/2 should also be an integer => k is odd...

      hence final ans would be 2 * No of odd divisors of n

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

My thought process on D.

Suppose the AP contains $$$k$$$ terms, namely, $$$a, a + 1, \dots a + (k - 1)$$$. Summing up all these values and using the formula for the sum of first $$$i$$$ natural numbers, we can conclude that

$$$ a \cdot k + \frac{k \cdot (k - 1)}{2} = N $$$

Multiplying both sides by 2, so that we deal with integers instead of fractions, we get

$$$ k(2 \cdot a + (k - 1)) = 2N $$$

Naturally, $$$k$$$ which denotes the number of terms, should be divisible by $$$2N$$$. In other words, the possible value of $$$k$$$ is a divisor of the number $$$2N$$$. Finally,

$$$ 2 \cdot a = 2\frac{N}{k} + 1 - k $$$

This implies that the RHS should be divisible by 2. If we can satisfy both these conditions, we get our desired sequence.

We know that there are atmost $$$O(N^{1/3})$$$ divisors. Hence, we can bruteforce the 2 conditions over all divisors.

Code

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

How to solve D ? In problem D I used AP formula and then realized that if for positive value of $$$a$$$ , $$$(2a-1)^2 + 8n$$$ is perfect square , then we can increment the answer twice . But i didn't knew how to proceed further.

Can someone help in how to count all positive values $$$a$$$ such that $$$(2a-1)^2 + 8n$$$ is perfect square ?

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

    Number of odd divisors * 2

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

      I understood from above explanations that why it should be one of the divisors . Could you please elaborate why it will by always odd divisor and not even ?

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

        Assume N = x * y and x is odd. Now, you have x copies of y summing to N. You can modify it to y-i,..y-2, y-1, y, y+1, y+2,.., y+i and get an AP. Another Ap can be made if you consider negative integers. But the same is not true if x is even.

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

          Thanks . It makes sense why odd will work always . It's difficult to create even length AP around y (similar to what we did when length was odd) . But it doesn't proves that there won't exist any AP of even length summing to N ?

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

            even length (lets say it is l) is possible if 2N/l — (l+1) is even, which is possible only when l has all powers of 2 as in 2*N means 2N/l is odd (and indeed l is a divisor of 2N). Due to this only the answer comes as 2*(number of odd divisor possible)

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

              I understood that if x is even then then it should contain all powers of 2 but i didn't get why it cannot be one of the answer ?

              For N = 53*4 = 212 , take x = 8 , then 'a' turns out to be 23. Indeed 23+24+25+...+30 = 212 . Thus one of the even divisor of 212 that is 8 is working .amurto could you also please check this example.

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

                After doing some observation, I came to know this

                $$$a + (a + 1) + (a + 2) + .. d = n$$$
                And the problem can be reduced to find all possible values of $$$a$$$ and $$$d$$$.

                We can represent the desired series as $$$\frac {(a + d) * (d - a + 1)} 2 $$$

                If you observe the parity of $$$(a + d)$$$ and $$$(d - a + 1)$$$ it will always be different. So, that gives an idea the sum will be in the form of $$$\frac {odd * even} 2$$$.

                And the solution is suffice to find all possible forms of $$$odd divisor * even divisor$$$ when you prime factorize $$$2n$$$. And you have to multiply it by $$$2$$$ since $$$(even divisor * odd divisor)$$$ order matters.

                The quotient may be even when you divide $$$2n$$$ by one of its even divisor But, the quotient is always an even number when you divide $$$2n$$$ by its odd divisor. Thus, The answer is $$$2$$$ * (total number of odd divisors of $$$2n)$$$.

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

                8 satisfies well the condition I wrote above 2*212/8 — 9 is indeed even and then is a valid divisor of 2*212 for which answer is possible.

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

                For N=212, x=53, y=4, consider 53 copies of 4. Lets create an AP with terms y-x/2,..,y-1,y,y+1,..,y+x/2. It would look like

                -22,-21,-20,...,0,1,2,3,4,5,,...,23,24,25,26,27,28,29,30
                

                We cannot add more integers to the prefix to make another AP, but rather remove some integers from the prefix. Consider a suffix from the above AP where sum=N. It is the same AP you mentioned. 23,24,..,30. So for every odd divisor, two APs are possible, even length and odd length.

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

                I understood it should be only 2* count of odd divisor .

                From formula $$$2a=2N/K+1-K$$$ , RHS shouldn't be odd and thus suppose $$$2N = x*y$$$ , both $$$x$$$ and $$$y$$$ cannot be even or odd simultaneously and cannot be equal.

                Also for every $$$x$$$ corresponding $$$y$$$ will be unique and suppose $$$x<y$$$ then it's going to work for only $$$x$$$ and not for $$$y$$$ else RHS won't be positive. odd element in pair $$$(x,y)$$$ will also be factor of $$$N$$$ and thus answer will be 2* count of odd divisor .

                thanks amurto,rkguptagkp462,EnterYourName .

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

                  It could be even divisor if the quotient is an odd when you divide $$$2n$$$ by an even divisor.

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

    Here is how I solved this problem. Let's say $$$n$$$ = $$$\frac{a\cdot (a + 1)}{2}$$$ — $$$\frac{b\cdot(b + 1)}{2}$$$
    Now after solving the equation we get $$$2\cdot n = (a - b)\cdot(a + b + 1)$$$ after that we can see whenever integer solution exists for $$$a$$$ and $$$b$$$ we add $$$2$$$ to our answer because we can also go into negative side to get one more solution . Time complexity will be $$$O(sqrt(n))$$$

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

    u can do it by counting the number of ways of making sum of n by consecutive numbers gfg algo for it by this and then just add 1 that the case the number n itself and multiply by 2 because u can always make the same series by adding negative terms and u are done..

    my code

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

    You can brute force the value of number of terms in AP, which is at most 1e7 for sum=1e12 and check if you can find any suitable a(First Term) for all number of terms from 1 to 1e7. Then just double the ans.

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

Felt like torturing myself while doing E

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

i solved F using Policy Based Data Structure in C++ how to solve it without Policy Based Data Structure

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

    You can use fenwick tree to count number of inversions in the initial array let say $$$ans$$$ . After that you can notice that each front element will move to the back of the array and thus you can do $$$ans = ans - (a[i]-1) + (n-a[i])$$$.

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

      not able to observe ans = ans — (a[i] — 1) + (n-a[i]) ... please explain

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

        You can observe that each time you increase $$$k$$$ , front element of the array will move to the back of the array . Since there are $$$a[i]-1$$$ elements which were causing inversion because they are after $$$a[i]$$$ but they will be at front of $$$a[i]$$$ as soon as we move $$$a[i]$$$ to the back of array . Thus we need to subtract $$$a[i]-1$$$ .

        For example :

        array $$$3,2,1$$$ , Now suppose i move $$$3$$$ to back of the array , then array will be $$$2,1,3$$$ . We can see that $$$1$$$ and $$$2$$$ were causing inversion with $$$3$$$ but after we moved $$$3$$$ to back of the array they won't cause inversion any more .

        $$$n-a[i]$$$ part can be explained analogously .

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

    You can use merge sort to find th no. of inversion , The link could be found on Geeks for geeks

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

      link to article please

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

        Or You can see other submissions on EURON

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

    Link to your solution please

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

wait! So, B isn't dp?

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

    Just do as the problem says.

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

      How to solve it if you can use multiple spells? I thought about some knapsack.

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

        You just need to find out whether there is at least one strong spell or not.

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

          Yeah But I'm asking how to solve the variant of the problem.

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

            If you can choose any number of spells, you just have to check the sum of the powers' of strong spells. But if there is a limit on the maximum number of chosen spells, yeah, it would be a knapsack problem.

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

    Wait, it was GRAPH!!

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

why you set question statement confusing instead of making good question. In todays contest question B statement was very confusing. In 2nd last contest you did in question C.

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

My submission for F passes the sample test on my system but they are generating a different output on Atcoder's system. Anyone please help me finding out where it's all going wrong.

UPD: Got the error, there was a segmentation fault in my Fenwick Tree.

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

    Hey, running your code on my system gives this error:

    f.cpp:122:15: runtime error: index 300016 out of bounds for type 'int [300015]'

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

D much harder than E and F. Still do not get it.

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

    Even i couldn't get the idea for D. But OEIS helped.

    oeis sequence

    Did a brute force to find the answer for the first 20 natural numbers and then used oeis to get the general formula.

    The formula is : 2*cnt_of_odd_divisors_of_n

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

    Hint: l + (l + 1) + ... + r = (l + r) * (r - l + 1) / 2

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

      I've also tried this to find r for each l iterating from -n to n. But it was a brute force approach.

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

        Sometimes coming up with brute force helps in problems like these where the input is a single integer. Most of the times the general formula can be obtained from sites like Oeis.

        This is not the best approach to solve problems but certainly helps if you are not able to come up with any better solution.

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

          These kinda problems are those I'd spend a day to solve. I know OEIS but It's only fun if I solve the problem myself. And Yeah, I think ABC really helps improving the observation skill.

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

    https://en.wikipedia.org/wiki/Arithmetic_progression

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

      What is the meaning of "we can factorize ... as ... such that..." ?

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

        i mean divisors : 12 => (1, 12), (2, 6), (3, 4)

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

    We can look at problem D in this way:

    Sum of 'n' elements of an AP with first term being 'a' and common difference being 'd' = n*a + (n*(n-1))/2.

    we want it to be equal to 'S'. On rearranging terms we get

    a = (S-(n*(n-1))/2)/n

    We can fix that a>0 as we can always form an AP starting with negative -a+1. So for every possible a>0 we can have another AP whose 1st term is non-positive.

    for a to remain positive S-(n*(n-1))/2 should remain positive.

    So we need to iterate over all values of 'n'. S can go up to 1e12 and it's subtracted with n^2 so we need to travel around 10^6 only.

    Hope that helps. Feel free to ask if anything is not clear.

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

      I would be happy to get some explanation starting with the idea, not some formular.

      As far as I understood the formulars follow the idea that 2*N is diviseable by the length of the seq with sum N. Is that correct?

      How do we know that there is only one such sequence with than length? What is 'a' in your formulars, how/why can we "fix it"?

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

        Regarding idea, I started by writing down the formula itself because I remembered that there is square term in the formula and the time complexity also seemed to be O(sqrt(n)).

        There are a lot of formulas to calculate the sum of AP but I chose this because of the square term.

        'a' is the first term of AP.

        With common difference 'd' being fixed and equal to 1, sum of AP becomes sum of consecutive numbers starting from 'a'. So for a particular length and fixed sum, we can have only 1 'a', so it's unique. We cannot have sum of, let's say 3 consecutive numbers same unless they have the same first number.

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

        Maybe this helps to get the intuition.

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

    Let $$$n$$$ be the given number $$$a$$$ the first number in the sequence and $$$k$$$ size of the sequence: $$$n = \frac{k * (k-1)}{2} + a * k$$$. We want to get how much $$$a$$$ is equal, because it has to be the real number. With enough transforming, you get the following formula: $$$a = \frac{n}{k} - \frac{k-1}{2}$$$. We have two cases: 1) Both $$$\frac{n}{k} - \frac{k-1}{2}$$$ are real. For that case, the answer is the number of odd divisors of $$$n$$$. 2) Both $$$\frac{n}{k} - \frac{k-1}{2}$$$ are of the form $$$0.5$$$ $$$+$$$ some real number. As you can see, $$$k$$$ must be even so that $$$\frac{k-1}{2}$$$ be of that form. Now $$$\frac{n}{k}$$$ to be of that form, $$$gcd(n, k)$$$ must be equal to $$$\frac{k}{2}$$$. The answer for this case is also the number of odd divisors of $$$n$$$.

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

    Try out a few numbers and try to find the pattern. I didn't think in terms of formulae either, but was lucky enough to catch this from the examples.

    N = 12
    N = 5
    Observation
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I did a binary search approach on D. I tried to express the number as a sum of i consecutive numbers. You can check my submission for a better understanding

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

      Actually I am not sure for which value do you do the binary search. On the other hand, I was now able to implement a binary search.

      The formular for the sum of some seq, let $$$l$$$ be first, $$$r$$$ be last element of the seq: $$$(l+r)/2 * (r-l-1)$$$

      So we know that $$$2*N$$$ is divisable by the len of the seq. Finding all divisors of $$$2*N$$$ foreach: Binary search for the first element of that seq.

      Then, if the seq of that len, with that first element has sum N, then we found one and increment ans by 2.

      I had some difficulties to overcome overflow errors, in the end I used 128 bit type. However, it seems to work with 64 bit, too, but I still do not see how. Debug output shows me that calculating the sum in the binary search overflows the 64 bit type.

      submission

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

        Let l be the first term and total number of terms be i.. so it can be written as l,l+1,l+2,...,l+i-1 i.e (l*i)+((i-1)(i-1+1)/2) so it will never overflow because l <=1e12 and i<=2e5 in my submission. And l was the value on which i did binary search for every i terms

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

Can somebody please help as why my recursive solution is giving TLE in problem C? I don't understand.

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

    Interesting! Looks like you're iterating through $$$k!$$$ instead of $$$2^k$$$ combinations. remove the for loop.

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

      Yes, I iterated through k!, the unnecessary loop didn't strike me ;(, Thanks :)

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

        You can either use some bitmask trick.

        for(int i = 0; i < 1 << k; i++) {
                for(int j = 0; j < k; j++) {
                    if(i >> j & 1) //include 
                }
        }
        
»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it

My solutions, along with detailed explanations, can be found here :)

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

Words hiding behind each problem

A
B
C
D
E
F
»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Can we make problem F harder and E easier?

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

This is my code for question C.

I cant figure out why it failed for 12 cases.

I worte a recusive fintion for 2^k enumeration and check each condition.

Can Anyone help?

ll n,m;
ll k;
ll ans;
vector<ll>S;

void rec(ll i, vector<pll>&pep, vector<pll>&test)
{
	if(i==k)
	{
		ll x=0;
		for(int j=0;j<m;j++)
		{
			if((S[test[j].first] > 0) && (S[test[j].second] > 0))
			{
				x++;
			}
		}
		ans=max(x,ans);
		return;
	}
	else{
		S[pep[i].first]++;
		rec(i+1, pep, test);
		S[pep[i].first]--;
		S[pep[i].second]++;
		rec(i+1, pep, test);
	}
}

void solve()
{
    cin>>n>>m;
    S = vector<ll>(n+1,0);
    vector<pll>test(m,{0,0});
    for(int i=0;i<m;i++)
    {
    	cin>>test[i].first>>test[i].second;
    }
    cin>>k;
    vector<pll>pep(k,{0,0});
   	for(int i=0;i<k;i++)
    {
    	cin>>pep[i].first>>pep[i].second;
    }
    ans=0;
    rec(0, pep,test);
    cout<<ans<<endl;
    return;
}

int main()
{
    fast;
    ll tc = 1;
    //IN tc;
    while (tc--)
    {
        solve();
    }
    return 0;
}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What are some similar problems that you factor the N like in D? Any recommendations?

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
Video tutorial for Problem A, B
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, Can anyone please explain me the question C https://atcoder.jp/contests/abc190/tasks/abc190_c

I couldn't figure out what's going on the question. The structure is v peculiar to me since this was my first time participating in this one.

I have put more than an hour to understand the question but still couldn't figure it out.

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

    There are K persons and the i-th the persons can increase either value of Ci or Di by 1(which simply means that the two dishes that are given to him, he can increase the value of any one of them by 1).

    above are the m conditions and the condition i is true if both the i-th dish have value >= 1. so the question is each person should increase the value of the dish in such a way that most conditions are satisfied.

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

Anyone solved E with DSU/Kruskal's algo ?? If yes, please share link to your solution. I am unable to find where mine is going wrong... My solution

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

    Building a graph is one step of the solution. But then we have to find a path in the graph including all of a given set of vertex. That set has nothing to do with a MST, so it is unclear how Kruskal could help in that problem.

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

      Let x and y are two vertices and distance between them is d (from the normal unweighted graph). We will make a new graph with an edge between x and y , weight of that edge will be (d-1). i.e. number of extra gems required for that path. And this new graph will contain only k vertices. This becomes a MST problem then.(Some more manipulation is required of course).
      Feels like unnecessary calculation, but somehow this was the first approach that struck me after reading the problem. Not sure if its right.