atcoder_official's blog

By atcoder_official, history, 3 months ago, In English

We will hold TOYOTA SYSTEMS Programming Contest 2023(AtCoder Beginner Contest 330).

We are looking forward to your participation!

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

»
3 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Good luck for everybody!

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

Good luck for everybody!

»
3 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Good luck for everybody!

»
3 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Good luck for everybody!

»
3 months ago, # |
  Vote: I like it +19 Vote: I do not like it

omg it's the first time i found that there's a discuss of atcoder

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Good luck for everybody!

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

good luck

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

is there any penalty for wrong submissions in atcoder contests?

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

    Yes. 5 minutes will be added to your time. (But only if you end up solving that question. Wrong submissions on problems, that you don't solve, won't give you any penalties).

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

Who the f*%k set today's G? :(

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

    How you solved F? what was the check function in binary search?

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

Problems D and E are easier than problems B and C.

Can't understand problem statement of B. How to solve?

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

    First,find the minimum value of right hand side then find value of x accordingly.

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

    if A-i < L, print L

    if A-i > R, print R

    if A-i is in range [L, R], print A-i

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

Can anyone help with F? I used binary search + two pointers to check, but got 3 WAs in main test, thanks a lot

https://atcoder.jp/contests/abc330/submissions/47936272

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

    I am in the same situation, have you resolved it?

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

    If I understand correctly, you're considering the interval can start at some $$$a_i$$$ and finish at $$$a_i + x$$$, but you may be missing the cases where it can finish at some $$$a_i$$$ and start at $$$a_i - x$$$.

    To handle this I used a copy of the array with the reversed sign, and then you can take the min between both cases. Code

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

    I have solved this problem, you can try this data: 5 5 3 2 2 1 2 4 0 1 0 2

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

@atcoder_official Code in editorial for problem-F is not formatted.

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

My code is failing at only testcase for E — Mex and Update. Not able to figure it out.

Please help. link to submission

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

Is $$$F$$$ solvable through binary search?

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

      Can you explain the check function, please? I have been tried to understand others' code, but failed to do it.

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

        Sure my check function handles x and y coordinates separately. I try to find the minimum moves required for all x and y to end in windows of size mid and then if the sum of both coordinates is less than k that's good'

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

Could anyone tell me the meaning of symbol γ?

Many thanks.

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

    The symbol γ in the editorial of F.

»
3 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

When I run my $$$\mathcal{O}(n \log^2 X)$$$ solution for F on GCC C++, it runs in ~600ms. However, if I run it on clang C++, it runs in ~190ms. Even funnier, if we change a max function call to if-elses, it TLEs on GCC C++.

what the f-

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

Solution of Problem C

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

    precalculate all squares of num till 4e6 and store them in vec. iterate for all possible x values (<=sqrt(d)) . Then rem=d-x*x. find min possible y less than rem using binary search in vec for y and update ans. Link

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

Today's B is fun. In fact, Y is unuseful here, we just need let the $$$X_i$$$ smaller (

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

It was such a pain debugging G because the small samples didn't cover all cases and the big sample was too large to print anything out. Anyways it was a good problem to learn how not to make your code a mess.

»
3 months ago, # |
  Vote: I like it +14 Vote: I do not like it

How my desperate solution of F passed all test cases?

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

    Wow that's a really smart solution. Considering only the $$$x$$$-cordinate ($$$x,y$$$ are independent), I think the intuition here is that you examine all the possible problematic pairs that create the $$$\max_{i}X_{i}-\min_{i}X_{i}$$$ difference.

    Assuming you sort $$$X$$$, at first you look at $$$X_{1}$$$ and $$$X_{N}$$$ (which are the min, max). No matter how you choose the optimal square with side $$$\ell$$$, it will be inside $$$[X_{1},X_{N}]$$$ so you will always just have make $$$X_{1}$$$ bigger to match the left side of the square and $$$X_{N}$$$ smaller to match the right side of the square, in total $$$X_{N}-X_{1}-\ell$$$ times.

    After you handle $$$X_{1},X_{N}$$$ change them so they fit the square. Now the min/max pair that will be problematic is $$$X_{2},X_{N-1}$$$, so you continue using the same logic if it is actually problematic, i.e if $$$X_{N-1}-X_{2} >\ell$$$ (notice that if $$$X_{N-1}-X_{2}>\ell$$$ you can also be sure that the square will lie inside $$$[X_{2},X_{N-1}]$$$). Also you don't really have to stop the loop since any pair afterwards will still have a smaller difference than $$$\ell$$$.

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

Can anyone help with C? I used two pointers , but got WAs in main test, thanks a lot

https://atcoder.jp/contests/abc330/submissions/47945670

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

How to solve C

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

Hints are cool, but I think something happened to the code formatting in the English editorial of F :Clueless:

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

The task_C's constraints is wrong, but I didn't notice about that during the contest. I think it's $$$1 \leq D \leq 2 \times 10^{18}$$$. I hope the wirters will read this comment and fix it.

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

Can anyone give Test case where it fail's problem E https://atcoder.jp/contests/abc330/submissions/47972996

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

The problems are very well structured