Блог пользователя chokudai

Автор chokudai, история, 4 года назад, По-английски

We will hold AtCoder Beginner Contest 177.

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

We are looking forward to your participation!

  • Проголосовать: нравится
  • +63
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Atcoder beginner at 5:30, codechef lunchtime at 7:30, tomorrow cf Div 2 666. Good happy weekends for cp lovers :>

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится
    Today
    Tomorrow

    :)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Could you please suggest some good cp website to practice. I found binarysearch.io quite interesting. Please suggest some. Thanks

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Also worst weekend for getting brutally killed when problems are tough ..

»
4 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

I think atcoder admins are not at all interested in begineer contest now-a-days.

problems are also repeating more from some time. why?

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve problem F?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +60 Проголосовать: не нравится

    Store an array $$$a$$$ where $$$a[i]$$$ denotes the minimum number of rightwards moves to get to a column $$$i$$$ at row $$$r$$$. We can simply add the fixed number of downward moves at the end. We update this at each row when we go from row $$$r$$$ to $$$r+1$$$. So in the beginning it is $$$a = {0, 0, \dots, 0}$$$. Note that when we try to move to the next row, and are forbidden from going downwards from columns $$$[L, R]$$$, we have that for $$$i\in [L, R]$$$, $$$a[i] = a[L-1] + i - (L - 1)$$$. The rest of the values in $$$a$$$ stay the same. If $$$L = 0$$$, then $$$a[i] = INF$$$ for $$$i\in [L, R]$$$, where $$$INF$$$ denotes impossibility to get to that location, formally stored as a large number. We can store the array as blocks of consecutive numbers. For example, the array $$${1, 2, 3, 2, 3, 6}$$$ could be compressed into $$${ ((0, 2), 1), ((3, 4), 2), ((5, 5), 6)}$$$, where these denote an interval and the starting number of the block of consecutive numbers. Then updates can be done in $$$\mathcal O(\log W)$$$ using a set. We then simply query for the minimum value of any block of consecutive numbers, and add the current row number for the vertical moves. If this is $$$INF$$$, then we know we can't get to this row. Overall, this runs in $$$\mathcal O(H\log W + W\log W)$$$.

    Submission

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you elaborate on the blocks of consecutive numbers and the compression of arrays?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        To actually do this, I use an interval union data structure (not an official name, just the name of my template). What it does is it stores a bunch of intervals (currently, it doesn't handle repeated intervals, but it's not hard to change to multiset to handle it). You can then query the intervals that intersect the a given interval in the data structure in $$$\mathcal O(X + \log I)$$$, where $$$I$$$ is the number of intervals in the structure and $$$X$$$ is the number of intervals intersected. You can also add and remove intervals in $$$\mathcal O(\log I)$$$ time. So to change a block of intervals, I simply query the intervals intersected by $$$[L, R]$$$, and remove them and update the endpoints. See my code for more details on implementation.

        If you want other problems that can use something like an interval union data structure, see Facebook Hacker Cup 2020 Round 1 problems A2 and A3, although they are a little terrible to implement.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    It is segment tree with a clever range update. I was not able to make a working implementation, but others did.

»
4 года назад, # |
  Проголосовать: нравится +65 Проголосовать: не нравится

