NBOTS - Editorial

editorial
, , , , ,
1

Practice
Div-2 Contest
Div-1 Contest

Author & Editorialist: Alei Reyes
Tester: Danya Smelskiy

DIFFICULTY:

TIE-BREAK.

PROBLEM:

We are given a matrix of N rows and N columns, the cell at position (i,j) has a strength T_{i,j}. Find the minimum number of laser shots to destroy all cells. The laser can be fired from the left or right of each row, or from the top or bottom of each column. The laser destroys all the cells in its way with a total strenght less than ore equal to F.

EXPLANATION:

The minimum number of shots to destroy one row of N cells using only horizontal shots can be calculated using the following dynamic programming

f[L][R] = minimum number of shots to destroy cells between L and R.

The recurrence relation is of the form f[L][R]=min(1+f[L'][R],1+F[L][R']) where L' and R' are the respective new indices if the laser is shot from the left or right respectively.

The following greedy score some points: While the matrix is not empty, find the row or column that requires the minimum number of shots (using the previous dp) and destroy it.

Note that after removing one row or column the dp must be recalculated. Since the dp is cuadratic, some heuristics to approximate the value can be used. The idea of only partially remove a preffix or suffix of the rows can also be incorporated.

Mihai Bunget: Random search

Mihai Bunget was the first one to AC the tie-break, moreover his solution is very simple and scores at least 50 points.

The idea is to flip a coin to chose a direction, and shot the laser only on the rows (or columns) from which at least X cells are destroyed, initially we can set X=512 . If no such file exists, we decrease X, rinse and repeat.

The state of the board can be represented as horizontal and vertical segments. Each segment contains only non-destroyed cells. When a laser is shot, the segments shrink.

The previous algorithm runs very fast, since we have 10s to solve the problem, we can keep it repeating many times searching for the best solution.

Lewin Gan: Score function heuristic

For each possible laser shot, let’s calculate two parameters:

  • s, the total thickness sum of the destroyed cells
  • c, the number of destroyed cells.

Which of the 4 \cdot n possible shots should we use?
Lewin designed the following score function to meassure the goodness of each each shot:

