atcoder_official's blog

By atcoder_official, history, 9 months ago, In English

We will hold Toyota Programming Contest 2024#2(AtCoder Beginner Contest 341).

We are looking forward to your participation!

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

»
9 months ago, # |
  Vote: I like it -8 Vote: I do not like it

lovely score distribution :)

»
9 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Hope I can AK!

»
9 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

475 F & 575 G ?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish I could pass A, B, C, D, change the rating from 23 to 100.

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

    But if you pass ABCD,you will up to over 100,even 200

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

      If you pass ABCDEFG in half an hour,you will up to over 2000,even 2300.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I can AK!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope ABCDEF!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If I can pass ABCDEF,maybe I can up to 1000+. But if F is 525+, maybe I can up to 1100.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I can pass ABCDE!!

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Hope I can get 1Dan in this contes!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope to AC A-E. Good luck!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Atcoder down?

»
9 months ago, # |
  Vote: I like it -34 Vote: I do not like it

trash round,atcoder worse and worse

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Can we please talk about our solutions?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

noo why do they remove one piece in problem F :(

»
9 months ago, # |
  Vote: I like it -13 Vote: I do not like it

I wonder why they like segment tree so much.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why my problem E failed: My Solution

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why this code for D is getting WA?

My Code
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    LCM is n*m/gcd(n, m), not just n*m.

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

    Can you explain to me the solution to your problem D? I can't come up with an effective solution

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

      Binary Search for answer, number of values that are multiples of X for an integer N = $$$N / X$$$. In general here only one of the two holds for Kth smallest value $$$value \vert N$$$ or $$$value \vert M$$$. But notice how for all multiples of $$$lcm(N, M)$$$ they are counted twice (once for N, once for M) so remove them. Hence finally for any integer X you get the formula $$$ X / N + X / M - 2 * lcm(X, Y)$$$. Now this range can be $$$[1, max(N, M) * K]$$$. To check fast user binary search.

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

        could elaborate why the upper bound is

        $$$ [1, \max(n, m) \times k] $$$
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Assuming $$$m = max(n, m)$$$ $$$m \times k$$$ gives the $$$kth$$$ number that is divisble by m. Till this range there are $$$(m \times k) / n$$$ numbers divisble by n and k numbers divisble by m. You can easily see $$$(m \times k) / n + k - (m \times k) / lcm(m, n) >= k$$$.

»
9 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

My Problem G failed, could anyone find why I'm wrong?

I divided the sequence to the $$$O(\sqrt{n})$$$ blocks, and I calculate the maximum average perfix of each block.

For a query $$$i$$$. I calculate the answer in the block of $$$i$$$ first. Then, for each block next the block which $$$i$$$ belongs, I compare the maximum average perfix with the now answer, if it's bigger, I will infer the position which get the maximum is good, and calculate it into answer.

My proof is below.

First, the last element of the maximum average perfix of a block must bigger(or equal) than the number of maximum average perfix. If the maximum average perfix if bigger than now answer, we could infer that last element if bigger than the now answer. So we choose the last element is better.

Thanks.

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Was there a typo in the post you guys made or is it actually being hold?

The first line of the post was this:

We will hold Toyota Programming Contest 2024#2(AtCoder Beginner Contest 341).

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I've written smth interesting for problem E here.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the rating update today so slow?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E , I am storing indexes where the element is equal to the previous element. For a range l to r , I am finding largest index from the stored indexes which is smaller than or equal to r , if it is greater than l the answer is NO otherwise the substring is good . I am getting WA. Do I miss something . Submission

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Loved Problem B&G . Best Atcoder beginner round ever!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

G blows my mind.