You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

This question is marked "community wiki".

asked 13 Jan '18, 16:21

usaxena95's gravatar image

7★usaxena95
2311313
accept rate: 0%

edited 20 Feb '18, 16:59

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

amstan's gravatar image

4★amstan
111
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; }

link
This answer is marked "community wiki".

answered 01 Mar '18, 15:12

satyam543's gravatar image

2★satyam543
1
accept rate: 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

link

answered 22 May '18, 09:35

bhaunda_123's gravatar image

1★bhaunda_123
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; }

link
This answer is marked "community wiki".

answered 23 Aug '18, 12:27

nihal09's gravatar image

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

link
This answer is marked "community wiki".

answered 23 Aug '18, 12:27

nihal09's gravatar image

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;

}

link

answered 01 Oct '18, 16:41

aam2kor's gravatar image

2★aam2kor
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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