Difficulty

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is wrong with my solution for E?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D ?

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Participated in Beginner contest for the first time. Missed the announcement, started 40 minutes late, but managed to solve 3 problems. Could you guys post the announcement 24 hours earlier, if that's not too inconvenient for you?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to do C? I tried it using prefix sums and got right answers for sample inputs. Still WA.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can find it here.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Compute the times all integers within the given range occurred as a prime factor, then

    • If every one of them occur no more than once, then pairwise coprime,
    • Or, if at least one of them occour $$$n$$$ times, then setwise coprime,
    • Or, not coprime

    https://atcoder.jp/contests/abc177/submissions/16343274

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Even if one prime factor occurs more than once, it enough to say it will be either setwise or not distinct depending upon the whole gcd.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is enough to create the set of primefactors foreach a[i] and check if any primefactor is in any others a[j] set.

    Additionally calculate the gcd of all a[i].

    submission

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I used the same approach but it failed.Can you please tell me what's wrong with my code? https://atcoder.jp/contests/abc177/submissions/16376967

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      code

      logic
      * notprime if gcd(a1,a2,---,an)>1
      * setwise prime if any two elements ai,aj have a common divisor, for this just memories the divisors which we have encountered
      * other wire pairwise prime

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      spookywooky What will be the complexity of your solution?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Yes.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          but what if all numbers are prime then the fact function will have to check till $$$\sqrt(N)$$$ for all numbers ?

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Dude, I changed my answer, previously i thought he was storing the smallest prime factor for each number using Sieve, but i was mistaken, you're right. Though most optimized solution of this problem is of complexity Nlog2(N)

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              then why his code is not giving TLE verdict?

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Because, N and MAXN ranges are 10^6, now to bottleneck the solution you have to find 10^6 such numbers which are distinct because as soon as it will encounter any two numbers which happen to be the same or have gcd > 1, it will terminate instantly and thus, code never reached 10^9 iterations. 1 sec of C++ can accommodate about 2 * 10^8 iterations which i also suppose is very hard to reach, which by the ac time you can see its even less than half of them.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится +5 Проголосовать: не нравится

                  Ok got it so the method of implementation is optimizing the solution because as soon as we are factorizing we are checking if the prime factors already exist.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    approach for E :

    for setwise coprime : i used the recursive property of gcd

    for pairwise coprime : is it possible to make a set(size > 1) from given numbers s.t if we take any two element from the set whose gcd is atleast x.

    if it is not possible for x>1 then paiwise coprime

    submision

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem E can someone tell me what is wrong in my code

I got WA for 5 test cases

code
»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Solution of problem E(Coprime) :

Firstly we will calculate the smallest prime factor of all the numbers(due to the given constraints).

Secondly, we will store the different prime numbers in the prime factorization of a number in a set for each number in the array. We will do this for all the elements.

Lastly we will iterate over the different prime numbers of the prime factorization of all the numbers in the array, and maintain an hash array for the prime numbers found.

If we don't find any prime number which occurs in more than 1 number, then our ans will be pairwise co-prime, else, if the gcd of all numbers is 1 then the ans is setwise coprime otherwise it is not coprime

If anything is not clear, please ask.

And if anyone got a solution with better complexity, do share it.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell me what is wrong with my submission for problem C?

https://atcoder.jp/contests/abc177/submissions/16372833

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please tell me the what is the wrong in my code. here is my solution

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why are ABCs always unbalanced, how can mid-level participants use atcoder to improve?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ya there shall be more ARCs!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    They just could have used some tougher E. I took some time at B, then got a WA in E and that costed me.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Rarely are some atcoders good for practice. Mostly are easy till E then out of the world F. After giving contests on codechef, atcoder and codeforces, I think only codeforces is the one which could help us improve, there is always something to upsolve.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Well, you forgot the old atcoder problems. There are a lot of interesting E's and F's there including this F to solve. Atcoder problems are better in my opinion but they are making unbalanced rounds recently.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi, someone can help me with problem E?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone explain the question F?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    After each of the H rows we have foreach starting position a "shift" to right if we start at that position. The starting position with the min shift is optimal to start (because it produces the shortest path).

    So we need to calculate/maintain these shifts efficiently. This is possible with a segment tree and lazy range updates, but the implementation is tricky. Because every position is not simply updated. The Update-Function is something like: newVal=max(oldVal, position-b[i])

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

if anyone is getting WA on just one test case in problem E ..try this:

3

1 1 1

answer should be "pairwise coprime"

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Why is this approach for problem C wrong??????

My Code
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You have done a mistake. Consider sum1 is 1e9+8 we are at an array element 2 . Now you take addition of 2%(1e9+7) and sum1 becomes 1e9+10. Same way you have done mistakes with sum and total.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

If anyone need short explanation & sample implementation from A-E Here

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain this in problem $$$F$$$. I didn't understand this — $$$you \,cannot\, move \,down \,from \,the$$$ $$$A_i th, (A_i+1)th,...B_i th$$$ $$$squares\, from \,the \,left \,in \,the$$$ $$$i^{th}$$$ $$$row \,from \,the \,top$$$

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In first row you cannot go down at positions in interval (a[1],b[1]), in second row you cannot go down at positions (a[2],b[2]) etc.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think 'at' should be replace with 'from'. But still then what does this remaining part signifies $$$"from\,the\,left\,in\,the \, i^{th} \,row\,from\,the\,top"$$$. Because what you are saying is clear without this part also. Does this part trying to say something extra?

»
4 года назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

from itertools import accumulate mod= 1e9+7 def main(): n = int(input()) a = list(map(int,input().split())) ans =0 ac = list(accumulate(a)) for i in range(n): ans += a[i]* (ac[-1]-ac[i]) ans %=mod print(int(ans))

