Help in third problem of google kickstart round B

→ Обратите внимание

До соревнования
Codeforces Round 987 (Div. 2)
19:54:38
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Codeforces Round 987 (Div 2) - Solution Discussion

Shayan

До начала 21:59:38

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
4	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
8	Dominater069	154
8	nor	154

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя nipul1

Help in third problem of google kickstart round B

Автор nipul1, история, 5 лет назад, По-английски

Problem My approach was to keep the multiplication factors in stack and pop them when a bracket ends

code

//JSD
#include<iostream>
#include<map>
#include<stack>
#define ll long long 
#define Maxx (long long)1e9
using namespace std;
void solve(int test){
	string s;
	cin>>s;
	int n=s.length();
	stack<int> st;
	int factor=1;
	map<char, int > m;
	for(int i=0;i<n;i++){		
		if(isdigit(s[i])){
			st.push(int(s[i]-'0'));
			factor*=int(s[i]-'0');
		}
		if(s[i]==')'){
			int x=st.top();
			st.pop();
			factor/=x;			
		}
		if(isalpha(s[i])){
			m[s[i]]+=factor;
		}
	}
	ll x=0,y=0;
	x=(x+m['S'])%Maxx;				
	x=(x-m['N']+Maxx)%Maxx;
	y=(y+m['E'])%Maxx;
	y=(y-m['W']+Maxx)%Maxx;
	cout<<"Case #"<<test<<": "<<y+1<<" "<<x+1<<"\n";	
}
int main(){
	ll t;
	cin>>t;
	int test=1;
	while(t--){
		solve(test);
		test++;
	}
	return 0;
}

Please Help I am unable to find the mistake

#googlekickstart, #stack

nipul1
5 лет назад
13

Комментарии (11)

Показать архивные | Написать комментарий?

kabeer27

5 лет назад, # |

The value of factor will most probably overflow if it is something like 9(9(9(9(9(9.........)))

→ Ответить

nipul1

5 лет назад, # ^ |

so how can I deal with it, I thought of using modular arithmatic while contest but got stuck in the fact that fermat's theorem can't be applied to non prime numbers for taking mod so how actually we can handle that. thanks for replying

→ Ответить

CoderPenguin

5 лет назад, # ^ |

Fermat's little theorem only comes into play when computing modulo inverse. There are no divisions, so it doesn't really matter if the value you've to take modulo by is prime or not.

→ Ответить

nipul1

5 лет назад, # ^ |

← Rev. 2 →

actually I had divided the factor value by the top of stack but now I have changed my code a bit and removed division part by recalculating the factor value each time it is needed

code

//JSD
#include<iostream>
#include<map>
#include<vector>
#define ll long long 
#define Maxx (long long)1e9
using namespace std;
void solve(int test){
	string s;
	cin>>s;
	int n=s.length();	
	int factor=1;
	map<char, int > m;
	vector<int > st;	
	for(int i=0;i<n;i++){		
		if(isdigit(s[i])){
			st.push_back(int(s[i]-'0'));			
		}
		if(s[i]==')'){
			int x=st.back();
			st.pop_back();			
		}
		if(isalpha(s[i])){
			factor=1;
			for(auto x: st){
				factor=(factor*x)%Maxx;
			}
			m[s[i]]=(m[s[i]]+factor)%Maxx;
		}
	}
	ll x=0,y=0;
	x=(x+m['S'])%Maxx;				
	x=(x-m['N']+Maxx)%Maxx;
	y=(y+m['E'])%Maxx;
	y=(y-m['W']+Maxx)%Maxx;
	cout<<"Case #"<<test<<": "<<y+1<<" "<<x+1<<"\n";	
}
int main(){
	ll t;
	cin>>t;
	int test=1;
	while(t--){
		solve(test);
		test++;
	}
	return 0;
}

and it is still giving me wrong answer on second test case

→ Ответить

ma_da_fa_ka

5 лет назад, # ^ |

← Rev. 2 →

In your submission

1 factor should be long long

2 value of map mp should be long long

→ Ответить

BumbleBee

5 лет назад, # ^ |

I solved it using modular arithmetic.
There are only additions and multiplications. Why would you need Fermat's theorem?

→ Ответить

nipul1

5 лет назад, # ^ |

Now I have changed the code using addition and multiplications but still getting a WA earlier I used division in my logic that's why I needed fermat's theorem Please review the code in my previous comment

→ Ответить

kabeer27

5 лет назад, # ^ |

you could keep a stack of values instead of doing division you can just go back to the previous value, Example you encounter 2(9(..)).

You append into your stack [1, 2, 18] as we encounter them in 2 .. 9 order, then after 9's parenthesis is closed you can just pop the 18 and go back to using 2, no need of division.

→ Ответить

nipul1

5 лет назад, # ^ |

Thank you

→ Ответить

ma_da_fa_ka

5 лет назад, # ^ |

← Rev. 2 →

My approach : Total digits will be at max 500 since each digit will be linked with at least 2 parenthesis and one char. So there are total 500digits. Just brute them every time you encounter ')', do some arithmetic, count frequency of each char. complexity will be (n^2 + m) where n is 500 and m is length of string. AC code https://ideone.com/qXVQCT

→ Ответить

nipul1

5 лет назад, # ^ |

← Rev. 2 →

ok thanks , got it

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 14.11.2024 19:40:22 (h2).

Десктопная версия, переключиться на мобильную.

При поддержке