We will hold AtCoder Beginner Contest 332.

- Contest URL: https://atcoder.jp/contests/abc332
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20231210T2100&p1=248
- Duration: 100 minutes
- Writer: math957963, leaf1415, evima, m_99
- Tester: physics0523, cn449
- Rated range: ~ 1999
- The point values: 100-200-300-425-525-550-625

We are looking forward to your participation!

Good luck!

E is worth 525 points!

haha！

I hope I can make ABCDE

Good luck for everyone!

gl & hf! (though unrated)

off-topic: any specific tip to be red?Ask Kevin114514.

hope you guys get uogrades and good luck ! :)

glhf!Can indians participate in Atcoder contests?

I guess you can if you have the account in <atcoder.jp>, but I don't know whatever it's forbidden in India or not.

Yes,they can .I would highly recommend it also.

okay

Good luck for all of you!

Good luck and have fun!

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

good luck bro

Good luck!

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

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

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

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

Looks like yet another segtree problem F.

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

What's wrong in my solution of $$$D$$$?

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

Submission link

What's your logic?

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.

I had similar logic and I am also getting 4 Test cases wrong. Not sure of the reason though.

Also all of my failed test case failed in your case as well.

Link to submission: https://atcoder.jp/contests/abc332/submissions/48394796

I did the same, but it didn't work for me. I guess my code to find inversions using mergesort was wrong. Anyways, Thank you!

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

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

You don't need to use

`long double`

.I personally got accepted, after I used

`__float128`

instead of`long double`

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

On problem E, what makes

correct while

is wrong?

Submission link: AC, WA

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

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

Try this

They both outputs

`0.25000000000000000`

which seems to coincide with the tourist's E's output. Am I missing something?can anyone help me understand the problem D , i didn't got any clue regarding how to solve that , during the contest

Simple BFS.

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

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

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

thanks bro , i sure am getting some idea now

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

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

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

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`

.Again :(

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

Submission

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

my code with memoization updated codestill showing WA on 6 testcases :(

What is the purpose of problem E?

If I use this

That's OK.

But this

is wrong.

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

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

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:

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?The two lines

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

Try to change the code to

It will pass :)

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.

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

std:1224489579591846.408203

wolframalpha:1224489579591846.408163

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

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

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

Can anyone hack 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!?

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

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

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

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

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?

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

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

Thanks

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

change

`cout << -at << endl;`

into`cout << -mn << endl;`

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:

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:

Now we should work out total amount of water.

We can see:

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:

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

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

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)

The editorial of D is beautiful :)