Contents
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 prints1
, 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
- Maximum Product Difference Between Two Pairs
- Cyclically Rotating a Grid
- Number of Wonderful Substrings
- Count Ways to Build Rooms in an Ant Colony
Biweekly Contest 55
- Remove One Element to Make the Array Strictly Increasing
- Remove All Occurrences of a Substring
- Maximum Alternating Subsequence Sum
- Design Movie Rental System
June Long Challenge 2021 Solutions
- Maximum Frequent Subarray Sum solution codechef
- Dual Distance solution codechef
- Optimal Xor Set solution codechef
- Minimum Subtree Cover solution codechef
- Minimum Dual Area solution codechef
- Bitwise Tuples solution codechef
- Shortest Route solution codechef
- Bella ciao solution codechef
- Summer Heat solution codechef
March Long Challenge 2021 Solutions
- An Interesting Sequence ISS SOLUTION
- Tree House THOUSES SOLUTION
- Valid Paths VPATH SOLUTION
- Modular Equation MODEQ SOLUTION
- Tic Tac Toe TCTCTOE SOLUTION
- Xor Equality XOREQUAL SOLUTION
- Golf LKDNGOLF SOLUTION
- Solubility SOLBLTY SOLUTION
April Long Challenge 2021 Solutions
- Chef and Dice SDICE Solution
- Worthy Matrix KAVGMAT Solution
- Binary String MEX MEXSTR Solution
- Boolean Game BOOLGAME Solution
- Tree Permutations TREEPERM Solution
- Destroy the EMP Chip CHAOSEMP Solution
- Chef and Pair Flips PAIRFLIP Solution
- String Power STRPOW Solution
- Brahma and Shiva SHRINES Solution
- Water Sort Puzzle (Challenge) WTRSORT Solution
- World Record BOLT Solution
- Strong Language SSCRIPT Solution
- Valid Pair SOCKS1 Solution
Codechef Long Challenge Solutions
February Long Challenge 2021
- 1. Frog Sort Solution Codechef
- 2. Chef and Meetings Solution Codechef
- 3. Maximise Function Solution Codechef
- 4. Highest Divisor Solution Codechef
- 5. Cut the Cake Challenge Solution Codechef
- 6. Dream and the Multiverse Solution Codechef
- 7. Cell Shell Solution Codechef
- 8. Multiple Games Solution Codechef
- 9. Another Tree with Number Theory Solution Codechef
- 10. XOR Sums Solution Codechef
- 11. Prime Game Solution CodeChef
- 12. Team Name Solution Codechef
January Long Challenge 2021
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef
November Challenge 2020 SOLUTION CodeChef
- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID
October Lunchtime 2020 CodeChef SOLUTIONS
- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP
Related :
- A. Shandom Ruffle SOLUTION
- B. Pear TreaP SOLUTION
- C. Sneetches and Speeches 3 SOLUTION
- D. The Grim Treaper SOLUTION
- Y. Sneetches and Speeches 1 SOLUTION
- Z. Trick or Treap SOLUTION
- A. Floor Number SOLUTION CODE FORCES
- B. Symmetric Matrix SOLUTION CODE FORCES
- C. Increase and Copy SOLUTION CODE FORCES
- D. Non-zero Segments SOLUTION CODE FORCES
- E. Rock, Paper, Scissors SOLUTION CODE FORCES
- F. Number of Subsequences SOLUTION CODE FORCES
Related :
- Chef and Easy Queries SOLUTIONS CHEFEZQ
- Covid Run SOLUTIONS CVDRUN OCTOBER CHALLENGE
- Positive AND SOLUTIONS POSAND
- Replace for X SOLUTIONS REPLESX
- Village Road Network SOLUTIONS VILLNET
- Random Knapsack SOLUTIONS RANDKNAP
- D-Dimensional MST SOLUTIONS DDIMMST
- Compress all Subsegments SOLUTIONS SEGCOMPR
- Adding Squares SOLUTIONS ADDSQURE
- Inversions SOLUTIONS INVSMOD2 OCOTBER CHALLENGE
- Rooted Minimum Spanning Tree SOLUTIONS ROOTMST