Help needed!A problem about N-Dimentional Array Lookup

[DavidWang]

I have deliberated upon this problem for long, which seems very easy, but in vain. So I come here for some help. Please read it throughout though it is somewhat copious.

All Description is as follows:
An N-dimensional array contains zero or more (N-1)-dimensional arrays, each of which can have different length. A plain array (1-dimensional) contains zero or more elements. In our problem we assume that the elements are all positive integers.
An N-dimensional query is represented as a list of N integers, namely the indices for each dimension. Index is always zero based. A valid query should point to an element at its end-point.

Input Description:
Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.
The first line of each test case is the array representation. The dimension is not given explicitly. The dimension will be at least 1 and at most 100. Length of each dimension does not exceed 100. The total number of elements does not exceed 1,000,000. Space is not important in the array representation and should be ignored. You may assume that the array representation is always valid.
The second line contains the query, which is a list of M (1 <= M <= 100) integers separated with a single space.

Output Description:
Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.
If the query can not be satisfied, print the sentence "Invalid query!" on a single line, otherwise print the value of the element which the query specifies.

Sample Input

2

{{1}, {2, 3}}
1 0

{1, 2, 3}
3

Sample Output

Case 1:
2

Case 2:
Invalid query!

[little joey]

Without proper testcases it is difficult to say if it's correct, but this might work:

Code: Select all

*** DELETED ***

[sunmoonstar_love]

the problem can be found in

http://acm.zju.edu.cn/show_problem.php?pid=2538


It is one from the 30th ACM/ICPC Hangzhou prem.....

[little joey]

Well, in that case I have deleted my code. I don't want to give spoilers for other sites. And anyway: it gave WA

[DavidWang]

sunmoonstar_love, the URL you provide has a problem alike. However, it is not helpful. What I need is a wonderful idea or the code.

[misof]

sunmoonstar_love, the URL you provide has a problem alike. However, it is not helpful. What I need is a wonderful idea or the code.

Not much to think about, the difficulty of this problem lies in implementation only. Just learn how dynamic memory allocation works in your programming language and store the array in memory exactly as described in the problem statement.

