SPAMCLAS - Editorial

PROBLEM LINK:

Practice

Contest

Author: Praveen Dhinwa

Tester: Jingbo Shang

Editorialist: Utkarsh Saxena

PROBLEM

You are given N Neurons. i^{th} neuron receives an input x_i gives an output y_i=w_i*x_i+b_i.
Also x_{i+1} = y_i. Given a range [L, R] as input to x_1, find for how many inputs the y_n was even and odd.

Constraints: n \le 10^5, 1\leq L \leq R\leq 10^5

EXPLANATION

This problem is inspired by Neural Nets in machine learning.
Nowadays, everyone is talking about deep learning and Artificial Neural Nets (ANNs).
This problem used a very trivialized definition of Neural Nets.

You only need to know the parity of the output.
So you can take all transformations y_i=w_i*x_i+b_i and make it modulo 2.
The parity of y_i depends only on the parity of x_i.
Doing this repetitively will imply parity of y_n is only dependent on parity of x_1.
So just check parity of y_n when x_1=0 and parity when x_1=1.

Then check how many numbers in [L,R] has even parity (will correspond to x_1=0)
and how many have odd parity(will correspond to x_1=1)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

4 Likes

Please someone help me to find the bug in my code because I keep getting “Wrong Answer” (WA)

import java.io.*;
import java.util.*;
class spam2
{
public static void main() throws IOException
{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    Scanner sc=new Scanner(System.in);
    
    int t=Integer.parseInt(br.readLine());
    
    while(t>0)
    {
        String l=br.readLine();
        StringTokenizer st=new StringTokenizer(l);
        int n=0,minx=0,maxx=0,w=0,b=0;
        while(st.hasMoreTokens())
        {
            n=Integer.parseInt(st.nextToken());
            minx=Integer.parseInt(st.nextToken());
            maxx=Integer.parseInt(st.nextToken());
        }
        int i=1,j=2,c1=0,c2=0,e=0,o=0;
        
        while(n>0)
        {
            String s=br.readLine();
            StringTokenizer str=new StringTokenizer(s);
            
                while(str.hasMoreTokens())
                {
                    w=Integer.parseInt(str.nextToken());
                    b=Integer.parseInt(str.nextToken());
                }
                
                
                i=w*i+b;
                j=w*j+b;
                
                if(i%2==0)
                i=2;
                else
                i=1;
                
                if(j%2==0)
                j=2;
                else
                j=1;
            
                n--;
        }
            if(minx%2==0 && maxx%2==0)
            {
                o=(maxx-minx)/2;
                e=o+1;
            }
            
            else if(minx%2!=0 && maxx%2!=0)
            {
                e=(maxx-minx)/2;
                o=e+1;
            }
            
            else
            {
                e=((maxx-minx)/2)+1;
                o=e;
            }
                if(i%2==0)
                c1=e;
                else
                c2=e;
                
                if(j%2==0)
                c1=c1+o;
                else
                c2=c2+o;
                
                
                System.out.println(c1+" "+c2); 
                t--;
                
            }
        }
    }

Please tell where is the error.
I have divided the entire list into two sublist- each of odd and of even numbers. If the first number of the list is a spammer all the members are and if not, none are. Where is the fault?
I got the wrong answer even with int.

#include
using namespace std;

long neuralNetEvaluation(long w, long b, long x)
{
return (w*x+b);
}

int main()
{
long t; cin>>t;
while(t>0)
{
long N, minX, maxX;
cin>>N>>minX>>maxX;
long spam[2]={0};

long parameters[N][2];
long NN= N;
while(NN>0)
{
  cin>>parameters[N-NN][0]>>parameters[N-NN][1];
  NN--;
}
long first = (maxX-minX+1)/2;

  long x=minX;
  for(long i=0; i<N; i++)
  {
    x = neuralNetEvaluation(parameters[i][0], parameters[i][1], x);
  }
  if (x%2==0)
    spam[0]+=first;
  else
    spam[1]+=first;

  x= minX+1;
    for(long i=0; i<N; i++)
    {
      x = neuralNetEvaluation(parameters[i][0], parameters[i][1], x);
    }
    if (x%2==0)
      spam[0]+=(maxX-minX+1-first);
    else
      spam[1]+=(maxX-minX+1-first);
cout<< spam[0]<<endl;
cout <<spam[1]<<endl;
t--;

}

return 0;
}

