Problem link: Color Play
I tried a greedy approach for this problem, here is my solution :
But this gave me WA. So I found a test case also:
answer should be 1 , but my code gives 3. I guess this is DP problem. Can anyone please help.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Problem link: Color Play
I tried a greedy approach for this problem, here is my solution :
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
signed main(void){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef HELL_JUDGE
freopen("input","r",stdin);
freopen("output","w",stdout);
#endif
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
deque<char>d;
d.push_back(s[0]);
map<char,int>m;
m['G'] =1;
m['R'] =2;
m['B'] =3;
map<int,char>rm;
rm[1] ='G';
rm[2] ='R';
rm[3] ='B';
for(int i=1 ; i<n; ++i) {
if(d.back() != s[i]) {
char ch = d.back(); d.pop_back();
ch = rm[m[ch]^m[s[i]]];
while (!d.empty() && d.back() != ch) {
char temp = d.back(); d.pop_back();
ch = rm[m[ch]^m[temp]];
}
d.push_back(ch);
} else {
d.push_back(s[i]);
}
}
cout << d.size() << '\n';
}
return 0;
}
But this gave me WA. So I found a test case also:
1
7
RGRRGRR
answer should be 1 , but my code gives 3. I guess this is DP problem. Can anyone please help.
I am trying to solve UVa 107 problem. It seems to be an maths oriented problem. Initially I tried to derive a few relation but they didn't seem to be helpful.
After searching for any online explaination i found this. Here if you consider first point in explaination (N/(N+1))^(M-1) = B / A, I am not able to understand how this relation is true. It would help me if anyone could explain it. Thanks.
Problem Statement : Hotel Queries
for this problem, I implemented two solutions. The first solution by using merge sort tree with simple vector and Second is by using merge sort tree with multiset. Both of the solutions are giving me TLE for 3 test cases. Could you please share a better approach.
#include <iostream>
#include <algorithm>
#include <string>
// #include <sstream>
// #include <fstream>
// #include <iomanip>
#include <chrono>
#include <numeric>
#include <utility>
#include <functional>
#include <bitset>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <array>
// #include <unordered_map>
// #include <unordered_set>
#include <set>
#include <map>
// #include <deque>
#include <climits>
#include <cstring>
#include <cmath>
#include <cassert>
#include <cstdio>
using namespace std;
using namespace std::chrono;
// using namespace placeholders;
// using namespace __gnu_pbds;
// template<typename TypeInfo>
// using new_set = tree< // find_by_order & order_of_key
// TypeInfo ,
// null_type ,
// less<TypeInfo> ,
// rb_tree_tag ,
// tree_order_statistics_node_update
// > ;
void debug_out() { cerr << endl; }
template <typename HEAD, typename... TAIL>
void debug_out(HEAD H, TAIL... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef HELL_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 0
#endif
const int MAXM = (int)1e5+100;
const int MAXN = (int)2e5+100;
const int MOD = (int)1e9+7;
// default size is considered MAXN
long long arr[MAXN];
vector<int> seg_tree[4*MAXN];
// BUILD THE SEGMENT TREE
void build(int current_node , int left_, int right_){
if(left_ == right_) {
seg_tree[current_node].push_back(arr[left_]);
return ;
}
int mid_point = left_ + (right_ - left_) / 2;
build(2*current_node, left_ , mid_point);
build(2*current_node+1, mid_point+1 , right_);
merge(
seg_tree[current_node*2].begin() , seg_tree[2*current_node].end() ,
seg_tree[current_node*2+1].begin() , seg_tree[2*current_node+1].end(),
back_inserter(seg_tree[current_node])
);
return ;
}
int query(int current_node , int start , int end , int member){
if(seg_tree[current_node].back() < member){
return -1;
}
if(start == end){
if(seg_tree[current_node].back() < member){
return -1;
}else{
seg_tree[current_node].back() -= member;
return start;
}
}
int mid = (start + end) /2;
int ans=-1;
if(seg_tree[2*current_node].back() >=member){
ans = query(2*current_node , start , mid , member);
}else{
ans = query(2*current_node+1 ,mid+1 , end , member);
}
seg_tree[current_node].clear();
merge(
seg_tree[current_node*2].begin() , seg_tree[2*current_node].end() ,
seg_tree[current_node*2+1].begin() , seg_tree[2*current_node+1].end(),
back_inserter(seg_tree[current_node])
);
return ans;
}
int main(void){
#ifdef HELL_JUDGE
freopen("input","r",stdin);
freopen("output","w",stdout);
freopen("error","w",stderr);
#endif
#ifdef HELL_JUDGE
auto INITIAL_TIME = high_resolution_clock::now();
#endif
int n , m; cin >> n >> m;
for(int i=0;i<n;++i){
cin >> arr[i];
}
build(1 , 0 , n-1 );
while(m--){
int x; cin >> x;
cout << query(1 , 0 , n-1 , x) +1 << '\n';
}
#ifdef HELL_JUDGE
auto FINAL_TIME = high_resolution_clock::now();
cout << "Time : "
<< duration_cast<milliseconds>(FINAL_TIME-INITIAL_TIME).count()
<< " ms" << '\n';
#endif
return 0;
}
#include <iostream>
#include <algorithm>
#include <string>
// #include <sstream>
// #include <fstream>
// #include <iomanip>
#include <chrono>
#include <numeric>
#include <utility>
#include <functional>
#include <bitset>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <array>
// #include <unordered_map>
// #include <unordered_set>
#include <set>
#include <map>
// #include <deque>
#include <climits>
#include <cstring>
#include <cmath>
#include <cassert>
#include <cstdio>
using namespace std;
using namespace std::chrono;
// using namespace placeholders;
using namespace __gnu_pbds;
template<typename TypeInfo>
using new_set = tree< // find_by_order & order_of_key
TypeInfo ,
null_type ,
greater<TypeInfo> ,
rb_tree_tag ,
tree_order_statistics_node_update
> ;
void debug_out() { cerr << endl; }
template <typename HEAD, typename... TAIL>
void debug_out(HEAD H, TAIL... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef HELL_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 0
#endif
const int MAXM = (int)1e5+100;
const int MAXN = (int)2e5+100;
const int MOD = (int)1e9+7;
multiset<int , greater<int>> seg[4*MAXN];
long long arr[MAXN];
void build(int current_node , int start , int end){
if(start == end){
seg[current_node].insert(arr[start]);
return;
}
for(int i=start;i<=end; ++i){
seg[current_node].insert(arr[i]);
}
int mid = (start + end) /2;
build(2*current_node , start , mid);
build(2*current_node +1 , mid+1 , end);
}
pair<int,int> query(int current , int start , int end , int member){
int x = *(seg[current].begin());
if(x < member){
return {-1,-1};
}
if(start==end){
pair<int,int>p;
p.first = x;
p.second = start;
seg[current].erase(seg[current].begin());
if(x-member >0){
seg[current].insert(x-member);
}
return p;
}
int mid = (start + end) /2;
pair<int, int > ans;
int y = *(seg[2*current].begin());
if(y >= member){
ans = query(2*current , start , mid , member);
}else{
ans = query(2*current+1 , mid+1 , end , member);
}
if(ans.first!=-1 && ans.second!=-1){
auto itr = seg[current].find(ans.first);
seg[current].erase(itr);
if(ans.first - member >=0){
seg[current].insert(ans.first-member);
}
}
return ans;
}
int main(void){
#ifdef HELL_JUDGE
freopen("input","r",stdin);
freopen("output","w",stdout);
freopen("error","w",stderr);
#endif
#ifdef HELL_JUDGE
auto INITIAL_TIME = high_resolution_clock::now();
#endif
int n , m; cin >> n >> m;
for(int i=0; i < n; ++i){
cin >> arr[i];
}
build(1 , 0, n-1);
while(m--){
int x; cin >> x;
pair<int,int> a = query(1 , 0 , n-1 , x) ;
cout << a.second + 1 << '\n';
}
#ifdef HELL_JUDGE
auto FINAL_TIME = high_resolution_clock::now();
cout << "Time : "
<< duration_cast<milliseconds>(FINAL_TIME-INITIAL_TIME).count()
<< " ms" << '\n';
#endif
return 0;
}
In this problem i sorted the activities by their ending time. With this solution i got Wrong Answer 6 times. I got so much frustrated that i implemented this brute force solution & even it gave me a wrong answer. Would you please point out my mistake.
Name |
---|