chokudai's blog

AtCoder Beginner Contest 260 Announcement
By chokudai, history, 2 years ago, In English

We will hold AtCoder Beginner Contest 260.

The point values will be 100-200-300-400-500-500-600-600.

  • Vote: I like it
  • +68
  • Vote: I do not like it

Comments Comments (21)
| Write comment?
»
2 years ago, # |
  Vote: I like it +53 Vote: I do not like it

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.

→ Reply
»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Atcoder BEGINNER contest they said...

E is nice though.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you explain your solution to E?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 4   Vote: I like it +4 Vote: I do not like it

      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

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For D, I used union-find. Each pile of cards has its own unique root.

      → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve $$$E$$$?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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

    → Reply
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Someone please explain the pigeonhole principle in problem F

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it +13 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thank you so much for your explanation. It helps a lot ^__^

      → Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Alternative solution for B, let's sort the index array instead of the data array.

sort(v.begin() + x + y, v.end(), [&](int l, int r) {
    return make_pair(-(a[l] + b[l]), l) < make_pair(-(a[r] + b[r]), r);
});
→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D, I am using this code but this is giving me TLE. I am really surprised by this behaviour. Its O(nlogn), how can it be TLE.

#include <bits/stdc++.h>
using namespace std;

void solve() {
  int n, m;
  cin >> n >> m;

  vector<int> arr(n);
  for (int i = 0; i < n; ++i)
    cin >> arr[i];

  vector<int> ans(n, -1);
  set<int> active;
  vector<int> group_map(n + 1, -1);
  vector<vector<int>> groups;
  int group_id = 0;

  for (int i = 0; i < n; ++i) {
    int curr = arr[i];
    auto it = upper_bound(active.begin(), active.end(), curr);

    if (it == active.end()) {
      groups.push_back({curr});
      group_map[curr] = group_id++;
    } else {
      int next = *it;
      active.erase(it);
      group_map[curr] = group_map[next];
      groups[group_map[curr]].push_back(curr);
    }

    if ((int)groups[group_map[curr]].size() == m) {
      for (int j : groups[group_map[curr]])
        ans[j - 1] = i + 1;
    } else {
      active.insert(curr);
    }
  }

  for (int i = 0; i < n; ++i)
    cout << ans[i] << " ";
  cout << endl;
}
→ Reply