Unofficial editorial December long challenge

editorial
,
23

Well, the problem states that every red marble should only have green marbles in four adjacent cells. Yes, problem doesnt mention chess board, but as i identified the pattern, i saw it similar to chess board. Where a white cell always has four black adjacent cells and same for black cells.

I mentioned chess board to make myself entirely clear. :slight_smile:

24

As we move from, say N= 2 to N=3,

ans[3] = ans[2] + (4+5)(for last row except last element) + (4+5)(for last column except last element) +2*3

ans[3] = ans[2] + 2*(sum[5]-sum[3]) + V[2*3].

ans[i] = ans[i-1] + 2*(sum[2i-1]-sum[i]) + V[2i]

Cheers

25

Shouldn’t sum[1] be 1 instead of 0??

That’s the only error i guess.

26

@taran_1407 no it’s just that the array need’s to be long long thanks by the way a more memory efficient is possible solution:- CodeChef: Practical coding for everyone

27

@taran_1407
i have edited my post.

28

This is same as (i+j)%2 == 1 (in bitwise).

This condition automatically make adjacent cells of different colors.

29

Often you would find thatwhenever there are 1e5 test case, you need to answer test cases in O(1) or atmost O(logN) time. For that, it’s very often you preprocess all answers, or enough to find all answers.

30

Nice one!!

31

I don’t think there should be such a problem, but you can refer to this memory efficient solution if you can declare an array of size 1000000.

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

32

There are two errors in your solution…

First, you were not reading all the input lines. You were just reading the first line. Try putting a loop and break the loop at the end of the input file.

Second, you have commented out a portion of your solution from line 5-18

33

Well, it is not always necesaary that you need to preprocess the answer. Rather, take CHEFUNI of current long challenge. It too require O(1) answer, because T upto 1e5. But in that problem, we cannot even store or calculate answers for all possible values of X, Y Z, A,B and C.

Well, preprocessing often is easier but have time and memory constraints. If preprocessing is feasible with given constraints, go with preprocessing, else prefer constant time solutions (comparatively tougher than preprocessed solution as i feel).

So, it depends upon problem and constraints.

34

Got it!.
I was doing it only for the first line.And after I got a wrong answer, I commented the code to atleast get the 1st subtask right.Which again failed coz i was just processing first line.

35

You can visualise it as a 2-D matrix rather than a chessboard. These patterns become obivous after some practice on similar problems.

36

Bhai… I guess u are a bit late @vijju123 :smiley:

He asked this on 11th DEC :P.

1 Like
37

Ofcoursw i can check, but i would recommend u to solve this again, using the way i tell u below…

First make a 2D character array, and take all input.

Now, solve this for first case, that is, if (i+j)%2 == 0, color should be green, otherwise red, and calculate cost

Now, solve this for second case, that is, if (i+j)%2 == 0, color should be red, otherwise green, and calculate cost.

Output minimum of both.

Idea Use separate loops whenever u feel it complicated…:slight_smile:

38

@dinesh2193 you first initialize 1D array

string a[n]

and then you doing this a[i][j] you didn’t initialize a 2d array and as taran said try to separate the for loops when getting the input and solving the problem

39

yeah ,i got the answer for both the above methods.but i had not used any extra space for creating a 2D array(for the above two cases) but used a single variable which can optimise the solution.but it didnt get accecpted

40

I want you to to solve the problem the way i mentioned, and then rewrite the solution in the way you want, That’s how we all learn…

PS: Don’t mind using extra space, as long as it gets you an AC, and then reduce space complexity.

I hope you don’t mind that. :slight_smile:

41

okk
thanks

42

Why my solution is giving WA??

void solve(string s){

ll score_a = 0, score_b = 0;

ll shoot_a = 5, shoot_b = 5;

for(int i = 0; i<=9; i+=2){

    if(s[i]=='1'){

        shoot_a--;

        score_a++;

    }

    else shoot_a--;

    if(s[i+1]=='1'){

        shoot_b--;

        score_b++;

    }

    else shoot_b--;

    if(score_a > shoot_b+score_b){

        cout<<"TEAM-A "<<i+2<<endl;

        //break;

        return;

    }

    if(score_b > shoot_a+score_a){

        cout<<"TEAM-B "<<i+1<<endl;

        //break;

        return;

    }

}

int flag = 0;

for(int i=10; i<=19; i+=2){

    if(s[i]=='1' && s[i+1]=='0'){

        if(score_a>=score_b){

            flag=1;

            cout<<"TEAM-A "<<i+2<<endl;

            //break;

            return;

        }

        else if(score_a < score_b) score_a++;

    }

    else if(s[i]=='0' && s[i+1]=='1'){

        if(score_b>=score_a){

            flag=1;

            cout<<"TEAM-B "<<i+1<<endl;

            //break;

            return;

        }

        else if(score_b < score_a) score_b++;

    }

    else if(s[i]=='1' && s[i+1]=='1'){

        if(score_a == score_b){

            score_a++;

            score_b++;

        }

        else if((score_a>score_b) && (score_a-score_b==1)){

            flag=1;

            cout<<"TEAM-A "<<i+2<<endl;

            //break;

            return;

        }

        else if((score_a>score_b) && (score_a-score_b>1)){

            flag=1;

            cout<<"TEAM-A "<<i+1<<endl;

            //break;

            return;

        }

        else if((score_b>score_a) && (score_b-score_a==1)){

            flag=1;

            cout<<"TEAM-B "<<i+2<<endl;

            //break;

            return;

        }

        else if((score_b>score_a) && (score_b-score_a>1)){

            flag=1;

            cout<<"TEAM-B "<<i+1<<endl;

            //break;

            return;

        }

    }

}

if((score_a==score_b) && flag==0 ) cout<<"TIE"<<endl;

}

int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//this is fast I/O (inputput output) use header file <cstdio>

string s;

while(cin>>s){

    solve(s);

}

return 0;

}