Have you done it? i have memory limit in test 10 too (c++)

Have you done it? i have memory limit in test 9 too (c++)

Edited by author 05.09.2017 19:58

Edited by author 05.09.2017 19:58

Do you think test case number one is the sample?

done!

...

Edited by author 06.12.2014 19:30

I solve without loop but is return WA#4

There is my algorithm :
if in list has 1 , 2 , 3 together always "Yes"
otherwise "No" am I right or any case is there ?

Edited by author 09.08.2017 09:41

Edited by author 09.08.2017 09:42

Or this, aldo wa 15
What´s the problem??

#include <bits/stdc++.h>
using namespace std;
const int infInt = 1e9;

vector<int>adj[100010];
pair<int,int> edges[100010];
int final;
map< pair<int,int> ,int> Map;
bool mark[100010];

bool vis[100010];
int dp[100010];

int f(int u){
  if(edges[u].second==final)return 0;
  if(vis[u])return dp[u];
  vis[u]=true;
  int x=edges[u].first;
  int y=edges[u].second;
  int ans=infInt;
  for(auto z:adj[y]){
    int v=Map[make_pair(y,z)];
    if(v>u)
      ans=min(ans,1+f(v));
  }
  return dp[u]=ans;
}


void rec(int u){
  if(edges[u].second==final){
    cout<<" "<<final<<endl;
    return;
  }
  int x=edges[u].first;
  int y=edges[u].second;
  for(auto z:adj[y]){
    int v=Map[make_pair(y,z)];
    if(v>u and dp[u]==1+f(v)){
      cout<<" "<<y;
      rec(v);
      break;
    }
  }
}

int main(){
  int ant,curr,root,n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>curr;
    if(i>0){
      edges[i].first=ant;
      edges[i].second=curr;
      adj[ant].push_back(curr);
      Map[make_pair(ant,curr)]=i;
    }

    if(i==0)
      root=curr;
    ant=curr;
    if(i==n-1)
      final=curr;
  }
  if(root==curr){
    cout<<root<<endl;
    return 0;
  }
  int best=infInt,bestInd=-1;
  for(int i=1;i<n;i++){
    if(edges[i].first==root){
      int ans=f(i);
      if(ans < best){
        best=ans;
        bestInd=i;
      }
    }
  }
  cout<<edges[bestInd].first;
  rec(bestInd);

}

Yay \o/

Lee algorithm. Runs in O(N * M).

If you don't know it, here is a short description: you start from starting position (sl, sc) and now you expand this node; in a queue you put all its neighbours. You do this only if you optimize by going to that neighbour, i.e. the current cost is shorter than the previous one. let a[i][j] be a matrix with two fields: boots and length. a[i][j] means: minimum number of boots and minimum length to reach (i, j) from start position.
You expand from (x, y) to a neighbour (c, d) when:
a[x][y].boots + 1 (if you change boots, 0 else) < a[c][d].boots or a[x][y].boots + 1 = a[c][d].boots and a[x][y].length + 1 < a[c][d].length. Obvious, you take the valid neighbours (not 0s or outside ones)
hope it's clear...

It could be proved that in Dijkstra's algorithm the choice K = E /V is assimptotically optimal. So, applying to our problem, E / V equals to 8.

yes, coordinates may be negative and this problem is very very easy :)