Can someone tell me why answer of C is wrong in some cases when mod=1e9+7(float) but 10**9+7(int) is right. Thank you!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it true that set of distinct integers {a,b,⋯z} is pairwise coprime if its product is equal to its least common multiple? can we solve problem E using this?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you can't use lcm bcz if all numbers are prime, you will end up the lcm to be greater than the range of int as well as long long.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

lol during the contest on E, I was printing "set coprime" instead of "setwise coprime" and I wasn't able to debug it.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    That's why I copy-paste the magical strings from the problem statements. Too easy to make a mistake

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +45 Проголосовать: не нравится

Personal editorial for this contest:

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you explain what does the "lo" and "lh" means in the code of problem F?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Could you please explain update [L,R] to f(i)=f(L-1)+i-L+1(since we must go right from L−1)

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

        You can take it as a DP solution, consider dp[i][j] means: the minimum moves to reach the position (i,j). So dp[1][j] is always 0.

        Now, suppose there is an example with W = 9 and the first row is like:

        O,O,O,X,X,X,X,O,O

        (X for blocked grid)

        Then, you can see that the dp[2][-] should be:

        1,1,1,2,3,4,5,1,1

        Based on the observation above,we can use formula to conclude it:

        a. if (i-1,j) isn't blocked, then dp[i][j] = dp[i-1][j]+1.

        b. if (i-1,j) is blocked, then dp[i][j] = dp[i-1][x]+1+(j-x), where x is the maximum number (rightmost) with (i-1,x) isn't blocked. The formula "f(i)=f(L-1)+i-L+1(since we must go right from L−1)" you mentioned is about this one.

        You may see the example above for better understanding.

        Now, the question is how to optimize this solution and it's natural to think of segment tree and that's what I don't understand lol

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      "lo" means minimum, "lh" means the current value of the left endpoint.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Wow. It was helpful. I bookmarked that site.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I have added some comments to the code of Problem F, hope they will help.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain how to make the second update and find minimum then?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      We store the value of the left endpoint and the minimum in our segment tree nodes.

      For the second update, we just update the left endpoint according to the value of $$$l-1$$$, and when pushing down, we can just use the information stored in the parent node. Also, since the value will increase from left to right, the minimum will be set to the value of the left endpoint after the update.

      For the range minimum query, we just choose the minimum of left child and right child.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

For E, why if(n>80000) {cout<<"setwise coprime\n";return 0;} is not correct? In my view,$$$80,000$$$ is larger than $$$\pi(1000000)=78,498$$$ ,so there must exist $$$(i,j)$$$ which have same prime factor. my submittion

»
4 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

plz explain correct logic behind F or give a link of easy to understand submission

my WA submission

EDIT-> it is wrong because we can start from any column

WA solution

Logic-> for every row we need to find out the lowest column we can visit

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just a little thing here .. why have they stopped tagging this blog for each contest on the atcoder page for few time now ?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hey! Can Someone help me figure out what am doing wrong here, getting WA on a few testcases.

E-Coprime

Thanks!

»
4 года назад, # |
Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

