SPAMCLAS - Editorial

editorial
, , , ,
1

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.

2

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--;
                
            }
        }
    }
3

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;
}

4

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

5

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;
}

6

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;
}

7

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_2w[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;

}