atcoder_official's blog

By atcoder_official, history, 11 months ago, In English

We will hold AtCoder Beginner Contest 332.

We are looking forward to your participation!

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

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

Good luck!

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

E is worth 525 points!

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

haha!

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

I hope I can make ABCDE

Good luck for everyone!

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

gl & hf! (though unrated)

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

hope you guys get uogrades and good luck ! :)

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

glhf!

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

Can indians participate in Atcoder contests?

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

Good luck for all of you!

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

Good luck and have fun!

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

E is worth 525 points and F is worth 550 points,emmm.....

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

good luck bro

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

Good luck!

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

Was it intended, that the main difficulty in problem $$$E$$$ is not to lose precision?

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

Why do i think problems after C is way harder than before?

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

can anybody tell why this backtracking logic for d is not working,

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

    My guess is that when you marked a state as visited and would not visit it again, since you're using DFS, the first time a state is visited may not be the best answer.

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

Looks like yet another segtree problem F.

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

imho best ABC contest in a long time, the idea for EF more educational than the usual easy problems, thanks a lot :)

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

Can anyone tell why this submission is getting WA? The logic should be correct after all.

Submission link

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

    What's your logic?

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

      Before and after any swap, the elements on the same row or the same column are preserved. So the task is precisely finding minimum number of swaps to equalize row-wise elements and column-wise elements, which then reduces to counting inversions on each axis.

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

