Editorial for Problems of Codechef-DSA-Learning-Series: 1-Complexity Analysis + Basics Warm Up

  • I applied a similar logic related to the pattern of 2,4,8,6.
  • I ran a loop till the first occurrence of digit ‘2’ in the number and computed the sum till that position, for the rest of the digits(if any) i find the sum directly using sum of 2,4,8,6 and dividing the remaining digits by 4 and later modulo to find if anythings left.
  • it is still giving a TLE. i dont understand why.

Here is a link to my code :
https://www.codechef.com/viewsolution/32334578

Hi,

Can you tell me what’s wrong in this code because it seems to be correct. But getting Runtime Error after submission. @striker22

My Java Code:

static long playGame(int ini, int n, int q) {
        long headctr = 0, tailCtr = 0;
		char[] charr = new char[n];
		
        if(ini == 1)
            Arrays.fill(charr,'H');
        else
			Arrays.fill(charr,'T');
			
        for(int i=0; i<n; i++) {
            for(int j=0; j<=i; j++) {
                if(charr[j] == 'H')
                    charr[j] = 'T';
                else
                    charr[j] = 'H';
            }
		}
		for(int i=0; i<charr.length; i++) {
			if(charr[i] == 'H') headctr++;
			else tailCtr++;
		}
        return (q==1)?headctr:tailCtr;
    }

Thanks :slightly_smiling_face:

Can you share your complete code?

1 Like

As mentioned earlier I am getting RTE for this code. @striker22

Complete Code:

import java.util.*;

import java.io.*;

class CoinFlip {

    static long playGame(int ini, int n, int q) {

        long headctr = 0, tailCtr = 0;

        char[] charr = new char[n];

        

        if(ini == 1)

            Arrays.fill(charr,'H');

        else

            Arrays.fill(charr,'T');

            

        for(int i=0; i<n; i++) {

            for(int j=0; j<=i; j++) {

                if(charr[j] == 'H')

                    charr[j] = 'T';

                else

                    charr[j] = 'H';

            }

        }

        for(int i=0; i<charr.length; i++) {

            if(charr[i] == 'H') headctr++;

            else tailCtr++;

        }

        return (q==1)?headctr:tailCtr;

    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        while(t-- > 0) {

            int ngames = sc.nextInt();

            for(int i=0; i<ngames; i++) {

                int initial = sc.nextInt(), roundCoins = sc.nextInt(), q = sc.nextInt();

                System.out.println(playGame(initial, roundCoins, q));

            }

        }

    }    

}

I think you are getting Runtime Error because the value of N can be as large as 10^9 which I don’t think JAVA will be able to allocate.

When I ran your program I get the following message for the given test-case:

1
1
1 1000000000 1
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at CoinFlip.playGame(coin_flip.java:11)
	at CoinFlip.main(coin_flip.java:67)

NOTE: I am not a JAVA programmer, so I am not sure, but maybe that is the sure bug in your program.

Test-Cases: The following are the test-cases on which you can run your program, if you get the correct output, then you can be sure that your solution is correct.

Input:

7
2
1 5 1
1 5 2
2
1 1 1
2 1 1
2
1 3 1
2 3 1
2
1 4 1
2 4 1
5
2 5 1
2 5 2
1 1 2
2 1 2
2 4 2
1
1 1000000000 1
1
1 1000000000 2

Correct Output:

2
3
0
1
1
2
2
2
3
2
1
0
2
500000000
500000000

However, there is a O(1) time solution to the problem which I have already explained in the post Editorial for Problems of Codechef-DSA-Learning-Series: 1-Complexity Analysis + Basics Warm Up

1 Like

Thanks for your help :slightly_smiling_face:

Here is my code of CARVANS. Please tell me about where I am wrong.

try:
    a = int(input())
    for i in range(a):
        e = 0
        b = int(input())
        c = list(map(int, input().split()))
        if(len(c) == 1):
            print(1)
        else:
            for i in range(len(c)-1):
                if(i == 0):
                    e += 1
                
                elif(c[i] < c[i-1] and c[i] < c[i+1]):
                    e += 1
            print(e)
            
