SEVENSEG - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Erfan Alimohammadi
Tester: Aleksa Plasvic
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Bitmasks, Implementation.

PROBLEM:

Given a digital display where each single decimal digit is represented by seven segments. Some of the segments are broken. We are also given N conditions, where each condition specifies that when we try to show value x, exactly y segments switch to on state. We need to find the minimum and the maximum number of segments which can be broken so that all the conditions are satisfied, or print invalid if no possible set of broken segments can satisfy the given conditions.

QUICK EXPLANATION

  • Since there are seven segments and each segment can be either broken or non-broken, there can be 2^7 different compositions.
  • For checking each configuration, we can check manually whether the number of segments in on state is exactly same as given in condition for all digits. If the configuration is valid for each digit, we can consider the number of broken segments in our minimum and maximum and then finally print these values. In case we do not find any valid configuration, we should print Invalid.
  • For ease of implementation, bitmasks can be used, each bit denoting one of the seven segments and bit being on or off tells the state of the segment.

EXPLANATION

Let us denote configuration of the display as assigning each segment either working or broken. Since each segment can be in one of the two states, the total number of configurations can be 2^7 = 128.

Since the number of configurations is small, we can try each configuration and check if this configuration is valid or not. If it is valid, we can consider the number of broken segments and print the minimum and maximum of this value over all valid configurations.

Now, the only part left is, that how to check whether a given configuration is valid for the given set of conditions.

Let us denote each segment by bits. So, each configuration can be written as a binary number with exactly seven bit, ith bit denoting the state of ith segment, if we number the bits as shown in the image.

sevenseg

Now, the segments which shall try to be in on state for a given digit can also be written as a binary number mask of digit x. How to find out the number of segments in on state, if we have to display x for a given configuration given by binary number mask.

We know, ith segment shall be in on state IF and only if the ith bit in both the configuration and mask have the ith bit on. This is the same as AND bitwise operation. Hence, we can just take the AND value of configuration and mask of digit and check if the number of set bits is the same as given in condition or not.

Hence, we can pre-define masks of each digit and check all configurations.

You can refer this to learn more on bitwise algorithms.

Time Complexity

Time complexity is O(N*2^7*7) per test case.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
 
using namespace std;
 
int mask[10]={119, 36, 93, 109, 46, 107, 123, 37, 127, 111};
int n;
int x[11], y[11];
 
int check(int msk)
{
    for (int i=1;i<=n;i++)
    {
	int bed = 0;
	for (int j=0;j<7;j++)
	if ((mask[x[i]]&(1<<j)) && !(msk&(1<<j))) bed++;
	if (bed!=y[i]) return false;
    }
 
     return true;
}
void solve()
{
    assert(n<=10);
    cin>>n;
 
    for (int i=1;i<=n;i++){
	cin>>x[i]>>y[i];
	assert(x[i]>=0 && x[i]<=9);
	assert(y[i]<=7 && y[i]>=0);
 
	for (int j=i-1;j>0;j--)
	    assert(x[i]!=x[j]);
    }
 
    int ok = 0;
    int mini = 10;
    int maxi = 0;
    for (int i=0;i<1<<7;i++)
	if (check(i)){
	    if (!ok)
	    {
	        ok = 1;
	        mini = __builtin_popcount(i);
	        maxi = mini;
	    } else
	    {
	        mini = min(mini, __builtin_popcount(i));
	        maxi = max(maxi, __builtin_popcount(i));
	    }
	}
 
    if (!ok) printf("invalid\n"); else
    printf("%d %d\n",mini,maxi);
}
 
int main()
{
    int t;
 
    cin>>t;
    while(t--)
	solve();
 
    return 0;
}
Tester's Solution
     		#include<bits/stdc++.h>
 
using namespace std;
 
int mask[10]={119, 36, 93, 109, 46, 107, 123, 37, 127, 111};
int n;
int x[11], y[11];
 
