Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

snuke's blog

Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306） Announcement
By snuke, history, 3 years ago, In English

We will hold Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306）.

We are looking forward to your participation!

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

Comments Comments (29)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Will it be rated ? (considering the delay in judging)

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

I solved F using fenwik tree, is there easier solution?

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

Unrated!!

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

my solution is still not judged. Submission

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

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?

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

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 ;(.

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

can we do E using segment tree?

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

Hi! I'm not sure where to discuss the problems so I just post it here.

The Japanese editorial of problem G states that

  • $$$L$$$ (the set which contains all lengths of cycles) might be an infinite set.
  • Let $$$g$$$ be the greatest common divisor of all elements in $$$L$$$, if $$$g = \text{gcd}(l_1, l_2, \cdots, l_t)$$$, then all multiples of $$$g$$$ larger or equal than $$$\text{lcm}(l_1, l_2, \cdots, l_t)$$$ will appear in $$$L$$$.

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)$$$?

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

    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).

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

    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.

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

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.

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

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.

→ Reply