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.
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.
@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
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); }
}
/* 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;
#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
/* 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);
}
}