We will hold AtCoder Beginner Contest 250.
- Contest URL: https://atcoder.jp/contests/abc250
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220508T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: m_99, physics0523
- Tester: kyopro_friends, math957963
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!
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
The 250th ABC,cheers!
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.
It seems that problem G is same as https://codeforces.me/problemset/problem/865/D
Problem G is the same as CF865D.
Really a sh*t round.
Problem D!!! idk why it gets WA! :"(
if u used inbuilt functions for calculating cube root then chances of precision error is there.
Nope! just num*num*num !
u should store prime nos till 1e6 i guess
E can be solved with randomized mapping and xor hash.
How to do E? i was getting WA on 1 testcase.may be my approach was wrong.
Just hash element and check equality. I used simple multiply hash
can u share your solution
Sure you can see this.
Can you explain your approach in detail.
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.
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.
Got it. Thanks bro.
I used two pointers. https://atcoder.jp/contests/abc250/submissions/31548536
Can you please explain your code ?
I guess this is an overcomplicated solution for this problem.
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
The editorial is up and I love YunQianQwQ's approach
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
I think F is similar to rotating caliphers, but did not solved it.
Please Tell me how to submit a user Editorial????
Once your rating reaches 1 Dan, then you can see a 'User Editorial' button.
so if my rating is low , i cant submit it?
Yes.
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)
The maximum area can reach is (8 * 10 ^ 8) ^ 2 (sample test 2)
that's right , thanks
Problem D, p and q are both prime, or only p?
They are primes. I asked.
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.
Click customize and check 'Show rated'.
Can anyone give me a counter-case for my solution to problem E?
Thanks in Advanced :)
In this case the first set is {1, 2}, the second is {1}, so the answer is No, but your solution prints Yes.
Thanks :D
anyone explain task d please , one thing i understand that we need to store all prime <=1e6 using seiv
j*i*i*i may cause overflow. I handle it by using __int128 to avoid them.
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-1inside.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 by submission :')
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 \lt 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 \lt q}$$$ we will also have $$${p \lt 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}$$$