How to avoid precision problem in E, I spent all my time to implement it but still get WA. :(

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

    you can open brackets, (∑x^2 — m∑2x + Dm^2)/D

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    1. pre-calculate the average
    2. divide D at the end

    You don't need to use long double.

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

      I personally got accepted, after I used __float128 instead of long double

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

      Thanks, I got AC when dividing D at the end.

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

On problem E, what makes

cout << (dp.back() * m - sum.back() * sum.back()) / m / m << "\n";

correct while

cout << dp.back() / m - sum.back() * sum.back() / m / m << "\n";

is wrong?

Submission link: AC, WA

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

    It may happen if the difference between the two values are really small ...?

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

      Isn't the ratio of difference and abs of operands the one that matters?

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

    Try this

    2 2
    99999999 100000000
    
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      They both outputs 0.25000000000000000 which seems to coincide with the tourist's E's output. Am I missing something?

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        15 15
        99999999 99999999 99999999 99999999 99999999 99999999 99999999 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
        
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me understand the problem D , i didn't got any clue regarding how to solve that , during the contest

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

    Simple BFS.

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

      the grid one right?, can you elaborate the idea you might have got

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

        I keep changing grid A by one move at a time, until it is same as grid B. Submission

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

          Can you explain the intuition behind the BFS reasoning ? first thoughts is that bruteforcing permutations will give you if there is a solution, but couldn't figure out how to get the shortest number of operations needed

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

          thanks bro , i sure am getting some idea now

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

      Thanks. I wasted most of the contest doing DFS instead of BFS. Then I read your comment and facepalmed. I guess that's why I am Newbie indeed.

      Easy to read solution for other Newbies

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

        That's a very easy implementation bro , got me the idea entirely thanks

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

Can anybody pls tell me .. in which test case my D fails- Submission — https://atcoder.jp/contests/abc332/submissions/48405276

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

    Comparing two rows or columns using set will ignore the number and order of occurrences of each value.

    You can try this 3 3 1 1 2 1 1 2 2 2 1 2 1 1 1 2 1 2 1 2 the answer should be -1.

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

Again :(

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

Wrong on three cases on problem F. Can someone find an error?

Submission

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

In problem E, I believe my implementation has issues.I would like to understand where I made a mistake.

my code with memoization updated code

still showing WA on 6 testcases :(

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

What is the purpose of problem E?

If I use this

long double ans=(long double)((__int128)D*dp[(1<<n)-1][D]-ave*ave)/(D*D);

That's OK.

But this

long double ans=(long double)dp[(1<<n)-1][D]/D-(long double)ave*ave/(D*D);

is wrong.

I know precision is important but this is too ...

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

    I also encounter this problem, maybe take a good care of precision next time :(

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

Problem E, I don't understand why the program that uses fewer double get 5 WAs but the program that uses more double get AC?

In the first program, because:

$$$ \begin{aligned} &\frac{1}{D}\sum_{i=1}^{D}\left(x_{i} - \bar x\right)^2 \\ = &\frac{1}{D}\sum_{i=1}^{D} x_{i}^2 + \bar x^2 - \frac{1}{D}\sum_{i=1}^{D} 2x_{i}\bar x \\ = &\color{red}{\frac{1}{D}\sum_{i=1}^{D} x_{i}^2} + \color{blue}{\bar x^2 - \frac{2 \bar x}{D}\sum_{i=1}^{N} w_{i}} \\ \end{aligned} $$$

I use a dp to calculate the minimal value of the red part. As all the x are integer, and I can avoid using double in dp, I believe it will be more precise. The second problem simply sums $$$\left(x_{i} - \bar x\right)^2$$$ and uses long double in dp. Why the second program AC but the first not?

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

    The two lines

    auto xbar = (long double)s[all] / d;
    long double ans = (f[all] + xbar * xbar * d - 2 * sa * xbar) / d;
    

    lost even more precision than dp with double. ($$$5$$$ double multiplications' precision loss in the worst case)

    Try to change the code to

    long double ans = (long double)1.0 * (d * f[all] - s[all] * s[all]) / (d * d);
    

    It will pass :)

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

      Thanks!

      I get it now. The first program uses a value many times larger than the answer, and the larger the value, the worse the precision. But in the second program, the value used in dp is always smaller than the answer, so there doesn't seem to be much precision lost.

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

why E not output "variance * D * D" as the answer? just to edu us how to "avoid precision problem"?

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

std:1224489579591846.408203

wolframalpha:1224489579591846.408163

So why does the question ask for an accuracy of 1e-6?

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

    In this case, you need to calculate relative difference, not absolute difference.

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

Sorry, but my simple brute force (just do dfs) passed E... Submission.

Can anyone hack it?

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

In problem D. How the number of operations required to obtain a desired sequence A(A1, A2, ... , An) starting from the sequence (1, 2 .... N) by repeatedly swapping adjacent two elements is given as the inversion number of the permutation A. Can anyone explain that!?

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

Hi hope you are well!

Could you please check my submissions for problem E, submissions 48412388 and 48412226 should give the same answer mathematically. It does seem like this problem would be better if it requires an output in p/q format rather (maybe mod 1e9+7 or something) rather than output as a fixed point number. Thanks!

Regards Yuhao

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

Where I can found vedio solutions of today's atcoder contest?

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

In problem F, how to do the replacement which is mentioned in editorial with lazy segtree.

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

    Based on the editorial, each update that happens on an interval changes each of its values from $$$x$$$ to $$$\alpha x + \beta$$$ for some $$$\alpha,\beta$$$ related to the update.

    Two different updates described by $$$(\alpha_{\ell},\beta_{\ell}),(\alpha_{k},\beta_{k})$$$ can be merge to $$$\left(\alpha_{k}\alpha_{\ell},\alpha_{k}\beta_{\ell}+\beta_{k}\right)$$$ because

    $$$ \alpha_{k}\left( \alpha_{\ell}x+\beta_{\ell} \right) +\beta_{k} = \alpha_{k}\alpha_{\ell}x + \alpha_{k}\beta_{\ell}+\beta_{k}. $$$
    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      What is beta hete? What do we need to store and how to do merge /updates

      Can you share a submission link where atcoder library is being used on this problem?

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

        Beta is the part that gets added each query. From the editorial:

        $$$ α = (λ_i-1)/λ_i $$$
        $$$ β = 1/λ_i * X_i $$$

        Here is a submission with the AtCoder library. (not mine)

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

Can anyone suggest any corner cases for this solution. I am confused.Submission Link

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

    change cout << -at << endl; into cout << -mn << endl;

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

There's a $$$O(lgN)$$$ solution for problem B:

let $$$x = GCD(G, M)$$$, $$$ G=ax; M=bx $$$, so there's a cycle with $$$2a+2b-1$$$ operations. After each cycle, both bottles become empty again. So first we mod $$$K$$$ with $$$2a+2b-1$$$ to make $$$0\lt K\lt 2a+2b-1$$$.

Because bottles only become both empty after each cycle, so in cycle it must formed like this:

  • operation type 1/2
  • operation type 3

So in each cycle, each operation with odd index is type 1/2 and each operation with even index is type 3.

If we know the total amount of two bottles, we can know how much in each before/after operation type 3:

  • Before operation type 3, mug holds as more water as possible.
  • After operation type 3, glass holds as more water as possible.

Now we should work out total amount of water.

We can see:

  • If total amount less than G, next operation should be type 2(fill water)
  • If total amount greator or equal than G, next operation should be type 1(empty water)

If there's i operations of type 2 and j operations of type 1, we got current water amount is $$$iM-jG$$$ . And we can find out:

$$$ 0\le iM - (k-i)G < G+M \\ 0\le i(G+M)-kG \lt G+M \\ kG \le i(G+M) \lt (k+1)G+M \\ i = \lceil\frac{kG}{G+M}\rceil $$$

So we can do all rest calculate in $$$O(1)$$$, the total time complexity will be $$$O(lg(min(G,M)))$$$ for "GCD" function.

submission link

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

Can anybody explain the second sample in problem C? I think the answer should be 2

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

    participating a contest requires a logo-shirt, which cant be replaced by the plain one. Since all he had at first is a plain shirt, he has to get 3 (logo) for the 3 contest day. Maybe there is some misunderstood, just check the problem statement carefully.(not english speaker but I hope you can understand what i am talking about)

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

The editorial of D is beautiful :)