int check(int msk)
{
    for (int i=1;i<=n;i++)
    {
	int bed = 0;
	for (int j=0;j<7;j++)
	if ((mask[x[i]]&(1<<j)) && !(msk&(1<<j))) bed++;
	if (bed!=y[i]) return false;
    }
 
     return true;
}
void solve()
{
    assert(n<=10);
    cin>>n;
 
    for (int i=1;i<=n;i++){
	cin>>x[i]>>y[i];
	assert(x[i]>=0 && x[i]<=9);
	assert(y[i]<=7 && y[i]>=0);
 
	for (int j=i-1;j>0;j--)
	    assert(x[i]!=x[j]);
    }
 
    int ok = 0;
    int mini = 10;
    int maxi = 0;
    for (int i=0;i<1<<7;i++)
	if (check(i)){
	    if (!ok)
	    {
	        ok = 1;
	        mini = __builtin_popcount(i);
	        maxi = mini;
	    } else
	    {
	        mini = min(mini, __builtin_popcount(i));
	        maxi = max(maxi, __builtin_popcount(i));
	    }
	}
 
    if (!ok) printf("invalid\n"); else
    printf("%d %d\n",mini,maxi);
}
 
int main()
{
    int t;
 
    cin>>t;
    assert(t<=1000);
    while(t--)
	solve();
 
    return 0;
}
Editorialist's Solution
	 import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
