snuke's blog

Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306） Announcement
By snuke, history, 17 months 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?
»
17 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Ordered set

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

      You are talking about F — Merge Sets right?

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

        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

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

          Oh, yes, it seems that the idea is roughly the same and there are many different implementations.

          → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      I don't trust this thing anymore tbh, shit constant factor

      → Reply
»
17 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Unrated!!

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Whenever I perform good (yesterday solved Till F) it gets unrated :(

    Anyways enjoyed a lot!

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

my solution is still not judged. Submission

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

    Mine was judged after contest, so i think you must wait a bit

    → Reply
»
17 months ago, # |
  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
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

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

    I believe this is the intended solution indeed

    → Reply
»
17 months ago, # |
  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
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    its frustating when it happens so frequently, what a bad feeling to complete the contest and realize its unrated

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can we do E using segment tree?

→ Reply
»
17 months ago, # |
  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
  • »
    »
    17 months ago, # ^ |
      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
  • »
    »
    17 months ago, # ^ |
    ← 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
»
17 months ago, # |
  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
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think I also failed the same test cases when I missed the case when K and N are equal

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

      Got it. Thanks!

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

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

      → Reply
»
17 months ago, # |
  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