We will hold AtCoder Beginner Contest 308.
- Contest URL: https://atcoder.jp/contests/abc308
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230701T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: yuto1115, nok0, evima, Nyaan
- Tester: Nyaan, physics0523
- Rated range: ~ 1999
- The point values will be 100 — 200 — 300 — 400 — 475 — 500 — 600 — 625.
We are looking forward to your participation!
is this account legit? maroonrk
yes! Mike proposed this user name.
Is this contest rated
why do you keep replacing a stupid question with another stupid question?
Problem were relatively easy this time especially F and G. Nice round.
Can C be solved by using modulo inverse?
C is simple sorting ,why do you need modular inverse?
You can use trie to do G right?
just simple set will do the trick.
It can be done with a multiset.I'm not sure how to do it with trie.
No, using multiset.
Yes, I solved it with divide and conquer + trie.
At first I completely misunderstood the problem and started thinking in wrong direction, but still it is interesting approach I think.
Curious to know your approach. Can you explain it?
He probably used segment tree. You see, the problem would be trivial if the "remove" query was a "roll-back" query. So the idea is just the same as dynamic connectivity. The complexity is $$$O(N * log ^ 2 N)$$$, which is not too bad considering the time constraint is $$$3$$$ seconds
Ok explain then, my tiny brain can't comprehend dynamic connectivity
We notice, that writing $$$x$$$ on the blackboard and erasing $$$x$$$ from the blackboard means that $$$x$$$ is spanned on some segment of queries, so we can use similar trick that we use in offline dynamic connectivity.
With a segment tree add $$$x$$$ on some range and when you traverse the segment tree recursively you want to do following:
All of this can be done in $$$O(N*log(N)*log(x))$$$
I have a better approach.
Make each node of the trie, store the answer for the suffixes of all the numbers that are in its subset (sub-tree or sub-trie, whatever). The idea is something similar to the merge operations we do in segment trees. Every time we insert or delete a number, we update the answer for all the nodes that are affected by its insertion or deletion. This works in O(NlogN). Here is a link to my submission: link
PS: But, it feels really silly to use a trie for this problem after reading the editorial.
"PS: But, it feels really silly to use a trie for this problem after reading the editorial."
Don't worry, it might be useful for other hard problems in future.
I did using a set, Code
The main idea is that it suffices to check every adjacent elements in a sorted array to get the minimum Xor
Yes, I solved it with dp on trie, using the fact that when we add/remove a number, at most 30 nodes need to recompute their dp value. Here is the code :)
Can you elaborate a bit about dp state and you idea?
The problem asks to find two paths to leaves of the trie with minimum xor value. We compute the dp value for each node, assuming that both paths go through it. Answer is the value of the root.
If a node has two possible paths when adding a 0 (or a 1), it’s never optimal to choose one path with 0 and the other one with 1.
We are left with the case when there is only one path with 0 and one with 1. Given that each path the only one in its subtree, we can mantain the value of the number it represents and use it to compute the xor of the two possible paths (we can update this value when we add/remove numbers).
Refer to my code for more details :)
Got it. Thanks!
Hints for E,F,G please :)
Editorial is released.
Can anyone explain the DP soln for F?
I did Greedy + bs
what you were looking for with bs? How do you retrive the max discount availble for a given price? I am doing lower bound on coupons looking for the closest one (with threshold just below the price and max discount) but its not working
https://atcoder.jp/contests/abc308/submissions/43149319
I am so stupid I was doing binary search on the coupons instead of prices... thx for your help
you will improve , keep grinding
My bad, I meant E, didn't notice it until now and was wondering how did bs came into play T-T
well the dp function will be like this dp(pos,current subsequence size, mask) — size : dp[200000][3][8] , although I didn't do dp during contest ; did brute force
Can you please help me out with the recursive function.
This is my submission from the contest. I know this is wrong since I am not calculating the dp till the i'th index , but I just couldn't find a way to do it properly.
Lmao, I finished F like 10 minutes after the contest was over and F took me less time than any of C-E.
.
In the editorial of G, shouldn't it say "more significant bits" instead of "less significant bits"
Why E requires DP, but F only requires greedy?
I did F : Greedy + Bs and doing dp in E is overkill , E is just brute force
https://atcoder.jp/contests/abc308/submissions/43142095 can anyone tell me whats problem here 4/39 case are failing i am not able to figure out problem wasted a hell lot of time in this done E late but haven't solved D
check line 10.
Also dp is redundant, It does nothing here plus format your code. It's a headache to read.
Can someone please tell why I am getting runtime error on problem D. I have used simple DFS with dp, some pass but mostly give me Runtime error. https://atcoder.jp/contests/abc308/submissions/43178624
you are visiting the same nodes again and again
it will give run time error for this case
2 6
sekunf
nukesn
first you will start at (1,1) you will reach (2,5) from there one dfs will be to (2,6) and another to (1,5)
consider (1,5), you will again go to (1,1) but at(1,1) dp[1][1] will still be equal to -1 as the dfs from (1,1) is not completed fully so you will again start dfs from (1,1) and it goes on .