chokudai's blog

AtCoder Beginner Contest 250 Announcement
By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 250.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

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

Comments Comments (43)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I have to go in for the contest while getting berated by upperclassmen on discord (time clashes, how sad).

Still, hoping to solve 5 problems!

edit: it was hell, couldn't concentrate

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

The 250th ABC,cheers!

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

G is the same as CF865D. And Ex is almost the same as CF1253F.

I think AtCoder should put more effort in searching the similar problems and avoid them in the contest.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems that problem G is same as https://codeforces.net/problemset/problem/865/D

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem G is the same as CF865D.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D!!! idk why it gets WA! :"(

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

E can be solved with randomized mapping and xor hash.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do E? i was getting WA on 1 testcase.may be my approach was wrong.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Just hash element and check equality. I used simple multiply hash

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

      can u share your solution

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

        Sure you can see this.

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

          Can you explain your approach in detail.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            Sorry for my bad English. I used translator for explanation.

            I decided to store the hashed values as an array for the first x elements.
            For each elements of sequence, the following was followed.

            1. If the element $$$a$$$ is not in the unordered_set, calculate $$$X = hashfn(a)$$$ and update the hash value with $$$hash[i] = hash[i-1] + X$$$. Insert $$$a$$$ into unordered_set for duplicate verification.
            2. If the element $$$a$$$ is in the unordered_set, there is no need for hashing, so $$$hash[i] = hash[i-1]$$$ and then moved on to the next element.

            Then it is simple to deal with the queries. Just check that $$$hash[x_{i}] = hash[y_{i}]$$$. The length of the array is less or equal than 200,000, so I bet that there will be no collision.

            → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I used two pointers. https://atcoder.jp/contests/abc250/submissions/31548536

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

      Can you please explain your code ?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 6   Vote: I like it +3 Vote: I do not like it 
        1) Compress Both arrays, now the values will lie in the range [0, 2*n-1].

        2) qr :stores raw queries, Q[i] -> list of indices of B that are queried with index i of A.

        3) pref is dummy vector<vector> of same size as Q. It will be used for prefix sum.

        4) for each i we increment j till B[j] is present in A[0...i], cnt denotes (sz(set(A[0..i])) - sz(set(B[0..i]))), so naturally when cnt becomes 0 our good segment for current i starts, we can maintain l and r for first and last occurence of cnt=0.

        5) Now updating range pref[i][pos(l)]...pref[i][pos(r)] using prefix sum trick.

        6) Now we can answer all queries. For query(L, R) ans is 'yes' if pref[L][pos(R)] > 0;

        I guess this is an overcomplicated solution for this problem.

        → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Define two arrays $$$L$$$ and $$$R$$$ where $$$L[i]$$$ and $$$R[i]$$$ are the first and last prefixes in $$$b$$$ that are $$$=$$$ the $$$i^{th}$$$ prefix of $$$a$$$. Observe that if $$$a[i]$$$ already exists in the $$$(i-1){th}$$$ prefix of $$$a$$$, $$$L[i]=L[i-1]$$$ and $$$R[i]=R[i-1]$$$.

    We can calculate $$$L$$$ and $$$R$$$ by iterating on the elements of $$$a$$$ one by one, and maintain a pointer $$$bi$$$ for $$$b$$$. If the $$$i^{th}$$$ element in $$$a$$$ is new, while that element is not encountered in $$$b$$$ yet, add $$$b[bi]$$$ to the elements of $$$b$$$ we have seen so far and increment $$$bi$$$.

    After the previous procedure, if no elements exist in $$$a$$$ only or in $$$b$$$ only (can be known through sets), we can set $$$L[i]$$$ to $$$bi-1$$$. Then, while $$$b[bi]$$$ is not new, increment $$$bi$$$. At the end, we can set $$$R[i]$$$ to the new $$$bi-1$$$.

    Submission

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

    The editorial is up and I love YunQianQwQ's approach

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can F be done with two pointers and updating current area (add/minus triangle area) ? UPD : solved, I shouldn't have used double in contest

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

    I think F is similar to rotating caliphers, but did not solved it.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please Tell me how to submit a user Editorial????

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Once your rating reaches 1 Dan, then you can see a 'User Editorial' button.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i don't understand why constraints for $$$X_i,Y_i$$$ are too big , it isn't even guaranteed that area of polygon is less than $$$8 \cdot 10^{18}$$$ (or something)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D, p and q are both prime, or only p?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way to get the "official" standing of AtCoder's ABC contests ?
i.e. to filter out candidates that are too strong to be scored in ABC.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me a counter-case for my solution to problem E?

Thanks in Advanced :)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    2
1 2
1 3
1
2 1

    In this case the first set is {1, 2}, the second is {1}, so the answer is No, but your solution prints Yes.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

anyone explain task d please , one thing i understand that we need to store all prime <=1e6 using seiv

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

    j*i*i*i may cause overflow. I handle it by using __int128 to avoid them.

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

      I solved using j*i*i*i, but with lots of WAs (not recommended)

      We can loop i on reverse from 1e6, then loop j to i-1 inside.

      That way we can catch overflows by breaking j loop early.

      The question is will it get TLE or not?

      Considering the sample test is 1e15 with 1e5 let's hope it won't TLE with 1e18 input.

      Prove:
      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This is how I solved the problem.

    As mentioned in the problem ,we need to find the number of good numbers $$${k}$$$ such that :

    $$$\hspace{50mm} {k=p×q^3}$$$ with primes $$$\underline{p < q}$$$.

    The maximum value which q can reach will be when $$${p = 2}$$$ and we get :

    $$$\hspace{63mm} \displaystyle { q = {\left(\frac{k}{2}\right)}^{\frac{1}{3}}}$$$

    Thus for a upper bound on N as $$${10^{18}}$$$ : we would be considering all the primes $$${q \le 10^6}$$$ and since $$${p < q}$$$ we will also have $$${p < 10^6}$$$.

    For a given $$${n}$$$ iterate over the values of $$${q}$$$ only till the point that $$$\displaystyle {q ^ 3 \le n}$$$.

    This will avoid overflow issues as the maximum value of $$${q}$$$ is bound by $$${10^6}$$$ hence $$${q^3}$$$ won't exceed $$${10^{18}}$$$ .

    For a given $$${q}$$$ we can just find all the primes $$${p}$$$ such that :

    $$$\hspace{55mm} p \le min \left({q - 2} , {\displaystyle \frac{n}{q^3}}\right) $$$.

    This can be done using upper_bound on the primes array for each q and then we can sum the answers up to get the count of good numbers $$${k \le n}$$$

    → Reply