CHN15A - Editorial

PROBLEM LINK:

Contest
Practice

Author: Arjun Arul
Tester: Kevin Atienza
Editorialist: Kevin Atienza

DIFFICULTY:

Cakewalk

PREREQUISITES:

Modulo operation

PROBLEM:

There are N minions, each having a characteristic value. Each minion is transmogrified. The transmogrifier adds an integer K to the minion’s characteristic value. If a minion’s new characteristic value is divisible by 7, then it will have Wolverine-like mutations.

How many of them become Wolverine-like after all of them are transmogrified?

EXPLANATION:

This is the easiest problem in the contest, so straightforward solutions will likely pass.

Simply loop through all N characteristic values, counting the numbers which when increased by K becomes divisible by 7. Checking whether a number is divisible by another number can be done with the modulo operation, written as a % b in most programming languages (including C++ and Java). Here are a few implementations:

C++:

#include <iostream>
using namespace std;

int main() {
    int cases;
    cin >> cases;
    while (cases--) {
        int n, k, ans = 0;
        cin >> n >> k;
        while (n--) {
            int a;
            cin >> a;
            if ((a + k) % 7 == 0) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

Java:

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int cases = sc.nextInt();
        for (int cas = 0; cas < cases; cas++) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int ans = 0;
            for (int i = 0; i < n; i++) {
                int a = sc.nextInt();
                if ((a + k) % 7 == 0) ans++;
            }
            System.out.println(ans);
        }
    }
}

Common errors

This is the easiest problem in the contest. However, that doesn’t mean nothing can go wrong with your submission. Lots of things can go wrong, from major problems down to simple gaffes such as choosing the wrong language while submitting! You must be prepared to handle these mistakes, because debugging is part of a programmer’s life, and in fact usually takes more time than actual coding.

One common error is forgetting to initialize variables, as in the following:

#include <iostream>
using namespace std;

