Submission #1152433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152433		jmuzhen	Zagrade (COI20_zagrade)	C++20	0 / 100	334 ms	9868 KiB

zagrade

// https://oj.uz/problem/view/COI20_zagrade
// try to grab 'entire sequence is valid' subtasks

/*  observations for q2.
 *  u can very easily get the first 2 subtasks, because notice that
 *  only querying on an even length range can give information. so we just query on
 *  all (N^2/4) even length ranges and then piece together the answer.
 *
 *  but how to piece together the answer once we have the query results?
 *  if answer is yes, then it's simple, assign () to the endpoints.
 *  but if no, then we need to look at where the issue is.
 *  but how to check?
 *  I think if u start from the middle of the string and see the result for that, it's either
 *  yes (which is easy) or no. if no ,then it can be )( or (( or )). how to determine which one?
 *  let's say (()()), it is valid. that should be easy to check.
 *  but what if it is (())() ? also valid.
 *  but what if it is ())(() ? not valid. but then we know () is valid and () is valid. so we can tell that
 *  the middle is )(. but wait, what observation can we derive here? what if it was )()(() ? or ))(()( ?
 *  well, wait wait wait. we have queried every segment of length 2, this means we have queried [1,2],[2,3],...
 *  so for example let's take the example just now, ))(()(. we know [1,2],[2,3],[3,4] all invalid. only [4,5] is valid.
 *  [5,6] is invalid as well. so let's consider 1. it can be ( or ), no info gained yet. but let's consider 2. if it was (
 *  then 3 must be (. then 4 must be ( . this would continue forever if we didn't have any () pair confirmed. but we do. so when
 *  we see 4, we see it contradicts. so , our original assumption was wrong and 2 must be ). similarly we can work back...
 *  wait! working backwards!
 *  so whenever we see a pair () we can work backwards, based on the results of our queries, to find the correct answers for the characters
 *  before it.
 *  so say there we knew [4,5] was (),
 *  . wait . i made a mistake. 4 must be (, not ). i have corrected it above.
 *  this means there wasn't actually a contradiction if we assumed 2 was (. for example:
 *  )((()) was a possible way that fit all my assumptions, yet is not the answer.
 *  so how to check if it's correct overall or not?
 *  to remind myself, the correct answer is ))(()(.
 *  well, we knew that [3,6] was not a correct pair. can we try to use that? [3,6] is either (( [correct answer] or
 *  )) or )(. but if it was )) then we have no more )) and so sequence has to be (()()). which is valid. but this doesn't
 *  generalise to large sequences, because we likely always have ( and ) left.
 *  if it was )(, then ...
 *  wait, this is getting too complicated. i don't think breaking it into such branches of logic helps here. to summarize, i think
 *  working backwards is a part of the intended solution. but how? we need to be prepared for a difficult case where we have few ()s to '
 *  work on. our solution probably works only for the case where the sequence is valid. because then we are definitely gonna have
 *  a lot of ()s to work on.
 *
 *  that seems to be the easier way to proceed - instead of solving it for small N first, let's try to solve it for the valid case
 *  first. but do we really have a lot of ()s to work on? what if they were flipped like, ()()() ? oh right, in that case we still have 3
 *  valid ones. i think this is quite easy to prove, because of the addition properties of valid sequences as stated in the qn.
 *  how about : first query every 2 adjacent pairs, so [1,2],[3,4], [5,6]. then, discard the ones that return true.
 *  that effectively splits the sequence into many segments. notice how in the extreme case, we get only 2 segments:
 *  ((())) -> (( ; )). but then we can break this down again. but how? i don't think we can break this down more.
 *  what if instead of grouping like that, we query from the center each time? that way we can keep decomposing the problem right?
 *  so like ((())) -> solved in first pass because every bracket pair matches. let's consider extreme case:
 *  ()()(). -> ) ( -> query 2..5 -> solved.
 *  i *think* that may work! in fact, let's consider the information theory aspect. in the AC solution every query must give us 1
 *  information. since in the valid subtask we already have a significant piece of info, i think that gives us at least 2x the info
 *  which would suggest we can solve it in N/2 queries.
 *  let's consider more extreme cases.
 *  ()()()() . -> ))(( -> no -> no. i think that works. let's go ahead with the implementation.
 *
 *  so we need some sort of recursive function that can keep decomposing the string.
 *  say we start with just one full string, s. then we query
 *  [1, n], [2,n-1], ... , ...
 *  every time query is true, we just give () to the endpoints in the answer.
 *  but if query is false, then we need to keep these 2 points. we will need to somehow give these to the next recursive function.
 *  so say n=8, string is ()()()(). then we have
 *  [2, 7]: )( - false. [4,5]: )( - false. then we need to deal with these two.
 *  say we sort the subarray of all the indices who need merging. then: [2,4,5,7]. we can then take [4,5] and [2,7] and go again.
 *  but special case: [4,5] is adjacent so we can just mark it as )(. why? otherwise, they would be paired with someone else, i think,
 *  and won't appear here. wait, is this true? i'm doubtful. you know what, let's assume this is true for a valid sequence, which
 *  _feels_ correct. then the problem is reduced as we only have [2, 7] left. but is this always going to happen? unsure. i think it is.
 *  because every time, for the center pair, if it's false then we give )(, if it's true then we give (), sooner or later it's going to be reduced.
 *  ehhh, let's try this first. i have no idea if it works.
 * so how does the dp work? say we give it an vector of indices. then it outputs, for each index, if the char is true or false. i think that works.
 * so input: vector<int>, output: vector<char>, then after we get the output from the child function, we update it in the original vector accordingly.
 * isn't that O(N^2)? well we can worry about that later, first let's check if this is correct.
 */
