No communications while contest

You shouldn't use set because it introduces logarithmic complexity; you might consider using bitset or something similar instead.

same here

same here

deduced the logic of D in like less than 5 minutes but was stuck on C for around 25 minutes but couldnt think of anything

Do a BFS solution, starting from the mask 0. To get the next masks for each mask, iterate to find each bit that are still turned off of the mask, and turn it on. If it is a safe state to reach, and also hasn't been visited, then it can be pushed to the queue.

can you share your code?

don't know if it is intended, but I did it this way. submission

Merging nodes, with each node having prefix, suffix and mid of the highest frequency letter and the letter

Use a segment tree (with each node representing one substring) to collect the following information

1. the length of that substring
2. the longest prefix with the same character as the first one in that substring
3. the longest suffix with the same character as the last one in that substring
4. the function value in that substring (i.e. longest substring in that substring with same letter)
5. what is the first letter
6. what is the last letter

it's kind of like CSES 1190 and CSES 3226 combined, but with strings instead of integer additions.

submission to F: here

I solve it： Code:

 #include <bits/stdc++.h>
          using namespace std;
          struct Node 
		  {
              char l_char, r_char;
              int l_len, r_len;
              int max_len;
              int len;
              Node() = default;
              explicit Node(char c) 
			  {
                  l_char = r_char = c;
                  l_len = r_len = 1;
                  max_len = 1;
                  len = 1;
              }
          };
          Node merge(const Node& left, const Node& right) 
		  {
              Node res;
              res.len = left.len + right.len;
              res.l_char = left.l_char;
              res.r_char = right.r_char;
              // left consecutive
              res.l_len = left.l_len;
              if (left.l_len == left.len && left.r_char == right.l_char) 
			  {
                  res.l_len += right.l_len;
              }
              // right consecutive
              res.r_len = right.r_len;
              if (right.r_len == right.len && left.r_char == right.l_char) 
			  {
                  res.r_len += left.r_len;
              }
              res.max_len = max(left.max_len, right.max_len);
              if (left.r_char == right.l_char) {
                  res.max_len = max(res.max_len, left.r_len + right.l_len);
              }
              return res;
          }
          void build(vector<Node>& tree, int idx, int l, int r, const string& s) 
		  {
          	
              if (l == r)
			   {
                  tree[idx] = Node(s[l]);
                  return;
              }
              int mid = (l + r) / 2;
              int left_child = 2*idx+1;
              int right_child = 2*idx+2;
              build(tree, left_child, l, mid, s);
              build(tree, right_child, mid+1, r, s);
              tree[idx] = merge(tree[left_child], tree[right_child]);
          }
          void update(vector<Node>& tree, int idx, int l, int r, int pos, char c) 
		  {
              if (l == r) 
			  {
                  tree[idx] = Node(c);
                  return;
              }
              int mid = (l + r) / 2;
              int left_child = 2*idx+1;
              int right_child = 2*idx+2;
              if (pos <= mid) 
			  {
                  update(tree, left_child, l, mid, pos, c);
              } 
			  else 
			  {
                  update(tree, right_child, mid+1, r, pos, c);
              }
              tree[idx] = merge(tree[left_child], tree[right_child]);
          }
          Node query(vector<Node>& tree, int idx, int l, int r, int ql, int qr) 
		  {
              if (ql <= l && r <= qr) 
			  {
                  return tree[idx];
              }
              int mid = (l + r) / 2;
              int left_child = 2*idx+1;
              int right_child = 2*idx+2;
              if (qr <= mid) 
			  {
                  return query(tree, left_child, l, mid, ql, qr);
              } 
			  else if (ql > mid) 
			  {
                  return query(tree, right_child, mid+1, r, ql, qr);
              } 
			  else 
			  {
                  Node left_node = query(tree, left_child, l, mid, ql, mid);
                  Node right_node = query(tree, right_child, mid+1, r, mid+1, qr);
                  return merge(left_node, right_node);
              }
          }
          int main() {
              ios::sync_with_stdio(false);
              cin.tie(0);
              int n, q;
              cin >> n >> q;
              string s;
              cin >> s;
              vector<Node> tree(4 * n);
              build(tree, 0, 0, n-1, s);
              while (q--) 
			  {
                  int type;
                  cin >> type;
                  if (type == 1)
				   {
                      int i;
                      char c;
                      cin >> i >> c;
                      i--;
                      update(tree, 0, 0, n-1, i, c);
                  } 
				  else 
				  {
                      int l, r;
                      cin >> l >> r;
                      l--; r--;
                      Node res = query(tree, 0, 0, n-1, l, r);
                      cout << res.max_len << '\n';
                  }
              }
              return 0;
          }

just to bulid a tree and do something

I did something using a lazy segtree representing an array where a[i] is the streak of consecutive same characters ending at index I, and you just query the max element with the range for the answer.

I did the following: Use dp to calculate the optimal solution for N<=1000. I guessed you could get to <=1000 with just 1 index. Try all M possible indices and pick the best. But WA in 1 case.

I have 38 ACs and 2 WAs

I sorted the exchange methods by $$$\frac{A}{B}$$$ from small to big, and then use each method in order, and use one as much as possible (until it can't be used) and then move on. I don't know why WA in 2 cases

Same as me, I tried to find the cycle and were very pleased when 39/40 passed and it is still grey, and the last case just turn yellow. Kill me !

Yes, N <= 1000 -> N <= 100000 with observation that we have <= 300 useful pairs and it passed

Can anybody prove that it is optimal to keep using one operation when $$$n$$$ is large enough, say, 100000?

Rather mysterious.

I think when you violently DP, you should sort the items by the value of the $$$a_i$$$ from largest to smallest to ensure that the order in which you choose items is optimal.

Sort the array by $$$A_i - B_i$$$; If some $$$A_i - B_i$$$ are equal, sort them by $$$A_i$$$, from small to large.

Did you find out what test case you are failing?

I used basically the same approach as yours. idk either

You have to maximize the minimum of coins he had had on the path instead of the coins he lastly have.

So, we need to maximize the minimum, one will use what?

your code fails this following test case:

23 6
9 7
1 1
5 3
16 4
21 7
12 5

Correct output: 11, your code's output (incorrect): 0

I think the reason why it fails is due to the incorrect calculation of the number of times the operation will be applied and the value of variable ct after applying a number of operations.

Here is my in-contest submission: https://atcoder.jp/contests/abc415/submissions/67755510

This test cuts solutions where N (size of dp array) is too small

i have tried this but it is giving TLE and MLE both

i just don't understand if making segment tree for each character and simply doing maximum subarray sum in a range is not allowed then why the Time Limit of question is 4 sec

wrong link bro

Can you explain D?

Sort $$$A_i - B_i$$$ in descending order instead of ascending

Also, please carefully check the code for calculating the times you can exchange