int main() {
    int cases, n, k, a, ans = 0;
    cin >> cases;
    while (cases--) {
        cin >> n >> k;
        while (n--) {
            cin >> a;
            if ((a + k) % 7 == 0) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

This one is also quite misleading because the line ans = 0 makes you think that the ans variable is being initialized properly. However, it’s outside the loop, so it doesn’t reset to 0 for the following test case! Consequently, your program will most likely get wrong answers for all but the first test case. Quite a few participants made this mistake!

One way to detect this is possibly to add an identical test case in your sample input. If the answers you got are different, then most likely something’s wrong. Also, to be sure, declare variables only on scopes they’re needed, as shown in the examples above.

Another error is allocating an array too small for the input sequence. Remember that when given constraints such as N \le 100, judges will most likely test out extremes, so allocating an array of size 10 will not be enough. Some participants also made this mistake and got a “Runtime error” verdict.

If you want to be extra cautious, you could allocate a larger array, say 111 or even 300. But in this particular problem, you can forgo allocating any array altogether and simply calculate the answer on the fly (throwing away each input value after using it), as is shown in the examples above. Note however that you can’t do that in most problems.

Readability

Another way to help you debug your code is to ensure your code is readable and clear. This includes formatting your code properly and possibly adding a few comments. In general, try to put yourself in your teammate’s shoe and see if he/she will understand the code just by reading it, without you explaining it.

Also, remember, simplicity is important. There’s no need for very advanced programming patterns for something as simple as this. If you check the examples above, you find that they’re simple and straight to the point, and it also has the desirable consequence of being clear and readable.

Miscellanea

Here we mention other common errors and things to remember.

  • Don’t forget to print a newline at the end of each test case! To be sure, try it yourself first with a couple of test cases and see if they output as expected. Command line tools such as diff or fc are helpful for this task and guards against manual checking which is unreliable.
  • Use zero-indexing. It’s idiomatic in many languages including C, C++ and Java. Even though some problems use one-indexing, it’s usually helpful to convert to zero indexing in most languages, especially if you’re gonna use some builtin functions that assume zero indexing.
  • Don’t print unnecessary stuff like "Please enter the number of test cases: ". These are considered part of your output and so your solution will be marked wrong. The goal is to exactly match the contents of the judge’s output file. Note that this includes extra lines and spaces, etc.!
  • You don’t need to check whether 1 <= n && n <= 100, etc. because these constraints are guaranteed. You just assume that they are true and try to solve the given problem.
  • Some submissions read the input as “k n” instead of the correct “n k”. This would most likely mean that you’re reading the input incorrectly and you won’t get a correct answer. In general, pay careful attention to the problem statement and input format.
  • Make sure that your program works as expected by trying out a couple of test cases. In particular, don’t submit code that doesn’t compile. It will cost you penalty points if you eventually solve the problem (not to mention real time lost).
  • Submit the source code, not the compiled output!

Language-specific things

  • When copy-pasting Java code to be submitted to CodeChef, use Main as your public class name (as stated in Sample Solutions | CodeChef ). It’s because Java requires the file name and public class name to be the same, but since you copy-pasted code, CodeChef doesn’t know the public class name and could have a harder time figuring it out from code. It’s easier to just assume it’s something, say, Main.
  • In C++, always return 0 in the main function, because returning something else means you’re signalling an error, and even if your code outputs correctly, you might receive a “Runtime error” verdict.

Contest-specific stuff

These are things usually good to be done during contests but are worth keeping in mind that they are considered bad practice in industry code.

  • In Java, there are times when some methods have checked exceptions, such as IOException for BufferedReader.readLine(), requiring you to handle them with bulky try-catch blocks. In these cases, you can just declare throws Exception in your main method. This is very much not recommended in production code, but in a contest, it’s very convenient.
  • In Java, instead of importing each class separately, you can import everything from a single package using “import *”, e.g. import java.util.*;. Of course this is not recommended at work because it makes it harder to keep track of where each used class is defined, but during contests you don’t really need to worry about it.
  • Instead of having to type std::cin all the time, you can add using namespace std in your C++ code so you can just use cin. It’s also considered bad practice in real life. Nonetheless, it’s also convenient, makes code a bit clearer, and can cut down typing time. Even then, people using it must be wary, because problems such as this and this might occur.

Time Complexity:

O(N)

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester

1 Like

import java.util.;
import java.lang.
;
import java.io.*;

/* 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
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
int n=sc.nextInt();
int k=sc.nextInt();
int count=0,a;
int b[]=new int[n];
for(int i=0;i<t;i++)
{
for(int j=0;j<n;j++)
{
a=sc.nextInt();
b[j]=a+k;
if(b[j]%7==0)
{
count++;
}
}
}
System.out.println(count);
}
}

/*


**************** Ankit Raj ****************
********** Chandigarh University **********
*********** https://ankitraj.in ***********


********** START OF THE PROGRAM ***********
*/

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

ll a,b,c,d=0,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z;

int main()
{
cin>>t;
akka(i,t)
{
cin>>n>>a;
while(n–)
{
cin>>c;
b=c+a;
if(b%7==0)
{
d++;
}
}
cout<<d<<endl;
}

cerr<<"Time Elapsed "<<(double)clock()/CLOCKS_PER_SEC <<" s"<<endl;

}
/* ********** END OF THE PROGRAM ***********
*/

What is wrong with my solution??

1 Like

I found another solution.
It is much the same, but faster. The difference is that you don’t need to keep adding K to each element.
Just figure out what should be the remainder r such that had K been added, the remainder would have been 0.
The formula is: r = 7 - (K%7)
One exception to this formula:
If K is divisible by 7, r will be equal to 7. It this case, it should be changed to 0.

T = input()
for Q in range(T):
	R = 0
	#Input:
	N,K = map(int,raw_input().split() )
	A = map(int,raw_input().split() )
	# Finding value of r
	r = 7-(K%7) 
	if r == 7:
		r = 0
	# Checking each elements
	for i in A:
		if i % 7 == r:
			R += 1
	#output
	print R