Hidden Cell Problem Codechef Solution

by

Hidden Cell Problem Solution Code: HIDECELL

There is an N×NN×N matrix. Let (i,j)(i,j) denote the cell in the ii-th row and the jj-th column, where the rows are numbered 0,1,…,N−10,1,…,N−1 from top to bottom and the columns are numbered 0,1,…N−10,1,…N−1 from left to right. There is a hidden cell (a,b)(a,b). It is known that this cell doesn’t lie on the boundary of the matrix. That is, min(a,b)≥1min(a,b)≥1 and max(a,b)<N−1max(a,b)<N−1.

Your task is to recover the hidden cell. You can ask queries, in which you give the judge a matrix MM of size N×NN×N, consisting of zeroes and ones. Let’s call a cell (i,j)(i,j) valid if (i,j)=(a,b)(i,j)=(a,b) or Mi,j=1Mi,j=1. The judge replies whether there exists a path from (0,0)(0,0) to (N−1,N−1)(N−1,N−1) consisting of only valid cells, moving only down and right.

Formally, it tells whether there exits a sequence of 2N−12N−1 cells (0=u0,0=v0),(u1,v1),…,(N−1=u2N−2,N−1=v2N−2)(0=u0,0=v0),(u1,v1),…,(N−1=u2N−2,N−1=v2N−2), such that (ui,vi)(ui,vi) is a valid cell for all ii and either (ui+1=ui,vi+1=vi+1)(ui+1=ui,vi+1=vi+1) or (ui+1=ui+1,vi+1=vi)(ui+1=ui+1,vi+1=vi).

The score of your submission is a function of the number of queries asked. Please refer to the scoring section for more details.

Note that the grader is not adaptive, which means that the hidden cell is fixed in the beginning and won’t change according to the queries you ask.

Input

  • First, you should read a single integer TT, the number of test cases.
  • For each test case, first read the value of NN.
  • To make a query, you should first print ? on a new line. Then you should print NN lines each containing a string of NN characters denoting the matrix MM.
  • If the query format is incorrect (i.e. if the matrix doesn’t have dimensions N×NN×N or if some character in the matrix is not 00 or 11), or if you have asked more than 120120 queries, the judge prints -1, and exits with a wrong answer verdict. In this case, you must also terminate your program.
  • Once you know the hidden cell, print a character ! on a new line. In the next line, print two space-separated integers aa and bb, the row and column numbers of the hidden cell respectively.
  • If your answer is incorrect, the judge prints -1 and exits with a Wrong Answer verdict. In this case, you must terminate your program as well. Otherwise, the judge prints 1, and you should move to the next test case (if any).

Note that whenever the judge prints −1, you should immediately terminate your program to receive a Wrong Answer verdict; otherwise, you may receive any verdict. Don’t forget to flush the output after printing each line!

Test Data and Scoring

Each test file has exactly 5050 test cases all with N=50N=50.

Let QQ be the maximum number of queries asked by you over all the test cases of all the test files.

  • If Q>120Q>120, you get 00 points.
  • If 61≤Q≤12061≤Q≤120, you get 99 points.
  • If 51≤Q≤6051≤Q≤60, you get 2424 points.
  • If Q≤50Q≤50, you get 54+⌊46×(50−max(Q,14))36⌋54+⌊46×(50−max(Q,14))36⌋ points, where ⌊x⌋⌊x⌋ denotes the largest integer ≤x≤x. In particular, you get 5454 points if Q=50Q=50 and 100100 points if Q≤14Q≤14.

Interaction Example

You                     Grader
                        3           # 3 test cases
                        4           # N = 4
?
1100
0100
0001
1111
                        1           # The judge tells that there is
                                    # a valid path.
!
2 1

                        1           # Correct answer! 

                        4           # Next test case, N = 4

?
1000
0000
0010
0001
                        0           # There doesn't exist a path
!
2 2
                        -1          # Incorrect output! Judge exits
You should also
terminate here
without reading
the next test case

Explanation

Please note that a small value of T,NT,N is used for explanation purposes. In all the actual tests, T=50,N=50T=50,N=50.

In the first example, (2,1)(2,1) is the hidden cell. You ask the query:

1100
0100
0001
1111

The path (0,0)→(0,1)→(1,1)→(2,1)→(3,1)→(3,2)→(3,3)(0,0)→(0,1)→(1,1)→(2,1)→(3,1)→(3,2)→(3,3) consists of only valid cells and the judge replies with 11.

In the second test case, the hidden cell is (1,1)(1,1). When you ask the query

1000
0000
0010
0001

Only all the diagonal cells are valid. There is no path from (0,0)(0,0) to (3,3)(3,3) passing only through valid cells, so the judge replies with 00.

Program:

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(a) (a).begin(), (a).end()
#define int long long

int n, k;

const int N = 5e4 + 5;

int sz[N];
vector<int> adj[N];
vector<int> dp[N];

void dfs (int v, int p) {
    sz[v] = 1;
    for (auto &i: adj[v]) {
        if (i != p)
            dfs(i, v), sz[v] += sz[i];
    }
    dp[v].resize(k + 1, (int) 1e18);
    dp[v][0] = 0;
    for (auto &i: adj[v]) {
        if (i != p) {
            auto ndp = dp[v];
            for (int j = 0; j <= k; ++j) {
                for (int l = 0; l <= j; ++l)
                    ndp[j] = min(ndp[j], dp[v][l] + dp[i][j - l]);
            } 
            dp[v] = ndp;
        }
    }
    if (sz[v] <= k)
        dp[v][sz[v]] = 1;
}

int32_t main() {
    cin.tie(0); ios_base::sync_with_stdio(false);

    int t;
    cin >> t;
    while(t--) {
        cin >> n >> k;
        for (int i = 1; i <= n; ++i)
            sz[i] = 0, adj[i].clear(), dp[i].clear();
        for (int i = 2; i <= n; i++) {
            int x;
            cin >> x;
            adj[i].push_back(x);
            adj[x].push_back(i);
        }
        dfs(1, 1);
        auto a = dp[1];
        auto b = a;
        int ans = 1e18;
        for (int go = 0; go <= k; ++go) {
            ans = min(ans, b[k] + go);
            for (int s = k; s >= 1; --s) {
                for (int s2 = 1; s2 < s; ++s2) 
                    b[s] = min(b[s], a[s2] + b[s - s2]);
            }
        }
        cout << ans << '\n';
    }
}

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment

17 + eight =