This article’s purpose is studying the unsolved problems in last contest for my P.S skill. It is made personally in the Notion and exported.
Editorial is here.
Below solutions are review of non-solved problem in the contest.
I read the problems A,B,C,D1,D2. But I’ve solved A,B,D1.
C - Robot Breakout
This problem’s main point is not simulation.
I’ve thought it is DP and simulation(or BFS) but the solution is simple than I thought.
First, Define the area by the min point(x,y) and max point(x,y).
(max x and y = 10^5, min x and y = -10^5)
And Move that points max and min by the robot’s available functions.
For example, If the robot cannot move to right (That mean, the robot can move to up and down and left)
The x of the max point have to find min right moving unavailable robot’s x coordinate. Because, That robot cannot move to right. That mean is if the robots in right site of min(max points) robot cannot move left direction, it could be not match between both robots.
Let’s look at the code.
#include <iostream>
using namespace std;
int main()
{
int q;
cin>>q;
while(q--)
{
int n;
cin>>n;
int minx = -100000, miny=-100000;
int maxx = 100000, maxy = 100000;
int X,Y,f1,f2,f3,f4;
for(int i=0;i<n;i++)
{
cin>>X>>Y>>f1>>f2>>f3>>f4;
if(!f1)
minx = max(minx, X);
if(!f2)
maxy = min(maxy, Y);
if(!f3)
maxx = min(maxx, X);
if(!f4)
miny = max(miny, Y);
}
if(minx<=maxx && miny<=maxy)
cout<<"1 "<<minx<<" "<<miny<<endl;
else
cout<<"0"<<endl;
}
return 0;
}
The “if statement” of the last output code’s the condition check the all of the robot can move to same points.
D2. RGB Substring (hard version)
I’ve solved the easy version by full-search. Because the input size is n < 2000.
But this problem has a large input. So, I have to think more.
I thought it is Definitely DP problem.
And It is (But the other technique more important to solve it)
This problem can solve easily using Sliding Window(Two points)
my easy version’s code has O(n^2) and the below solution has \($O(n)\)$.
#include <iostream>
using namespace std;
int main()
{
int q;
cin>>q;
while(q--)
{
int x,y;
cin>>x>>y;
string s;
cin>>s;
int arr[3] = {1, 2, 3};
int minv = 0x0FFFFFFF;
for(int i=0;i<3;i++)
{
int minp=0, maxp=y-1;
int curv = 0;
for(int j=0;j<y;j++)
{
if(s[j] == 'R' && arr[(i+j)%3] != 1)
curv++;
if(s[j] == 'G' && arr[(i+j)%3] != 2)
curv++;
if(s[j] == 'B' && arr[(i+j)%3] != 3)
curv++;
}
while(1)
{
// cout<<"SLIDE MI = "<<minp<< " MA = "<<maxp<<" curv = "<<curv<<endl;
minv=min(minv,curv);
if(s[minp] == 'R' && arr[(minp + i)%3] != 1)
curv--;
if(s[minp] == 'G' && arr[(minp + i)%3] != 2)
curv--;
if(s[minp] == 'B' && arr[(minp + i)%3] != 3)
curv--;
minp++;
maxp++;
if(s[maxp] == 'R' && arr[(maxp + i)%3] != 1)
curv++;
if(s[maxp] == 'G' && arr[(maxp + i)%3] != 2)
curv++;
if(s[maxp] == 'B' && arr[(maxp + i)%3] != 3)
curv++;
if(maxp >= x)
break;
}
}
cout<<minv<<endl;
}
return 0;
}