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

CodeChef-DSA-learners
, , , , ,
7

I cannot access the link (Access Denied), why? because you cannot share your solution link from an ongoing contest.
Use pastebin to share the solution.

8
9

You program is giving wrong answer for the following test-cases:

2
5 11 3
167 181 479

For case 5 11 3 you code is giving NONO as output.

Output should be:

NO
YES

This should help you debug your code.

10

why the answer for 2 9 5 is yes

and

1 ≤ d0 ≤ 9
0 ≤ d1 ≤ 9

13

Coin Flip Solution is O(1) which is similar approach but slightly different from the editorial -

#include <iostream>
#include <cmath>
using namespace std;

#define datatype long long int

int main()
{
datatype testcases;
cin>>testcases;
while(testcases--)
{
    datatype games;
    cin>>games;
    while(games--)
    {
        datatype initialState, numberOfRounds, prediction;
        cin>>initialState>>numberOfRounds>>prediction;

        int count= 0;
        
        if(initialState == 1)
        {
            if(prediction == 1 || numberOfRounds % 2 == 0)
                count= numberOfRounds/2;
            else
                count= numberOfRounds/2+1;
        }
        else
        {
            if(prediction == 1 && numberOfRounds % 2 != 0)
                count= numberOfRounds/2+1;
            else
                count= numberOfRounds/2;                
        }

        

        cout<<count<<endl;
    }
}
return 0;
}
14

Well you can combine the different cases into one because the answer can be either of the two i.e. n/2 or n/2 + 1.
It does not make significant difference between the Editorial Vs Solution code as long as both of them have same time and space complexity which in this case is O(1).

15

In problem statement, K is zero-indexed but digits are from 0 to k-1. It means in your first test case-
2 9 5
K is equal to 2 which means it has digits from d0 to d(k-1) => d(2-1) => d1.
So there are only 2 digits 9 and 5, and as 9+5=14 is not divisible by 3 so the answer should be NO.
You can check 2nd test case given in the problem statement is-
5 3 4
the number N is 34748 which has 5 digits as equal to given k. So i suggest you should yourself read the problem statement carefully.

1 Like
16

Thanks for pointing out a bug in the program I will update it, but however the solution is accepted by Online Judge even though it is giving wrong answer for the case 2 9 5

17

I guess this must be the reason I’m not getting AC in the problem.

18

Please tend to share submission link instead of pasting code.

19

If you have not solved the problem till now, what you can do is, write a brute force solution and run it on the possible test-cases where you think your optimised solution can give wrong answers. You will know what you are doing wrong.

20

what is wrong in this code

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

1 Like
21

Can you format your code or share the link, moreover can you tell me which problem you are trying to solve?

22

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.;
import java.io.;

class Rextester
{
static class Reader
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;

public Reader()
{
  din = new DataInputStream(System.in);
  buffer = new byte[BUFFER_SIZE];
  bufferPointer = bytesRead = 0;
}

public Reader(String file_name) throws IOException
{
  din = new DataInputStream(new FileInputStream(file_name));
  buffer = new byte[BUFFER_SIZE];
  bufferPointer = bytesRead = 0;
}

public String readLine() throws IOException
{
  byte[] buf = new byte[64]; // line length
  int cnt = 0, c;
  while ((c = read()) != -1)
  {
    if (c == '\n')
    break;
    buf[cnt++] = (byte) c;
  }
  return new String(buf, 0, cnt);
}

public int nextInt() throws IOException
{
  int ret = 0;
  byte c = read();
  while (c <= ' ')
  c = read();
  boolean neg = (c == '-');
  if (neg)
  c = read();
  do
  {
    ret = ret * 10 + c - '0';
  } while ((c = read()) >= '0' && c <= '9');

  if (neg)
  return -ret;
  return ret;
}

public long nextLong() throws IOException
{
  long ret = 0;
  byte c = read();
  while (c <= ' ')
  c = read();
  boolean neg = (c == '-');
  if (neg)
  c = read();
  do {
    ret = ret * 10 + c - '0';
  }
  while ((c = read()) >= '0' && c <= '9');
  if (neg)
  return -ret;
  return ret;
}

public double nextDouble() throws IOException
{
  double ret = 0, div = 1;
  byte c = read();
  while (c <= ' ')
  c = read();
  boolean neg = (c == '-');
  if (neg)
  c = read();

  do {
    ret = ret * 10 + c - '0';
  }
  while ((c = read()) >= '0' && c <= '9');

  if (c == '.')
  {
    while ((c = read()) >= '0' && c <= '9')
    {
      ret += (c - '0') / (div *= 10);
    }
  }

  if (neg)
  return -ret;
  return ret;
}

private void fillBuffer() throws IOException
{
  bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  if (bytesRead == -1)
  buffer[0] = -1;
}

private byte read() throws IOException
{
  if (bufferPointer == bytesRead)
  fillBuffer();
  return buffer[bufferPointer++];
}

public void close() throws IOException
{
  if (din == null)
  return;
  din.close();
}

}

public static void main(String[] args) throws IOException
{
Reader in=new Reader();
int test=in.nextInt();
while(test-- >0){
int k=in.nextInt();
int d0=in.nextInt(), d1=in.nextInt();
String D2=d0+“”+d1+“”+((d0+d1)%10);
//System.out.println(D2);
int d2=Integer.parseInt(D2);
String D3=d2+“”+((d0+d1+d2)%10);
//System.out.println(D3);
int d3=Integer.parseInt(D3);
//check for k<=3
if(k==2){
if((d0+d1)%3==0)
System.out.println(“YES”);
else
System.out.println(“NO”);
}
else if (k==3) {
if((d2)%3==0)
System.out.println(“YES”);
else
System.out.println(“NO”);
}
else if (k==4) {
if((d3)%3==0)
System.out.println(“YES”);
else
System.out.println(“NO”);
}
else if (d3%10==0) {
if(d2%3==0)
System.out.println(“YES”);
else {
System.out.println(“NO”);
}
}
else{
int skip=8+6+2+4;
int skp[]={8, 6, 2, 4};
long sum=d0+d1+d2%10;
//System.out.println(sum);
k=k-4;int index=-1;
if(d3%10==8)
index=0;
if(d3%10==6)
index=1;
if(d3%10==2)
index=2;
if(d3%10==4)
index=3;
int s= k/4;
int m= k%4;
sum= sum+s*skip;
//System.out.println(index);
for(int i=0;i<=m;i++){
sum+=skp[(index)%(skp.length)];
//System.out.println("–> "+sum);
index++;
}
//System.out.println("sum: "+sum);
if(sum%3==0)
System.out.println(“YES”);
else {
System.out.println(“NO”);
}
}
}
}
}

I have no idea why am I getting WA in multiple three. Please help

23

Please format your code, and explain in brief what was your logic?

However you can debug your code with the test cases provided here Competitive-Programming/Code-Chef/Multiples-of-3/test-cases at master · strikersps/Competitive-Programming · GitHub which will help you find the bug in your code.

24

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

25

my solution answer is correct but unable to submit
https://www.codechef.com/viewsolution/30963128

26

I cannot access the link (Access Denied), why? because you cannot share your solution link from an ongoing contest.
Use pastebin to share the solution.

27
28

Hi @striker22. Thanks for the editorials. I was able to solve the first 8 problems comfortably. But the MULTHREE too me a lot of time and I also needed to see your code to solve it. Is it bad for a beginner(no exposure to modular arithmetic) to be not able to solve that problem within a day ? I put my best efforts to complete it without outside help but was not able to.
BTW, thanks for the code on GitHub it saved my day :smiley:

1 Like