(The array can be imagined as a tree of depth=# of dimensions. When answering a query, walk down the tree, the i-th coordinate gives the number of the son node you move into in the i-th step.)

[Adrian Kuegel]

Well, in that case I have deleted my code. I don't want to give spoilers for other sites. And anyway: it gave WA :)

This problem has one special case:
A 1-dimensional array can contain zero elements!
{}
0
should give "Invalid query!"

[little joey]

My code handled that correctly.

Code: Select all

6

{}
0 

{{},{},{}}
1 0

{{},{1,2,3},{}}
1 1

{7,6,5,4,3,2,1}
4

{{{{{1}}}}}
0 0 0 0 0

{{{{{{{{1,2,3}}},{{{}}},{{{4},{5}},{{6}}}}}}}}
0 0 0 0 2 0 1 0

Gives

Code: Select all

Case 1:
Invalid query!

Case 2:
Invalid query!

Case 3:
2

Case 4:
3

Case 5:
1

Case 6:
5

Maybe I should treat the numbers as a string of digits, rather than converting them to 32-bits signed integers?

[Adrian Kuegel]

I used 64 bit integers to store the elements. Also, I made an additional check, if the number of given integers in the query is equal to the dimension of the array.

[DavidWang]

My code handled that correctly.

Code: Select all

6

{}
0 

{{},{},{}}
1 0

{{},{1,2,3},{}}
1 1

{7,6,5,4,3,2,1}
4

{{{{{1}}}}}
0 0 0 0 0

{{{{{{{{1,2,3}}},{{{}}},{{{4},{5}},{{6}}}}}}}}
0 0 0 0 2 0 1 0

Gives

Code: Select all

Case 1:
Invalid query!

Case 2:
Invalid query!

Case 3:
2

Case 4:
3

Case 5:
1

Case 6:
5

Maybe I should treat the numbers as a string of digits, rather than converting them to 32-bits signed integers?

Maybe you will give some samples handled incorrectly by your code.

[sunmoonstar_love]

sunmoonstar_love, the URL you provide has a problem alike. However, it is not helpful. What I need is a wonderful idea or the code.

Sorry, but I just want to tell Little Joey
where the problem can be judge

DFS is ok.

Don't have to construct a real N-dimensional array.

[little joey]

Maybe you will give some samples handled incorrectly by your code.

If I had such samples, I could fix my code.

Anyway, here's my code again. It now treats numbers as a string of digits, so overflow of an integer type should not occur. It even takes care of negative indices in the query, although I don't know if they appear in the input.

Code: Select all

#include <stdio.h>
#include <ctype.h>

/* declarations */

char array[13000000];
void read_array(void);
int skip_element(int *parsepos);
int get_element(int level, int *parsepos);
/* array[] contains the first line of the input with spaces removed
   it's declared 13 mln because we can have 1 mln numbers of max 10 digits with braces and commas
   
   read_array() reads it from the input
   
   skip_element() advances parsepos over the current element, which is either a number or a pair
   of matching braces '{' and '}'
   
   get_element() recusively accesses the elements indexed by the query, calling skip_element() to
   get to the indexed element. at the bottom level it finds the number and leaves parsepos
   pointing to it
   
   get_element() and skip_element() use and update the referenced variable parsepos that indexes
   into array[]; they return negative numbers in case of error conditions
   */

int subscript[128];
int subscripts;
void read_query(void);
/* subscript[] contains the indexes from the second line of the input
   read_query() reads them from the input
   */

int read_number(void);
void skip_line(void);
/* helper functions:
   read_number() reads a number from the input and advances to the next line
   skip_line() advances to the next line in the input
   */

int main(void);
/* main() reads the number of cases and processes them one by one
   reads the input, calls get_element() to process it and prints the result
   */


/* definitions */

int main(void){
   int cases,caseno;
   int parsepos;
   
   cases=read_number();
   for(caseno=1;caseno<=cases;caseno++){
      if(caseno>1) printf("\n");
      printf("Case %d:\n",caseno);
      skip_line();
      read_array();
      read_query();
      parsepos=0;
      if(get_element(0,&parsepos)<0) printf("Invalid query!\n");
      else{
         while(isdigit(array[parsepos])) putchar(array[parsepos++]);
         putchar('\n');
         }
      }
   return 0;
   }
   
void skip_line(void){

   while(getchar()!='\n');
   }
   
int read_number(void){
   int result=0;
   int c;
   
   while(!isdigit(c=getchar()));
   while(isdigit(c)){
      result=10*result+c-'0';
      c=getchar();
      }
   while(c!='\n') c=getchar();
   return result;
   }
   
void read_query(void){
   int c;
   int sign;
   
   subscripts=0;
   c=getchar();
   while((c!='\n')&&(c!=EOF)){
      subscript[subscripts]=0;
      sign=1;
      while(!isdigit(c)&&(c!='\n')&&(c!=EOF)){
         if(c=='-') sign*=-1;
         c=getchar();
         }
      if((c=='\n')||(c==EOF)) break;
      while(isdigit(c)){
         subscript[subscripts]=10*subscript[subscripts]+c-'0';
         c=getchar();
         }
      subscript[subscripts++]*=sign;
      }
   }
   
void read_array(void){
   char *ptr=array;
   
   while((*ptr=getchar())!='\n'){
      if(!isspace(*ptr)) ptr++;
      }
   *ptr='\0';
   }

int skip_element(int *parsepos){
   int nesting=0;
   
   if(isdigit(array[*parsepos])){
      while(isdigit(++(*parsepos)));
      }
   else{
      if(array[*parsepos]!='{') return -1;
      do{
         switch(array[(*parsepos)++]){
         case '{':
            nesting++;
            break;
         case '}':
            nesting--;
            break;
         case '\0':
            return -2;
            }
         }while(nesting);
      }
   return 0;
   }

int get_element(int level, int *parsepos){
   int i;
   int result;

   if(level==subscripts){
      if(!isdigit(array[*parsepos])) return -3;
      else return 0;
      }
   else{
      if(array[(*parsepos)++]!='{') return -4;
      if(subscript[level]<0) return -6;
      for(i=0;i<subscript[level];i++){
         if(result=skip_element(parsepos)) return result;
         if(array[(*parsepos)++]!=',') return -5;
         }
      return get_element(level+1,parsepos);
      }
   }

Maybe someone can have a look.
I noticed that people get accepted on zju in 0.000 seconds with less than 400k of memory. So the 1,000,000 elements should be taken with a grain of salt.

[DavidWang]

little joey, thanks for your help.
I used your code to test the samples you have verified, but it gave wrong answers. I don't know why. Furthermore, I guess maybe there is something wrong with function "get_element". I have been thinking on.