score(s,c) = \left\{ \begin{array}{ll} \sqrt c \cdot (4 \cdot F -s) & \quad s \leq f/2 \\ \sqrt c \cdot (F -s) & \quad s \gt f/2 \\ \end{array} \right.

The idea of the score function is to give weight to the number of destroyed cells, and penalize the shots with a small sum.

The laser shot with minimum score is fired, the matrix is updated and the process is repeated until all cells are destroyed.

I don’t know exactly how the function was designed, but we can try different score functions and choose the one that works better in practice. Also some machine learning approaches can help.

Hardifying problems

NBOTS is the 2D version of my BRKBKS. Just like in alchemy a cakewalk was converted into an unsolvable problem! Initially I included gravity i.e once the cells are destroyed they fall by gravity, and also there was the operation of rotation (after rotating the cells fall by gravity). However our admin told me that those operations could make it more unpredictable.

7 Likes
3

https://www.codechef.com/viewsolution/32855216

Can anyone point out why am I getting NZEC error in this problem?
@vijju123
@alei
@carre
@smelskiy

4

use

try:
your code
except:
pass

5

It was of no use.

6

then u might be accessing invalid memory location
check code once

7

What does TIE-BREAK stands for?

1 Like
8

Tie breaker is a score based question, once you read the question, u can see at the bottom of the question how the scoring works for that question.
If u get a ac verdict, the points you get out of 100 will be ((your score /highest score for that question achieved)*100),so , since scores generally are in thousands,this question is meant to break ties in the top rankings as not everyone gets the same highest score and the question will be difficult enough.

2 Likes
9

i thought the most optimum solution would be if we can somehow manage to decrease the wastage of our shot fires. so i calculated for each possibility the minimum wastage and fire accordingly. too bad my solution was too slow :relieved:. Hit me up if you wanna see my approach anyway.

1 Like
10

i’m curious, did you write your own solution to this problem?

11

yes but it gave tle which was expected since i was checking for each possible shot.

12

I wrote a basic solution to make sure the checker works correctly. It is based in the dp explained in the first parragraphs. I didn’t optimized it, so it should get a low score.

13

Hi Alei, my question was to @anon74059678

14

I used greedy (choosing the row/column which requires min lazers at the present scenario).
It gave me only 7 points.

15

I didn’t solve the problem so I don’t have it in my mind and didn’t try to follow your code, just run your code with random input and this line throw an error:

nlists[(number-n-1)][n-1-i] = 0

I think you may have an out of bounds there

16

yeah i wrote the same thought this was a 5 second problem so it may not show tle but my code did lol

17

My best approach was to track the targetted sum of all 2048 lasers… and then fire which has maximum sum… that’s it…(it didn’t throw TLE because i updated only those lasers which have to be really updated) I scored 66 in around 0.5secs .I would have thought more over it but I hit 100 submissions :joy:…

18

Where could I find the the tester’s or setter’s code ?

20

challenge questions are not provided with editorials so you can’t get testers or setters solution.You can only go through others solutions.

21

Is intended to have editorials for the challenge problem, however for some notorious coincidences sometimes (often?) we end up without one.

Basic solution dp + greedy 
  #include<bits/stdc++.h>
  using namespace std;
  typedef long long int uli;
  const int mx=520;
  int t[mx][mx];
  int n=512;
  int F=512;

  int lft[mx],rht[mx],f[mx][mx];

  string solve(vector<int>a,string w){
    int j=0,p=F;
    for(int i=0;i<n;i++){
      while(j<n && p>=a[j]){
        p-=a[j];
        j++;
      }
      rht[i]=j-i;
      p+=a[i];
    }
    j=n-1,p=F;
    for(int i=n-1;i>=0;i--){
      while(j>=0 && p>=a[j]){
        p-=a[j];
        --j;
      }
      lft[i]=i-j;
      p+=a[i];
    }
    for(int i=0;i<n;i++)f[i][i]=1;
    for(int l=2;l<=n;l++){
      for(int i=0;i+l<=n;i++){
        j=i+l-1;
        f[i][j]=1e9;
        if(i+rht[i]<=j)f[i][j]=min(f[i][j],f[i+rht[i]][j]+1);
        else f[i][j]=1;

        if(j-lft[j]>=i)f[i][j]=min(f[i][j],f[i][j-lft[j]]+1);
        else f[i][j]=1;
      }
    }
    int l=0,r=n-1;
    string ans="";
    while(l<=r){
      if(l+rht[l]>r){
        ans.push_back(w[0]);
        break;
      }
      if(r-lft[r]<l){
        ans.push_back(w[1]);
        break;
      }
      if(f[l+rht[l]][r]<f[l][r-lft[r]]){
        ans.push_back(w[0]);
        l+=rht[l];
      }
      else{
        ans.push_back(w[1]);
        r-=lft[r];
      }
    }
    return ans;
  }

  vector<tuple<int,int,int> >all;
  vector<int>a(n,0);
  void calc(){
    all.clear();
    for(int i=0;i<n;i++){
      int sm=0;
      for(int j=0;j<n;j++){
        a[j]=t[i][j];
        sm+=a[j];
      }
      if(sm==0)continue;
      solve(a,"LR");    
      all.push_back(make_tuple(f[0][n-1],0,i));
    }
    for(int j=0;j<n;j++){
      int sm=0;
      for(int i=0;i<n;i++){
        a[i]=t[i][j];
        sm+=a[i];
      }
      if(sm==0)continue;
      solve(a,"UD");
      all.push_back(make_tuple(f[0][n-1],1,j));
    }
    sort(all.begin(),all.end(),greater<tuple<int,int,int> >());
  }
  int main(){
    clock_t tStart = clock();
  //  freopen("secret/8.in","r",stdin);
  //  freopen("secret/8.out","w",stdout);  
    scanf("%d %d",&n,&F);
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        scanf("%d",&t[i][j]);
      }
    }
    int K;
    scanf("%d",&K);

    vector<pair<char,int> >ans;
    calc();
    for(int it=0;!all.empty();it++){
      int w,tp,x;
      tie(w,tp,x)=all.back();
      all.pop_back();
      string s="LR";
      if(tp==0){
        for(int j=0;j<n;j++)a[j]=t[x][j];
      }
      else{
        s="UD";
        for(int i=0;i<n;i++)a[i]=t[i][x];
      }
      int sm=0;
      for(int v:a)sm+=v;
      if(sm==0)continue;

      string sol=solve(a,s);
      for(char ch:sol){
        ans.push_back({ch,x});
      }
      if(tp==0){
        for(int j=0;j<n;j++)t[x][j]=0;
      }
      else{
        for(int i=0;i<n;i++)t[i][x]=0;
      }
      if(it%50==0)calc();
    }
    int shots=ans.size();
    printf("%d\n",shots);
    for(auto p:ans){
      printf("%c %d\n",p.first,p.second+1);
    }
    cerr<<K<<endl;
    cerr<<shots<<endl;
    cerr<<"score="<<K-shots<<endl;
    cerr<<"time="<<(double)(clock() - tStart)/CLOCKS_PER_SEC<<" seconds"<<endl;
    return 0;
  }
