Hey folks! I came across this problem and i am pondering for this solution for last 2 days. Is there anyone who could give solution/approach? Thank you in advance
ave shown
Any ideas? Anyone?
can you provide the full link to the problem?
1 Like
So this is a practice problem. It uses webcam for the real time environment
first precalculate the number lower than i for i up to r constraints.
Then, each testcase can be solved by a dp approach. dp[i] stores the minimum time required to get to the i cell. You start from cell 1 and move right 1 by 1.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool prime[100001];
ll int assign[100001];
ll int dp[100001];
void cal_prime(long long int n)
{
ll int p=2;
memset(prime,true,sizeof(prime));
memset(assign,0,sizeof(assign));
for(p=2;pp<=n;p++)
{
if (prime[p])
{
for(ll int i=pp;i<=n;i+=p)
prime[i]=false;
}
}
prime[1]=false;
prime[0]=false;
for(ll int j=2;j<=n;j++)
{
for(ll int k=2;k<=j;k++)
{
if (prime[k])
assign[j]++;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll int t,r1,r2,l;
string n;
cin>>t;
while (t>0)
{
t–;
cin>>r1>>r2;
cin>>l;
cal_prime(l);
cin>>n;
memset(dp,-1,sizeof(dp));
dp[1]=0;
for(int i=2;i<=l;i++)
{
if (n[i-1]!=’*’)
{
for(int j=1;j<i;j++)
{
if (dp[j]!=-1)
{
if((j+1>=i or j+2>=i) or (assign[j]/(j)>=(r1/r2) and j+assign[j]>=i))
{
if (dp[i]==-1)
dp[i]=max(dp[i],dp[j]+1);
else
dp[i]=min(dp[i],dp[j]+1);
//cout<<dp[i];
}
}
}
}
}
if (dp[l]!=-1)
cout<<dp[l]<<"\n";
else
cout<<"No way!"<<"\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool prime[100001];
ll int assign[100001];
ll int dp[100001];
void cal_prime(long long int n)
{
ll int p=2;
memset(prime,true,sizeof(prime));
memset(assign,0,sizeof(assign));
for(p=2;pp<=n;p++)
{
if (prime[p])
{
for(ll int i=pp;i<=n;i+=p)
prime[i]=false;
}
}
prime[1]=false;
prime[0]=false;
for(ll int j=2;j<=n;j++)
{
for(ll int k=2;k<=j;k++)
{
if (prime[k])
assign[j]++;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll int t,r1,r2,l;
string n;
cin>>t;
while (t>0)
{
t–;
cin>>r1>>r2;
cin>>l;
cal_prime(l);
cin>>n;
memset(dp,-1,sizeof(dp));
dp[1]=0;
for(int i=2;i<=l;i++)
{
if (n[i-1]!=’*’)
{
for(int j=1;j<i;j++)
{
if (dp[j]!=-1)
{
if((j+1>=i or j+2>=i) or (assign[j]/(j)>=(r1/r2) and j+assign[j]>=i))
{
if (dp[i]==-1)
dp[i]=max(dp[i],dp[j]+1);
else
dp[i]=min(dp[i],dp[j]+1);
//cout<<dp[i];
}
}
}
}
}
if (dp[l]!=-1)
cout<<dp[l]<<"\n";
else
cout<<"No way!"<<"\n";
}
return 0;
}
I have done thi but getting TLE on hidden cases.hough i think logic is correct Plz help
try to use fastio for this problem. I got ac. i used sieve with bfs. tell me if you want the code.
I used simple dp to solve it.
dp[i] = min number of steps to solve it.
check for at every i, update for dp[i+1],dp[i+2],dp[i+A] (if possible)
In end answer is dp[n]
1 Like
either way… i would be O(n).
please share code
import java.io.*;
import java.util.*;
public class TestClass {
static class Read {
private byte[] buffer =new byte[10*1024];
private int index;
private InputStream input_stream;
private int total;
public Read() {
input_stream = System.in;
}
public int read()throws IOException {
if(total<0)
throw new InputMismatchException();
if(index>=total) {
index=0;
total= input_stream.read(buffer);
if(total<=0)
return -1;
}
return buffer[index++];
}
public long readLong() throws IOException {
long number=0;
int n= read();
while(isWhiteSpace(n))
n= read();
long neg=1l;
if(n=='-') {
neg=-1l;
n= read();
}
while(!isWhiteSpace(n)) {
if(n>='0'&&n<='9') {
number*=10l;
number+=(long)(n-'0');
n= read();
}
else throw new InputMismatchException();
}
return neg*number;
}
public int readInt() throws IOException {
int integer=0;
int n= read();
while(isWhiteSpace(n))
n= read();
int neg=1;
if(n=='-') {
neg=-1;
n= read();
}
while(!isWhiteSpace(n)) {
if(n>='0'&&n<='9') {
integer*=10;
integer+=n-'0';
n= read();
}
else throw new InputMismatchException();
}
return neg*integer;
}
public double readDouble()throws IOException {
double doub=0;
int n= read();
while(isWhiteSpace(n))
n= read();
int neg=1;
if(n=='-') {
neg=-1;
n= read();
}
while(!isWhiteSpace(n)&&n!='.') {
if(n>='0'&&n<='9') {
doub*=10;
doub+=n-'0';
n= read();
}
else throw new InputMismatchException();
}
if(n=='.') {
n= read();
double temp=1;
while(!isWhiteSpace(n)) {
if(n>='0'&&n<='9') {
temp/=10;
doub+=(n-'0')*temp;
n= read();
}
else throw new InputMismatchException();
}
}
return doub*neg;
}
public String readString()throws IOException {
StringBuilder sb = new StringBuilder();
int n = read();
while (isWhiteSpace(n))
n = read();
while (!isWhiteSpace(n)) {
sb.append((char)n);
n = read();
}
return sb.toString();
}
private boolean isWhiteSpace(int n) {
if(n==' '|| n=='\n'|| n=='\r'|| n=='\t'|| n==-1)
return true;
return false;
}
}
static class Write {
private final BufferedWriter bw;
public Write() {
bw = new BufferedWriter(new OutputStreamWriter(System.out));
}
public void print(String str) throws IOException {
bw.append(str);
}
public void printLine(String str) throws IOException {
print(str);
bw.append("\n");
}
public void close()throws IOException {
bw.close();
}
public void flush()throws IOException {
bw.flush();
}
}
public static void pn(Object o)
{
System.out.println(o);
}
public static void p(Object o)
{
System.out.print(o+" ");
}
public static ArrayList<Integer> sieve(int n)
{
boolean prime[] = new boolean[n+1];
ArrayList<Integer> al=new ArrayList<Integer>();
for(int i=0;i<=n;i++)
prime[i] = true;
for(int p = 2; (p*p)<=n; p++)
{
if(prime[p] == true)
{
for(int i = p*p; i <= n; i += p)
prime[i] = false;
}
}
for(int i=2;i<=n;i++)
{
if(prime[i]==true)
al.add(i);
}
return al;
}
public static int[] numberOfPrimes(int n,ArrayList<Integer> al)
{
int dp[]=new int[n+1];
for(int i=1;i<=n;i++)
{
if(al.contains(i))
dp[i]=dp[i-1]+1;
else
dp[i]=dp[i-1];
}
return dp;
}
public static void main(String[] args) throws IOException
{
Read s=new Read();
Write w=new Write();
int t=s.readInt();
ArrayList<Integer> al=sieve(100000);
int nop[]=numberOfPrimes(100000,al);
while(t-->0)
{
int r1=s.readInt(),r2=s.readInt();
int n=s.readInt();
String str=s.readString();
if (str.charAt(0)=='*') {
w.printLine("No way!");
continue;
}
boolean visited[] =new boolean[n+1];
int count[]=new int[n+1];
int i=0;
Queue<Integer> queue=new LinkedList<Integer>();
queue.add(i);
visited[i] = true;
while(!queue.isEmpty())
{
int k=queue.remove();
if (k==(n-1)) {
break;
}
long a=(k+1)*((long)r1);
long b=nop[k+1]*((long)r2);
if(b>=a)
{
if(k+nop[k+1]<=n-1 && !visited[k+nop[k+1]])
{
if(str.charAt(k+nop[k+1])=='#')
{
queue.add(k+nop[k+1]);
count[k+nop[k+1]]=count[k]+1;
visited[k+nop[k+1]] = true;
}
}
}
if(k+2<=n-1 && !visited[k+2])
{
if(str.charAt(k+2)=='#')
{
queue.add(k+2);
count[k+2]=count[k]+1;
visited[k+2] = true;
}
}
if(k+1<=n && !visited[k+1])
{
if(str.charAt(k+1)=='#')
{
queue.add(k+1);
count[k+1]=count[k]+1;
visited[k+1] = true;
}
}
}
if (n==1)
{
if (str.charAt(0)=='#')
w.printLine("" + count[n - 1]);
else
w.printLine("No way!");
}
else {
if (count[n - 1] != 0)
w.printLine("" + count[n - 1]);
else
w.printLine("No way!");
}
}
w.flush();
w.close();
}
}