Circle Summation (30 Points) InterviewStree Puzzle cont

Question

Further to the question I solved it in following way.

#include <iostream>
#include <algorithm>
#include <iterator>
#include <stdio.h>
int main ( int argc, char **argv) {
 int T; // number of test cases
 std::cin >> T;
 for ( int i = 0 ; i < T; i++) {
 int N; // number of childrens
 std::cin >> N;
 int M; // number of rounds
 std::cin >> M;
 long long childrens[50];
 for ( int j = 0; j < N; j++ ) 
 std::cin >> childrens[j];
 int pos = 0;
 for ( int i = 0; i < N ; i++) {
 long long childs[50];
 for ( int j = 0; j < N; j++ ) 
 childs[j] = childrens[j];
 for ( int j = 0; j < M; j++) {
 int left = ( pos == 0) ? N - 1 : pos - 1;
 int right = ( pos + 1 >= N ) ? 0 : pos + 1;
 childs[pos] = (childs[pos] + childs[left] + childs[right])% 1000000007;
 pos++;
 pos = ( pos >= N ) ? 0 : pos;
 }
 std::copy(childs ,childs + N ,std::ostream_iterator<long long>(std::cout," "));
 std::cout << std::endl;
 }
 std::cout << std::endl;
 }
 return 0;
}

but the M can be 10^9, My code is going to take lot of time to finish, What are the various ways I can optize this.

• Winston Ewert: hehe, I'm trying the same problem. I don't know how to solve it.

Answer 1

#include <iostream>
#include <algorithm>
#include <iterator>
#include <stdio.h>
int main ( int argc, char **argv) {
 int T; // number of test cases
 std::cin >> T;
 for ( int i = 0 ; i < T; i++) {
 int N; // number of childrens
 std::cin >> N;
 int M; // number of rounds
 std::cin >> M;

Why split this across two lines instead of std::cin >> N >> M;?

 long long childrens[50];

I missed this in my first submissions and tried using 32 bit integers. It didn't work so well...

 for ( int j = 0; j < N; j++ ) 
 std::cin >> childrens[j];
 int pos = 0;
 for ( int i = 0; i < N ; i++) {
 long long childs[50];
 for ( int j = 0; j < N; j++ ) 
 childs[j] = childrens[j];
 for ( int j = 0; j < M; j++) {
 int left = ( pos == 0) ? N - 1 : pos - 1;

You can use left = (pos + N - 1) % N which works thanks to modular math.

 int right = ( pos + 1 >= N ) ? 0 : pos + 1;

You can use right = (pos + 1) % N

 childs[pos] = (childs[pos] + childs[left] + childs[right])% 1000000007;
 pos++;
 pos = ( pos >= N ) ? 0 : pos;

You can use pos = (pos + 1) % N

 }
 std::copy(childs ,childs + N ,std::ostream_iterator<long long>(std::cout," "));
 std::cout << std::endl;
 }
 std::cout << std::endl;
 }
 return 0;
}

Generally, writing brute force solutions for a site like Interviewstreet is a waste of time. Its not like you can write your brute force solution, and then optimize it so that it will run fast enough. You need to come up with a completely different approach.

Since Interviewstreet is trying to test your abilities I'm not going to share my solution. (Unless you have a solution for the Meeting Point problem, then I'll trade :P) But I will give a hint: think back to linear algebra.