Hii i don’t why am getting wrong error, my code is working fine for training input. Kindly help me.
Heres a link to my code
https://www.codechef.com/viewsolution/18626910

showing wrong answer but my code is correct giving same output
here is my code

#include
using namespace std;

int main(){
int t;
cin>>t;
while(t>0){
long n;
long long minx,maxx,w[n],b[n],ns=0,is=0,y;

cin>>n>>minx>>maxx;
for(int i=0;i<n;i++){
	cin>>w[i];
	cin>>b[i];
}
for(int i=minx;i<=maxx;i++){
		y=i;
		for(int j=0;j<n;j++){
			y=(w[j]*y)+b[j];
		}
	
		if(y%2==0){
			ns++;
		}
		else{
			is++;
		}
}
	t--;
cout<<ns<<"\t"<<is<<endl;

}
return 0;
}

showing wrong answer but my code is correct giving same output
here is my code

#include
using namespace std;

int main(){
int t;
cin>>t;
while(t>0){
long n;
long long minx,maxx,w[n],b[n],ns=0,is=0,y;

cin>>n>>minx>>maxx;
for(int i=0;i<n;i++){
	cin>>w[i];
	cin>>b[i];
}
for(int i=minx;i<=maxx;i++){
		y=i;
		for(int j=0;j<n;j++){
			y=(w[j]*y)+b[j];
		}
	
		if(y%2==0){
			ns++;
		}
		else{
			is++;
		}
}
	t--;
cout<<ns<<"\t"<<is<<endl;

}
return 0;
}

Any idea why the following timeout’s:

#include <stdio.h>

int main(void) {
// your code goes here
int num_test, minX, maxX,num_NN, cnt_nospam, cnt_spam, result_1, result_2;
int w[100000], b[100000];
scanf("%d", &num_test);
while(num_test–){
cnt_nospam=cnt_spam=0;
scanf("%d%d%d",&num_NN,&minX, &maxX);
for(int i = 0; i<num_NN; i++){
scanf("%d%d",w+i,b+i);
}
while(minX<=maxX){
result_1 = minX;
result_2 = maxX;
for(int j =0; j<num_NN; j++){
result_1 = result_1w[j]+b[j];
result_2 = result_2
w[j]+b[j];
}

        if((result_1%2) == 0){
            cnt_nospam++;
        }
        else{
            cnt_spam++;
        }
        if(minX<maxX){
            if((result_2%2) == 0){
            cnt_nospam++;
        }
        else{
            cnt_spam++;
        }
            
        }
        
        minX++;
        maxX--;
    }
    
    printf("%d %d \n",cnt_nospam,cnt_spam);
}
return 0;

}

@aam2kor: you need to take Y%2 each time you calculate as the large values will take more time to compute after each loop, the value of final output becomes larger than before and to ease the computation, we need to take %2 even time

1 Like

why my code isn’t working pls. help me out!!!.
https://www.codechef.com/viewsolution/24943219

With this code the time it takes it 2.01 sec how can i optimize the code to bring it down
#include
#include<stdio.h>
using namespace std;

int main(){
int t;
scanf("%d",&t);
while(t–){
long long int n,minx,maxx;
scanf("%lld %lld %lld",&n,&minx,&maxx);
printf("\n");
vector<pair<long long int ,long long int>> v(n);
for(int i=0;i<n;i++){
long long int w=0,b=0;
scanf("%lld %lld",&w,&b);
printf("\n");
v.push_back(make_pair(w,b));
}
long int spam=0,nonspam=0;
for (long long int x=minx;x<=maxx;x++){
long long int sum=0;
for(auto it=v.begin();it<v.end();it++){
sum+=(it->first*x)+it->second;
}
if(sum%2==0)nonspam+=1;
else spam+=1;
}
printf("%ld %ld \n",nonspam,spam); }
}

Can someone help me out what case is failing for this code ?

https://www.codechef.com/viewsolution/30979301

@usaxena95
PLS Help My code is giving WA
https://www.codechef.com/viewsolution/33139606

