We will hold AtCoder Beginner Contest 371.

- Contest URL: https://atcoder.jp/contests/abc371
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240914T2100&p1=248
- Duration: 100 minutes
- Writer: MMNMM, nok0, physics0523
- Tester: physics0523, kyopro_friends
- Rated range: ~ 1999
- The point values: 150-200-300-350-475-550-575

We are looking forward to your participation!

Wish U to get good grade.

Didn't get good grade because I started with problem F at first.

How the hell could the difficulty of the questions be ranked like this? I don't want to endure until the end, so now it's the first hour of the competition that has just ended, and the current passing situation is:

A 8740 / 9353

B 8505 / 8694

C 2790 / 2918 ?

D 4159 / 4730

E 1984 / 2142

F 85 / 150 ??

G 62 / 274 ?

True dude, I'm stuck on F and G. Mostly I will pass ABCDE and think for F or G and solve it (at least solve half of it) but this time I really have no idea.

Was the solution to G seriously to use python... lol

Don't understand why the editorial was written like that. There are ways that don't require any operations with numbers greater than $$$n$$$.

The Python solution is way easier though (I used another way but it cost me an hour of debugging).

How to solve G? Without any operations with numbers greater than $$$n$$$?

Please share if you don't mind!

I've just finished writing it and posted it on AtCoder. You can check it out :)

Maybe I need a book called "Python Crash Course"

Wasted 60 minutes trying to avoid big integers, and the official solution is to use big integers.

Relatable

my solution of E with lazy segtree. also how to solve C?

Just brute force on all permutations and calculate minimum.

plz explain in details how to solve it using seg tree ?

first construct a prefix array where $$$ pref_i $$$ tells the answer for $$$ f(1, i) $$$. segment tree will be constructed on that. then focus on what happens when we move from $$$ i $$$ to $$$ i + 1 $$$. We're deleting the element at index $$$ i $$$. if that's the last occurence of that element then the suffix $$$ [pref_{i+1}, pref_{i+2}, .... pref_{n}] $$$ all will be decremented once because one unique element has been permanently removed. otherwise we know there is at least one $$$ j $$$ such that $$$ a_i = a_j $$$. we can find that $$$ j $$$ using binary search. the same process will happen but this time the decrement will be only occur at the part $$$ [i + 1, j) $$$. Note that j is non-inclusive. that's because at index j, everything will become normal. all of this can be tracked with lazy segment tree and range operations.

E doesn't actually need lazy segtree. If you reorder the "queries" in a clever way, you can see that the seg operations reduce to simply adding one to a segment and querying total sum. This doesn't need a tree at all, and in fact doesn't require the array itself to be built. Maintaining the total sum as well as the last occurrence of each element was sufficient: https://atcoder.jp/contests/abc371/submissions/57767852

C was bruteforce. Observe that $$$O(n! \space n^2 \log n)$$$ passes.

Why logn

I stored the graph edges with an std::set, so insertion / checking was logn complexity

Yeah but that's kinda overkill

eh, not really. I just needed to be able to check if some edge (u, v) existed in the graph, and std::set was not only faster than an O(n) search but also easier to write. Also, unordered_set wasn't an option due to lack of hash..

You can use adjacency matrix here

ah shoot I see what you see about adj matrix and stuff

CodeI am solving with the exact logic you have mentioned but using fenwick tree but it isn't behaving like I want it to, Am I implementing the fenwick tree wrong?

Are you sure that fenwick tree supports range updates? I don't have good experience with them

E is way too easy for 475.

Maybe, but it was only for the 2nd time in my life I was able to solve an E. So I'm pretty happy regardless.

plz explain in details how to solve it using seg tree ?

E is just one google search away, literally the first search result

can anyone please explain E? Can't understand editorial.

Here's what I did:

First I realized that the approach simplified if I considered the sum of all subarrays ending at position $$$0$$$, then at position $$$1$$$, etc. For example, let's say that the array $$$a = 1, 2, 3, 2$$$

For each subarray of $$$a$$$, define the array $$$b$$$ to be all the $$$f(i, end)$$$ for all $$$i$$$. In the subarray $$$1, 2, 3$$$, then $$$b = 3, 2, 1$$$. There's a pattern in how each $$$b_i$$$ transforms to the next one:

$$$b(1, 2) = 2, 1, 0, 0$$$

$$$b(1, 2, 3) = 3, 2, 1, 0$$$

$$$b(1, 2, 3, 2) = 3, 2, 2, 1$$$

The pattern I noticed is that each added number $$$i$$$ increases all the values of $$$b$$$ between $$$i$$$ and the last occurance of $$$i$$$. It turns out that we don't actually need the array to be stored at all, and can just store and update the total sum of $$$b$$$.

My code here: https://atcoder.jp/contests/abc371/submissions/57767852