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
I 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