3 Likes
EURON Solution watch it Guy’s
1 Like
QHOUSE - Bear and House Queries
Fairly Easy problem. Sharing my clean function rich solution.
Three coordinates are important.
- Bottom Right Vertex of the Square. It will be of the form (a,0). The area of square will be 4aa.
- Bottom Right Vertex of the Triangle. It will be of the form (a+b, 2x)
- Top vertex of Triangle. It will be of the form (2x+c,0)
Final area is 4 X a^2 + ( a + b ) X ( c ). Be careful about not using fastio.
/*Binary Search*/
#include <bits/stdc++.h>
#pragma options optimize = 2
using namespace std;
bool check(int x, int y)
{
string s;
cout << "?" << " "<< x << " " << y << endl;
cin >> s;
if(s.compare("YES") == 0)
return true;
return false;
}
int binary_search(int min, int max, int c, int i)
{
bool state;
int mid;
while(min <= max)
{
mid = (max + min)/2;
if(c == 2)
state = check(i, mid);
else
state = check(mid, i);
if(state)
{
min = mid + 1;
}
else
{
max = mid - 1;
}
}
if(state)
{
return(min - 1);
}
return(max);
}
int32_t main()
{
int RBV = binary_search(0,1000,1,0);//Right Bottom Vertex;
int RBTV = binary_search(RBV,1000, 1, 2*RBV);//Right Bottom Vertex of Traingle
int TTV = binary_search(2*RBV, 1000, 2, 0);//Top of Triangle
int area = 4*RBV*RBV + (RBTV)*(TTV-2*RBV);
cout << "! " << area;
return 0;
}
1 Like
Ashigift: Great classic problem.
I defined a Point as a constraint point such that
- for location l,
- if at least c people remain,
- value is incremented by a.
Even a non-tribal camp where one has to eat cakes is a constraint point of the form (l, 0, -a). That is,
- at location l
- if at least zero people remain,
- the value is decremented by a.
I then accumulated all constraints into a vector and sorted them by location.
Then I binary searched to find the smallest group that is able to reach the end of the vector.
Code here::
/*Binary Search*/
#include <bits/stdc++.h>
#define int long long
#pragma options optimize = 2
using namespace std;
template<typename ... T>
void print(const T& ... t)
{
initializer_list<int>{ (std::cout << t << " ", 0)... };
cout << "\n";
}
class Point
{
public:
long long loc, constraint, add;
Point(long long l, long long c, long long a)
{
loc = l; constraint = c; add = a;
}
};
bool by_loc(Point &a, Point &b)
{
return a.loc < b.loc;
}
bool traverse(int start, vector<Point> camp)
{
//int end = -1;
for(auto p: camp)
{
if(start >= p.constraint)
{
start += p.add;
}
if (start < 1)
{
break;
}
//watch(start);
}
if(start >= 1)
{
return false;
}
return true;
}
int binary_search(vector<Point> camp)
{
int max = LLONG_MAX, min = 0, mid; bool state;
while(min <= max)
{
mid = min + (max - min)/2;
state = traverse(mid, camp);
if(state)
{
min = mid + 1;
}
else
{
max = mid - 1;
}
}
if(state)
{
return(min - 1);
}
return(max);
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t;
while(t--)
{
int n, c; cin >> n >> c;
vector<Point> camp;
int x, v, y;
for (int i = 0; i < c; ++i)
{
cin >> x >> v;
v *= -1;
Point p(x, 1, v);
camp.push_back(p);
}
cin >> c;
for (int i = 0; i < c; ++i)
{
cin >> x >> v >> y;
Point p(x, v, y);
camp.push_back(p);
}
sort(camp.begin(), camp.end(), by_loc);
print(binary_search(camp)+1);//binary_search(camp) will return the largest number of people that will fail.
}
return 0;
}
1 Like
EURON Solution in N Log(N).
1 Like
In EURON insert() will give TLE if we call insert() for the full array of length n, but it will pass if we call it for shorter array of length starting from 1 to n just like in your solution.
So the compexity for first insert is always n so total it is O(n^2) but for second method it will be total 1+2+3+…+n which is O(n^2/2) half of O(n^2) so it is passing the testcases.
So the testcases are weak.
1 Like
thank you
Could anyone help me in the LOWSUM problem and tell me why I am getting WA?
My solution link https://www.codechef.com/viewsolution/36053074 .
I am finding the maximum query qmax for the test case and generating the first qmax smallest sums.
Thanks
For Problem STRSUB:
For each query of type (l, r)(l,r), we can find a value cnt for which ans[cnt] \le rans[cnt]≤r.
Answer = sum of ans[i]ans[i] from 1 to cnt - sum of ans[i]ans[i] from 1 to (l-1) + (R-k)(R+1) - (R(R+1)/2 - L*(L-1)/2)(l−1)+(R−k)∗(R+1)−(R∗(R+1)/2−L∗(L−1)/2).
Can someone explain the above hint to me?
I am not able to understand how was the above equation deduced.
Answer = sum of ans[i] from 1 to cnt - sum of ans[i] from 1 to (l-1) +
(R-k)(R+1) - (R(R+1)/2 - L*(L-1)/2)(l−1)+(R−k)∗(R+1)−(R∗(R+1)/2−L∗(L−1)/2).
HINT NO. 3
couldn’t able to figure out why my solution giving Runtime Error(SIGSEGV). Could anybody please help me?
https://www.codechef.com/viewsolution/36072189
QHOUSE problem:-
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
int x[1001];
long int l=0,h=1000;
while(l<h){
long int mid=l+(h-l)/2;
cout<<"? “<<mid<<” "<<0<<endl;
cin>>s;
if(s==“YES”) l=mid+1;
else h=mid;
}
l--;
long int as=(l*2)*(l*2);
long int temp=2*l;
h=1000;
while(l<h){
long int mid=l+(h-l)/2;
cout<<"? "<<mid<<" "<<temp<<endl;
cin>>s;
if(s=="YES") l=mid+1;
else h=mid;
}
l--;
long int base=l;
int y[1001];
l=0,h=1000;
while(l<h){
long int mid=l+(h-l)/2;
cout<<"? "<<"0"<<" "<<mid<<endl;
cin>>s;
if(s=="YES") l=mid+1;
else h=mid;
}
l--;
long int heigth=l-temp;
long int ans = as + (base*heigth);
cout << "! " << ans <<endl;
return 0;
}
this is my code but its shows WA for task#8 and task#9
For LOWSUM, I think this solution should not work in the worst case.
For eg. when K=20000 (or >10000) and qi=10000, it will consider A[0] + B[0…9999], i.e. sum of the first element of (sorted) A and first 10000 elements of (sorted) B. 2nd element of A won’t be considered with the elements of B, which might be in smallest 10000.
Am I missing something really simple, please help me understand this?
@rishup_nitdgp @harshraj22
I didn’t see the code, but if you expect TLE, then maybe you are correct as test case for this question are weak.
2 Likes
I am getting the right answer for the example test cases, as well as custom inputs. i just cannot figure out why I keep getting Wrong Answer! Any help appreciated. Thanks.
https://www.codechef.com/viewsolution/36535848
here ‘nonEmpty’ stores the index of the last non empty stack in the vector of stacks
The test cases may contain duplicate numbers also. Try using the variant of pbds which can handle duplicates as well by using this statement
(notice the bold part)
#define pbds tree<int,null_type,less_equal,rb_tree_tag,tree_order_statistics_node_update>
Given here is the link to my solution .
https://www.codechef.com/viewsolution/36822397
Hope this helps !! 
Can anyone please help me with Inequality Reduction ( TRANSACT) problem? I am trying to solve it using binary search. It works for sample test cases & also some manual tests but I am getting WA in submission. Any help would be appreciated. Thanks.
My Solution
@rishup_nitdgp Hey, previously I was getting TLE for the STACKS problem but after adding the if(val>=max) condition my solution got passed with 1.43s. Can I do any better than that? Code
use merge sort
simple implementation…