We will hold Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306）.
- Contest URL: https://atcoder.jp/contests/abc306
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230617T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: physics0523, yuto1115, evima, Nyaan, m_99
- Tester: m_99, cn449
- Rated range: ~ 1999
- The point values will be 100 — 200 — 250 — 400 — 475 — 525 — 600 — 650.
We are looking forward to your participation!
Will it be rated ? (considering the delay in judging)
They just announced it will be "unrated" :(
I solved F using fenwik tree, is there easier solution?
Ordered set
You are talking about F — Merge Sets right?
Yes. You just need to find the contribution of each element one by one by finding count of elements smaller than it ahead. Maybe you can use some other technique too but oset came to my mind. Solution
Oh, yes, it seems that the idea is roughly the same and there are many different implementations.
I don't trust this thing anymore tbh, shit constant factor
Unrated!!
Whenever I perform good (yesterday solved Till F) it gets unrated :(
Anyways enjoyed a lot!
my solution is still not judged. Submission
Mine was judged after contest, so i think you must wait a bit
Problem G: I submitted this but I am still waiting for the verdict, Get the SCC that contains node 1 then get the gcd of all cycle lengths and check if it's in the form of $$$2^x5^y$$$.
Any idea if this will pass/not?
I had the exact same idea but was lazy to implement it since I wasn't sure about F's verdict, I guess it'll pass if implemented carefully
I believe this is the intended solution indeed
Two out of the last three ABCs were unrated. What's the issue surrounding the long judge times, frequent DDOS attacks or just the servers not being able to handle huge traffic?
I wish this problem is being taken care of by maybe making an optimization like on codeforcss judges to stop judging if a test case doesn't pass. Its kind of frustrating to finish the whole contest just to realize it's unrated ;(.
its frustating when it happens so frequently, what a bad feeling to complete the contest and realize its unrated
can we do E using segment tree?
i think by only using two ordered sets (prefix and suffix) as well as the tracker for the suffix sum, it also works
With simple sets, it can also be done. https://atcoder.jp/contests/abc306/submissions/42361724
Yes
Hi! I'm not sure where to discuss the problems so I just post it here.
The Japanese editorial of problem G states that
So if $$$L$$$ is an infinite set, $$$l_i$$$ might be infinitely large, so $$$\text{lcm}(l_1, l_2, \cdots, l_t)$$$ might be infinitely large. How can we make sure that $$$X = 10^{10^{100}}$$$ is large enough so that we can directly check if $$$g$$$ is a divisor of $$$X$$$? That is to say, how can we calculate the upper bound of $$$\text{lcm}(l_1, l_2, \cdots, l_t)$$$?
I think you wouldn't need to use them all though, if you take one with less or equal than n, then you only need to consider additional cycle sizes such that the primes different from 2 and 5 are not factors of the gcd, so every time you consider one more cycle size you divide the gcd by at least 2, meaning you only need $$$O(\log n)$$$ in total, the product of which should be smaller than X (and also their lcm).
Construct a cycle $$$C$$$ such that it starts in $$$1$$$ and contains all vertices, it's easy to see that such cycle has length of at most $$$(n-1)\cdot n$$$. As you mentioned lcm can be infinite, so let's shrink $$$L$$$ as much as possible so that the gcd stays the same. If you clear it completely and start with just $$$C$$$, you may need to get rid of up to $$$10$$$ prime factors. Notice that for any prime $$$p$$$ that is not a divisor of $$$g$$$ there exists a simple cycle with length not divisible by $$$p$$$ (you can take a non-simple cycle and split it in two, then at least one cycle that remains has length not divisible by $$$p$$$). So you can find such simple cycle, glue it to $$$C$$$ (length now is at most $$$n^2$$$) and remember the result. This way you will get up to $$$11$$$ cycles with gcd of their lengths equal to $$$g$$$, and their lcm is at most $$$(n^2)^{11} = n^{22}$$$, which is surely smaller than $$$10^{10^{100}}$$$.
Thanks to ffao for the idea.
Can someone help me figure out why I'm getting a RE on Problem E? My submission: https://atcoder.jp/contests/abc306/submissions/42513820 I tried generating random testcases for N = 1e5, K = 5e4 and Q = 1e5 but didn't get any RE. I guess it failed at a well curated testcase that can't* be generated randomly.
I think I also failed the same test cases when I missed the case when K and N are equal
Got it. Thanks!
For me, when my logic was wrong for K==N, there were 2 tests that failed, not 4. Submission
(Luckily, the judge returned WA soon enough,)
Hi snuke
I wrote an English user editorial here.
Later, someone pointed out that it was wrong. I wrote $$$10^8$$$ but it got AC.
I've updated it and it's $$$10^{18}$$$ now.
It will be better if you can add a hack testcase. Just a cycle length $$$131072$$$ is ok.