Can some tell whats wrong with my submission? Was not able to pass 2 tests:(

https://atcoder.jp/contests/abc177/submissions/16373270

The logic is to check setwise coprime, just find gcd of whole array and check if it 1. For pairwise i counted the number of numbers that are divisible by some number. If for any number, there are more than 1 numbers that are divisible by it, its not pairwise coprime.

E-Coprime

Please.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Try the case with all elements as 1.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Its giving correctly, pairwise coprime.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Ok your mistake is like if we have a prime number. Let's say 13. You are checking it till sqrt(13). 13 as a prime isn't being counted. Like if we have two elements 13 and 65. we have a common factor 13 between them . But your code won't show. If you want, I can help with correcting the code further.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    logic is correct but implimentation is wrong.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell me what is wrong in my approach for E. Link

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

For problem C, we can write $$$\sum_{i =1} ^{N - 1} \sum_{j = i+ 1}^{N} A_iA_j = \frac{((\sum_{i = 1}^{N}A_i)^2 - \sum_{i = 1}^{N}A_i^2)}{2}$$$. I used this, but got WA.What is wrong with my solution?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In the end of your solution you are dividing the answer by 2, but you can't do it by simply using operator "/" in modular arithmetic, you can read an article about it here. Also, I would say that your solution is too complicated, to get the answer you just need to calculate how many times will every number in the array be added, you can do that using prefix sums, see this solution.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your formula is fine, but remember that you work with MOD, so you can't just divide your answer by 2. If you'll take modular multiplicative inverse, you'll get AC. Your modified solution: link.

    For example: you should print answer $$$\frac{200}{2} \mod 109$$$. You're taking $$$\frac{200 \mod 109}{2} = 45$$$, that's wrong. Correct solution is: $$$200 * 2^{-1} \mod 109 \equiv 200 * 55 \mod 109 = 100$$$.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      extra caution: in the example above, $$$gcd(200, 109) = 1$$$
      if $$$gcd(200, mod) \neq 1$$$ then you can't use inverse multiplication for division

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yeah, sure, that's why all MOD's are prime: $$$10^9 + 7, 998244353$$$ and so on. That's important note, thanks!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem E I checked the condition of pair-wise coprime by using the fact that if $$$a_{1} a_{2} a_{3} ..... a_{n}$$$ are pair-wise coprime then their product = their LCM and for setwise coprime I checked that gcd over all numbers should be 1.My code is failing on some test cases.my submission

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    lcm grows very quickly so you can't store it in even long long.

    Consider 2 primes very close to 10^6 their lcm can be as large as 10^12. So if we have n distinct primes lcm can be 10^(6*n) although that's a very light upper bound value of distinct prime also decrease but still you get the idea you can't store lcm.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Is there any possible way to incorporate modulo operator with the lcm finding?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your LCM will overflow, and I think your solution might not be logically correct. Let's say the lcm of the array comes out to be x and the product the array comes out to be Mod + x then in this case your solution will output pairwise coprime whereas the correct output could be any of the 3 outputs. For example let the elements of the array be [Mod, Mod, Mod, Mod] then the lcm = Mod & product = Mod ^ 4, this will lead to the answer not coprime but your solution will give pairwise coprime. This example does not fit into the constraints but there will surely be one such testcase that will fit.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone hack my solution for problem E because I think there are weak-test cases. Here my another solution get accepted even though this fails for this simple testcase [1, 1, 6, 1].

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Share a solution without segtree for problem F.

Code
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    The main idea : use a set to store the nearest place in the row i which can be reached from column "j".Suppose it's d[j] for the j-th column,and use another set to store "d[j]-j" for finding the smallest "d[j]-j".

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Either my English is poor or the statement of problem F is not clear. Please help me to understand restricted moves.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For all $$$(i, j)$$$ such that $$$1 \leq i \leq H$$$ and $$$A_i \leq j \leq B_i$$$, it is prohibited to make moves of $$$(i, j) \to (i+1, j)$$$.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please explain why I am getting TLE in problem C?

Spoiler
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    You used 2 nested for loops, so you exceeded the time limit. Find a better approach with a better time complexity.

    It's a basic thing to notice you can't run 2 nested for loops like that. Do you know how to estimate time complexity?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • I'm beginner and solved A,B and C problem.I tried to use union find to solve D problem but got wrong answer.
  • I think the max size of the connected component is the answer.Is this concept wrong?What's wrong with my code?Can anyone teach me to adjust?thanks you very much. code is below (by python3)
code here...by Python3
N,M=map(int,input().split())
par=[i for i in range(N+1)]
size=[1 for i in range(N+1)]
def find(x):
    if x!=par[x]:
        par[x]=find(par[x])
    return par[x]
def union(x,y):
    if find(x)!=find(y):
        par[y] = par[x]
        size[x] += size[y]
res=N
for i in range(M):
    s,e=map(int,input().split())
    union(s,e)
print(max(size))
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Add 2 characters to WA code and it passes: https://atcoder.jp/contests/abc177/submissions/34640706

    The issue is $$$x = m[n-1]-m[i]$$$ might be a negative value if you apply $$$m[i]$$$ mod $$$d$$$(which isn't necessary to do so in this case). In some languages like C++, modding negative values is a bit weird, so you make it non-negative by adding $$$d$$$ to $$$x$$$ (as $$$|m[n-1]-m[i]|<d$$$ in the WA code) before modding by $$$d$$$.

»
22 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

in problem E

this code passed from 25 test and failed in only one test

can someone explain what's the wrong ?

  • »
    »
    22 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Corrected here.

    I debug your code in order to improve my debugging ability. You miss a case where there is no prime at all, i.e., all $$$a[i]=1$$$. So if(mx == 1) should be if(mx <= 1).

    Besides, potential integer multiplication overflow exists in your code.