×

# SPAMCLAS - Editorial

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.

This question is marked "community wiki".

2311313
accept rate: 0%

19.8k350498541

 0 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--; } } }  link This answer is marked "community wiki". answered 24 Jan '18, 04:04 4★amstan 11●1 accept rate: 0%

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 <iostream>

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

This answer is marked "community wiki".

1
accept rate: 0%

 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 answered 22 May '18, 09:35 1 accept rate: 0%

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

# include<iostream>

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

This answer is marked "community wiki".

2★nihal09
1
accept rate: 0%

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

# include<iostream>

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

This answer is marked "community wiki".

2★nihal09
1
accept rate: 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_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;


}

2★aam2kor
1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×3,764
×94
×24
×14

question asked: 13 Jan '18, 16:21

question was seen: 2,693 times

last updated: 01 Oct '18, 16:41