We will hold AtCoder Beginner Contest 260.
- Contest URL: https://atcoder.jp/contests/abc260
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220717T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: physics0523, Nyaan, kyopro_friends, leaf1415
- Tester: nok0, Kodaman
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
For problem G I found some $$$O(Qlog^3N)$$$ solution then I thought simple $$$O(QN)$$$ would behave better than that so I ended up coding $$$O(QN)$$$ solution and it passed with $$$~1.5$$$ s. IDK if this was intended but that's how I will become yellow on Atcoder.
Same :)
Atcoder BEGINNER contest they said...
E is nice though.
Can you explain your solution to E?
Let's fix the left point of S (let it be L). The segment [L; R] is good if for every pair at least one of the points is inside this segment. We will use two pointers teq. to find for every L the minimum R, such that [L; R] is good.
Now, notice that for every R' >= R [L; R'] is also good, so we increase the number of good segments of lengths R — L + 1, (R + 1) — L + 1, ..., N — L + 1. Range increasing can be done using a differece array or a Segment Tree (or Fenwik Tree).
My submission
Was somewhat wiered for me, not able to solve B and C. B I dont know, maybe persistently typing something trivial wrong. With C I was not able to see the dp.
However, D was streight forward, and solved E after some thinking using a lazy segment tree just in time.
B was mainly implementation, although you had to be careful because the description wasn't too clear. I thought it meant that you had to sort student IDs after each round, but you only had to print a sorted student list at the end. With that in mind, all you needed was three sorted arrays for math, english, and combo scores.
I didn't get D, is it possible to do it in linear time?
Found my problem in B. I parsed input as a list of ab,ab,ab... instead of aaa...,bbbb.
D is simulation. To maintain the stacks I used a set<pair<int,int>>, where the first is current front card, and second is an index into an array of array of int, holding the list of cards in that stack.
Then, if a new card is placed on a stack, we put that card into the data array-array, and remove/insert the pair with the updated front card into the set.
For D, I used union-find. Each pile of cards has its own unique root.
For python users, when you see a problem (like today's D) that reads "setter clearly thinks just use cpp::std::map or set" what's your go-to replacement and why? I've tended to google 'pyrival sortedlist' and just use that out of habit.
In hindsight, the problem is a little DSU-y...? but I don't think that was intended, or if you did choose that, I'd love to hear what your recognition points are...?
sorted list from pyrival works well my sub using it
How to solve $$$E$$$?
First understand the text, it is actually a contigous subseq, so a subarray.
Then we iterate possible left ends of that sequence, and foreach one find the min and max length of a seq starting at that position. With that min/max we update the answer. I used a lazy segment tree for that but sweepline would also work.
How to find the min and max length foreach start position? I did put all ab-pairs into a set, assuming to use the smaller (a) value of the pairs. Then iterate the positions.
Foreach position I take the first element(s) out of the set, swap a and b, and insert that new pair into the set. Then the biggest value of all used ab-pairs is the last element in the set. So we know the smallest and biggest value of all ab used, and can determine the smallest possible seq-size. Also, from the current position of the leftmost element we can determine the longest possible seq.
see
The "Pigeonhole Principle" analysis in problem F is so fascinating! At first sight, I think the algorithm has a huge complexity, but if we count all the operations on the number of pairs of T-nodes, the total complexity is in fact bounded by $$$O(T^2)$$$.
Perhaps this is somehow similar to amortized analysis. Really a cool problem, thanks to the problem writers.
Now I wonder whether this slightly modified bfs algorithm should work or not.
For each T-node, we put its S-neighbors into a queue. For each S-node in the queue, we visit its T-neighbors and if some of the T-node has been visited for at least two times, then we have found a 4-cycle and stop, otherwise there is no 4-cycle. We repeat the above steps for every T-node. Is the complexity of this algorithm also bounded?
Someone please explain the pigeonhole principle in problem F
The given graph is bipartite.
Let $$$a, b \in S$$$ and $$$x, y \in T$$$. If we have $$$4$$$-cycle, then we must have $$$4$$$ edges $$$(a, x), (a, y), (b, x), (b, y)$$$. From every $$$a, b$$$ to every $$$x, y$$$.
Let's iterate over all $$$a \in S$$$.
For each $$$a$$$ we iterate over all possible pairs $$$(x, y)$$$, such that we have edges $$$(a, x)$$$ and $$$(a, y)$$$. Just simple two nested for-loops.
We have $$$3000 \times 3000 = 9 \cdot 10^6$$$ possible different pairs $$$(x, y)$$$.
If we ever encounter the same pair $$$(x, y)$$$ twice, then we have two vertices $$$a$$$ and $$$b$$$ and both these vertices have edges to $$$x$$$ and to $$$y$$$ (found $$$4$$$-cycle).
Pigeonhole principle here is that we don't reach the complexity $$$O(M^2)$$$ or something like this. No matter how many pigeons (pairs $$$(x, y)$$$ in all nested loops) we have, there is only $$$9$$$ million different pairs $$$(x,y)$$$ (cages) which we can hit at most once (again, if some pair hit twice, then we have found $$$4$$$-cycle and can stop). So in total these nested loops make only $$$O(T^2)$$$ operations in the worst case (no $$$4$$$-cycles).
Thank you so much for your explanation. It helps a lot ^__^
Concerning problem E — At Least One, I'm having problems checking if a specific segment satisfies the conditions. My solution differs from the editorial and I can't get it to work (probably because it's incorrect).
Can anyone confirm (or disprove) the below statement? If it is correct then the problem is in my implementation.
A segment $$$[L,R]$$$ satisfies the conditions if and only if
$$$\displaystyle L \leq \min_{i=1}^N B_i$$$ (1), $$$\displaystyle R\geq \max_{i=1}^N A_i$$$ (2), $$$\displaystyle R\geq \max_{A_i < L} B_i$$$ (3) (basically I am checking that there is no pair $$$A_j < B_j$$$ such that $$$A_j<B_j<L$$$ (1) or $$$A_j<L\leq R < B_j$$$ (3) or $$$R<A_j<B_j$$$ (2), which I believe are all the bad cases).
Note: I fail 4/12 cases (1 of which is named "04_corner_02" so I am afraid I am missing something).
Alternative solution for B, let's sort the index array instead of the data array.