I just noticed @harshil21 also submitted something in the testing page 
// Basic sol with only 2 hits for now
#include <bits/stdc++.h>
#define mod 1000000007
#define init(arr,val) memset(arr,val,sizeof(arr))
#define f(i,a,b) for(int i=a;i<b;i++)
#define fr(i,a,b) for(int i=a;i>=b;i--)
#define ull unsigned long long int
#define ll long long int
#define pb push_back
#define pf push_front
#define F first
#define S second
#define fast ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define all(a) a.begin(),a.end()
#define br "\n"
using namespace std;
ll findS(ll s) {
  return (sqrtl(8*s + 1) - 1)/2;
}
ll phi(ll n) {
  ll result = n;
  for (ll p = 2; p * p <= n; ++p) {
    if (n % p == 0) {
      while (n % p == 0)
        n /= p;
      result -= result / p;
    }
  }
  if (n > 1)
    result -= result / n;
  return result;
}
bool isPrime(ll a) {
  if(a==1)return false;
  if(a==2 || a==3)return true;
  if(a%2==0 ||a%3==0)return false;
  for(ll i=5; i<=sqrt(a); i+=6)
    if(a%i==0 || a%(i+2)==0)
      return false;
  return true;
}
ll power(ll x,ll y) {
  if (y == 0)
    return 1;
  ll p = power(x, y/2) % mod;
  p = (p * p) % mod;

  return (y%2 == 0)? p : (x * p) % mod;
}
ll nCr(ll n,ll k) {
  ll C[k+1];
  C[0] = 1;
  f(i,0,k+1)C[i]=0;
  for (ll i = 1; i <= n; i++) {
    for (ll j = min(i, k); j > 0; j--)
      C[j] = (C[j] + C[j-1])%mod;
  }
  return C[k];
}
ll LOGN(ll n , ll r) {
  return (n > r-1) ? (1 + LOGN(n / r , r)) : 0 ;
}
void dfs(vector<ll> v[], bool visited[], ll current_node) {
  visited[current_node]=true;
  for(ll nxt_node : v[current_node]) {
    if(visited[nxt_node]==false) {
      dfs(v , visited, nxt_node);
    }
  }
  return;
}
void solve() {
  int n , f ;
  cin >> n >> f ;
  int mat_cell[n+1][n+1];
  f(i,1,n+1) {
    f(j,1,n+1) {
      cin >> mat_cell[i][j] ;
    }
  }
  int in;
  cin >> in ;
  vector< pair<char, int> > lazer;
  f(i,1,n+1) {
    f(j,1,n+1) {
      if(mat_cell[i][j] != 0) {
        int L_hit = 0 , col_cnt = 0 ;
        f(k,j,n+1) {
          if(L_hit + mat_cell[i][k] > f) break ;
          L_hit += mat_cell[i][k];
          col_cnt++;
        }
        int U_hit=0 , row_cnt = 0 ;
        f(k,i,n+1) {
          if(U_hit + mat_cell[k][j] > f) break ;
          U_hit += mat_cell[k][j];
          row_cnt++;
        }
        if(col_cnt > row_cnt) {
          int power = 0 ;
          lazer.pb({'L',i});
          f(k,j,n+1) {
            if(power + mat_cell[i][k] > f) break ;
            power += mat_cell[i][k];
            mat_cell[i][k] = 0;
          }
        } else {
          int power = 0 ;
          lazer.pb({'U',j});
          f(k,i,n+1) {
            if(power + mat_cell[k][j] > f) break ;
            power += mat_cell[k][j];
            mat_cell[k][j] = 0;
          }
        }
      }
    }
  }
  cout << lazer.size() <<br;
  for(auto i:lazer) {
    cout << i.first << " " << i.second <<br;
  }
}
int main() {
  fast ;
  int t = 1;
  //cin >> t;
  while(t--) {
    solve();
  }
  return 0;
}

Lewin solution: CodeChef: Practical coding for everyone
Mihai solution: CodeChef: Practical coding for everyone

1 Like