class SEVENSEG{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    // _  0
    //| | 1 2
    // _  3
    //| | 4 5
    // _  6
    int get(int[] x){
	int ans = 0;
	for(int y:x)ans |= 1<<y;
	return ans;
    }
    void solve(int TC) throws Exception{
	int[] cur = new int[10];
	cur[0] = get(new int[]{0,1,2,4,5,6});
	cur[1] = get(new int[]{2,5});
	cur[2] = get(new int[]{0,2,3,4,6});
	cur[3] = get(new int[]{0,2,3,5,6});
	cur[4] = get(new int[]{1,2,3,5});
	cur[5] = get(new int[]{0,1,3,5,6});
	cur[6] = get(new int[]{0,1,3,4,5,6});
	cur[7] = get(new int[]{0,2,5});
	cur[8] = get(new int[]{0,1,2,3,4,5,6});
	cur[9] = get(new int[]{0,1,2,3,5,6});
	int n = ni();
	int[] val = new int[10];
	Arrays.fill(val, -1);
	boolean valid = true;
	for(int i = 0; i< n; i++){
	    int x = ni(), y = ni();
	    if(val[x]==-1)val[x] = y;
	    else valid &= val[x]==y;
	}
	int min = 8, max = -1;
	for(int i = 0; i< 1<<7; i++){
	    boolean v = true;
	    for(int j = 0; j< 10; j++){
	        if(val[j]==-1)continue;
	        if(bit(i&cur[j])!=val[j])v = false;
	    }
	    if(v){
	        min = Math.min(min, 7-bit(i));
	        max = Math.max(max, 7-bit(i));
	    }
	}
	if(valid && min<= max)pn(min+" "+max);
	else pn("invalid");
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    long mod = (long)1e9+7, IINF = (long)1e18;
    final int INF = (int)1e9, MX = (int)3e5+2;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
    static boolean multipleTC = true, memory = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
	in = new FastReader();
	out = new PrintWriter(System.out);
	int T = (multipleTC)?ni():1;
	//Solution Credits: Taranpreet Singh
	pre();for(int t = 1; t<= T; t++)solve(t);
	out.flush();
	out.close();
    }
    public static void main(String[] args) throws Exception{
	if(memory)new Thread(null, new Runnable() {public void run(){try{new SEVENSEG().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
	else new SEVENSEG().run();
    }
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}
 
    class FastReader{
	BufferedReader br;
	StringTokenizer st;
	public FastReader(){
	    br = new BufferedReader(new InputStreamReader(System.in));
	}
 
	public FastReader(String s) throws Exception{
	    br = new BufferedReader(new FileReader(s));
	}
 
	String next() throws Exception{
	    while (st == null || !st.hasMoreElements()){
	        try{
	            st = new StringTokenizer(br.readLine());
	        }catch (IOException  e){
	            throw new Exception(e.toString());
	        }
	    }
	    return st.nextToken();
	}
 
	String nextLine() throws Exception{
	    String str = "";
	    try{   
	        str = br.readLine();
	    }catch (IOException e){
	        throw new Exception(e.toString());
	    }  
	    return str;
	}
    }
} 

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

12 Likes

I had the same approach but different indices for segment. Nice question. Loved it.

3 Likes

Nice Editorial, Kudos to the setter also for a good problem. :grinning::grinning:

2 Likes

Nice question on bitmasking.

1 Like
if ((mask[x[i]]&(1<<j)) && !(msk&(1<<j))) bed++;

Could someone explain me this line

1 Like

Can anyone please explain how the mask array is formed?
int mask[10]={119, 36, 93, 109, 46, 107, 123, 37, 127, 111};

Label segments as 0,1,2....6. If the segment is on for a particular number, set the bit at that position as 1 else 0. The binary value, when converted to decimal gives us the number. The numbers may vary as and per your labelling.

I also have doubt regarding the same. Why have we used
(not (msk & (1 << j)))
rather than just (msk & (1 << j)) ?
In any case all 128 combinations are going to be checked so the opposite one should satisfy the requirements. Unfortunately, it is a WA without “not”. Can someone please explain ?
Thanks

EDIT:

Ok. I understood why it is this way. We had to finally calculate how many LEDS are damaged min and max. So he has taken a NOT so that the final answer actually returns the min and max directly.
I did it without “not” and in the final print, had to cout << n - maxi << n - mini ;

My code is attached here: https://www.codechef.com/viewsolution/23738807

https://www.codechef.com/viewsolution/23712690"

Maybe this code will help. segments are numbered as
0 - 5 (from top and clockwise) and middle one is 6

2 Likes

((mask[x[i]]&(1<<j)) part checks that we only check for the segment that can represent the current digit

Then the next part check whether that segment is in off state or not

So we count basically the off states for our current configuration and also make sure the segments we are checking are of current digit

thus if its equal to y[i] then that configuration can be considered for calculating min and max :smile: Hope this Helps

Also i Think int can be optimised to bitset for msk

The origin problem narrative didn’t contain firgue of “0”, which confused me.

can somebody please explain this editorial solution in detail

For those who are having trouble understanding the editorial. Here is what it means.
Code for Reference: Link

There are 7 segments, they can either be on or off (0 or 1) hence can be represented as binary sequence.

Lets number them so that we can talk easily about them.

Top = 0^{th} bit
Top-Right = 1^{st} bit
Bottom-Right= 2^{nd} bit
Bottom = 3^{rd} bit
Bottom-Left = 4^{th} bit
Top-Left = 5^{th} bit
Middle = 6^{th} bit

Now we let’s see 1, here only Top Right and Bottom Right Segments are On. So It can be represented as 0000110 in 7 bits.
Therefore 1 is equivalent to 6
Similarly, we can calculate values of all digits(Can clearly see how in the main function of my code)

Now let’s move onto the solve method.
Here we take input and then check for all 2^7 combinations. Now in every combination, a set of the bad and working segment is represented by 0 and 1

For every input, we check this. We have our configuration and configuration of a digit. We check if a segment should be on in this digit and is working in our configuration (both should be 1), and then add to the working segment count of that digit. If our count for this input does not match then the configuration is not valid and we exit checking any further

But if it matches all input then
The number of the working segments ans = Number of 1 bit in configuration.
Thus non-working segments = 7-ans
set max and min
But if we never reached this far that is no configuration ever matched with the input then mn remains 8(which can never be if we ever get a correct configuration) then the input is invalid.

5 Likes

Consider the seven segment display diagram shown in the editorial.
Generate a 7 bit binary no, and set those bits which are on for the given no.
Eg:
For 0 - 1110111 = 119
1 - 0100100 = 36
and so on

Can you please explain this part with an example? How do we understand if the digit is in off or on and if it is working in the config?
((1 << j) & k) && ((1 << j) & a))
Can’t understand this part of the code :confused:

@tanmay157 As you can see in my code
k = m[i.first] this means the configuration of the digit as expected when all segments are working
a stands for my current configuration
Both are 7 bits ( as far as I am considering)
Now I check all 7 bits as for(int j = 0; j < 7; ++j)
((1 << j ) & k) It is a pretty common bit manipulation trick to check if j^{th} bit of k is 1 or not.
If j^{th} bit of k is 1 this means that if this segment is working then it will be on
So I check ((1 << j ) & a) which means if j^{th} bit of a is on or not(working or not)

So if it is working and it is expected to be on in digit it will be on
Hence increase my count.

1 Like

Suppose all the tests conducted were valid, would we still have to check each configuration? Or just finding the common segments in all the numbers would have been sufficient? Because I still am in the process of understanding this.

Hi your editorial is nice. But can u please explain this question to me?

I am also having trouble understanding it.