except EOFError:
    pass

Format your code first as the forum software has messed it up. Refer to the following guide:

Can you please tell me whats wrong in this solution.

Your program is giving WA for the following case:

Test-Case:

5
12 45 23 33 120

Your Code Output:

2

Correct-Output:

1

Hope this helps you figure out your mistake.

Yup, thanks @striker22

My Solution (CodeChef: Practical coding for everyone) for MULTHREE is reporting NZEC. Please help me!

You are not handling the case when K = 2.

However even after you handle K = 2 case, your logic is not correct.

Your program even after handling the case for K = 2 is giving WA for the following test-cases:

Test-Cases:

5
864204528303 5 4
472253834783 7 7
636817857948 6 6
812926620342 5 3
329423582819 1 0

Your Program Output:

NO
YES
NO
YES
NO

Correct Output:

YES
NO
NO
NO
YES

I suggest you to have a look on the editorial for the problem as explained here, and update your source-code accordingly and then run on the test-cases mentioned here.
If you are getting correct answers for all the test-cases then you can claim that your solution is correct.

Thanks a lot for the help. It worked!
Working solution is here

I’m not able to understand why I’m getting wrong answer for my submission. I’ve tripled checked my logic and have referred to a detailed tutorial on geeksforgeeks. Here’s the link:

Following is the link to my submission:
https://www.codechef.com/viewsolution/33043153

Please help me understand where I’m going wrong.

In the given constraints, d0 and d1 are less than/equal to 9, but in some test cases, they are greater than 9. Why?

1 Like

Can you please explain the formula written in the first line of this picture ? @striker22

Hi, I am stuck at the multiple of 3 problem.
my thought process behind the solution is :
case 1-- if (d0 +d1)%3 ==0 then the number will be a multiple of 3.
case 2 – if (k-3)*sum%3 ==0 then also the number will be will be multiple of 3
( case 2 can happen because of any of the two a-- k is multiple of 3 b-- sum is multiple 3.)
also this code works fine on the given test cases, but is giving WA for the solution.

here’s the link for my solution : CodeChef: Practical coding for everyone

please help,
thanks

I am getting Wrong answer. I tried something different. Is my solution approach, wrong? Any suggestion or help will be appreciated. Thank you :innocent: :grin:

#include<bits/stdc++.h>
using namespace std;

bool solve(){
    ll k,d0,d1;
    cin>>k>>d0>>d1;
    int d2 = d0 + d1;

    //corner case
    if(k==2){
        if((d0*10+d1)%3==0)
            return true;
        return false;
    }

    //corner case
    if(k==3){
        if((d0*100+d1*10+d2)%3==0)
            return true;
        return false;
    }


    vector<int> pattern; // pattern 
    /*
    example : 13 8 1
    the pattern we are looking to built is
        pattern [ 2 2 1 2 1 1 0  1  0  0  2   0 ]
    remainder of  4 5 6 7 8 9 10 11 12 13 14  15 th digit,
    so, since the number ought to be 13(k) we check the 13th digits remainder.
    */

    int rem = (d0*100+d1*10+d2)%3;
    for (int i = 0; i < 12; i++)
    {
        d2 = (d2*2)%10;
        rem = (rem*10 +d2)%3;
        pattern.push_back(rem);
    }
    // debug(pattern)

    /*
    Since the pattern is repeating 
    [ 2 2 1 2 1 1 0 1 0 0 2 0 2 2 1 2 1 1 0 1 0 0 2 0 ]
    it start to repeat at every 12 remainder,
    so (k-3-1)%12 since we reduced the first 3 remainders which is not 
    repetitive.  also we have checked in the corner cases.
    */

    if(pattern[(k-3-1)%12]==0) return true;
    return false;
}
int main() {
    fastio();
    ll t=1;
    cin >> t;
    while(t--) {
        if(solve())
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}

I’m sorry i am new to cp but what does " the constraints imposed on K i.e. 1 <= K <= 10^{12}, means you cannot go for the O(K)O(K) approach." mean in the problem “Multiple of 3” ?