please tell me why this is giving me the wrong answer on submitting,where as in other compiler it is running smooth and giving me the correct output.

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
try{
// youir code goes here
BufferedReader inp = new BufferedReader (new InputStreamReader(System.in));
int t= Integer.parseInt(inp.readLine());
while(t>0)
{ int n = Integer.parseInt(inp.readLine());
int min = Integer.parseInt(inp.readLine());
int max = Integer.parseInt(inp.readLine());
int w = Integer.parseInt(inp.readLine());
int b = Integer.parseInt(inp.readLine());
int spammer=0,nonspammer=0;
while(min<=max)
{ int i=min;

	        for(int p=0;p<=n;p++)
	        {
	           
	           int y=w*i+b;
	           i=y;
	         
	           }
	           if(i%2==0)
	           {
	           spammer++;
	           }
	           else{
	        nonspammer++;   
	           }
	        min++;
	       
	        
	    }
	    System.out.print(nonspammer+" "+spammer);
	    t--;
	}
   }
   catch(Exception e)
   {
       
   }
}

}

its giving WA please see this once !!!

#include<bits/stdc++.h>
using namespace std;
#include
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define int long long
#define mod 1000000007
#define pb push_back

int32_t main()
{
fast
#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
#endif

int t;
cin>>t;
while(t--)
{
    bool ans=true;
    int n,k,x,y,c=0,p=0;
    std::vector<int> v;
    int mi,ma;
    int w,b;
    cin >> n>>mi>>ma;
    y=mi;
    x=mi++;
    
    while(n--)
    {
        
        cin>>w>>b;
        mi=(mi*w)+b;
        x=(x*w)+b;
    }

    if(mi%2==0 && x%2==0)
         cout<<ma-y+1<<" "<<"0"<<endl;
    else if(mi%2==1 && x%2==1)
        cout<<"0"<<" "<<(ma-y)+1<<endl;

    else if((x%2==1 && mi%2==0) ||(x%2==0 && mi%2==1))
        cout<<(ma-y+1)/2<<" "<<(ma-y+1)/2<<endl;





}

}

Please either format your code or (better!) link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

obviously n must be <=100000 which means u can only use 2 loops… i mean one loop inside the loop of test cases…

Does anyone have an idea, why this solution isn’t working ?

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner scan = new Scanner(System.in);

	int cases = scan.nextInt();
	
	for (int i = 0; i < cases; i++) {
	    int N = scan.nextInt();     // Number of hidden layers
	    int minX = scan.nextInt();  /* user */
	    int maxX = scan.nextInt();  /* ids  */
	    
	    int[] arrW = new int[N];
	    int[] arrB = new int[N];
	    
	    // To record all the layers
	    for (int j = 0 ; j < N ; j++ ) {
	        arrW[j] = scan.nextInt();
	        arrB[j] = scan.nextInt();
	        // System.out.println(arr[j][0] + " " + arr[j][1]);
	    }
	    
	    int spammers = 0;
	    
	    for (int j = minX; j <= maxX; j++) {
	        long y = j;
	        for (int k = 0; k < N; k++) {
	            y = arrW[k]*y + arrB[k];
	            arrW[k] = arrW[k]%2;
	            arrB[k] = arrB[k]%2;
	        }
	        
	        if (y%2 == 1) {
	            spammers++;
	        }
	    }
	    
	    System.out.println((maxX - minX + 1 - spammers) + " " + spammers);
	    
	}
}

}

This is my code, giving the right output but it is exceeding the time limit can someone help to resolve this issue of time limit?

long long  t;
	cin>>t;
	for(long i=0;i<t;i++){
	    long long n,min,max;
	    cin>>n>>min>>max;
	    long p=max-min+1;
	    long neurals[(int)p];
        for(long k=0;k<p;k++){
            neurals[(int) k]=k+1;
        }
        for(long j=0;j<n;j++){
            long wi,bi;
            cin>>wi>>bi;
            for(int x=0;x<p;x++ ){
                neurals[x]=(wi*neurals[x]+bi);
            }
        }
        int even=0,odd=0;
        for(int j=0;j<p;j++){
            if(neurals[j]%2==0)
                even++;
            else
                odd++;
        }
        cout<<even<<" "<<odd;
	}
	return 0;