#include <bits/stdc++.h>
using namespace std;

int n, q;

map<pair<int, int>, int> query_memo; // optimisation

// helpers to query & output
inline int query(int i, int j) {
  if (query_memo[{i,j}]) {
    return query_memo[{i, j}];
  }
  cout << "? " << i << " " << j << endl;
  int r; cin >> r;
  return query_memo[{i,j}] = r;
}
inline int query(int i, int j, const vector<int>& input) {
  return query(input[i], input[j]);
}

inline void output(vector<short>&s) {
  cout << "! ";
  for (int i = 1; i <= n; i++) {
    cout << (s[i] == 0 ? '(' : ')');
  }
  cout << endl;
}

inline void output(vector<char>&s) {
  cout << "! ";
  for (int i = 1; i <= n; i++) {
    cout << s[i];
  }
  cout << endl;
}

// dfs recursively
void dfs(int sz, const vector<int>& input, vector<char>& output) {
  vector<int> next_it; // elements for next iteration
  // add one element for indexing to work properly.
  next_it.push_back(-1e9);

  for (int i = 1; i <= sz/2; i++) {
    int j = sz+1-i;
    int q = query(i,j, input);
    if (q == 1) {
      output[i] = '(';
      output[j] = ')';
    }
    else {
      if (i == sz/2) {
        // special case:
        output[i] = ')';
        output[j] = '(';
      }
      else {
        next_it.push_back(i);
        next_it.push_back(j);
      }
    }
  }

    if (next_it.size() == 1) {
      return;
    }

    // sort
    sort(next_it.begin(), next_it.end());
    vector<char> new_output(next_it.size());

    dfs(next_it.size()-1, next_it, new_output);

    // assign output
    for (int j = 1; j <= sz; j++) {
      if (new_output[j]) {
        output[next_it[j]] = new_output[j];
      }
    }
}

int main() {
    cin >> n >> q;
    vector<int> in(n+1);
    for (int i = 1; i <= n; i++) in[i] = i;
    vector<char> out(n+1);


    dfs(n, in, out);

    output(out);
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 7
• Subtask 3: 0 / 57
• Subtask 4: 0 / 22