Understanding this problem statement

[Kalcor]

Hello there is a problem that I can't exactly understand and due to that my code just answers some of the test cases and fails on the other but I'll provide a working code so it could help you explain the problem statement, so here is the problem:

Sagheer is walking in the street when he comes to an intersection of two roads. Each road can be represented as two parts where each part has 3 lanes getting into the intersection (one for each direction) and 3 lanes getting out of the intersection, so we have 4 parts in total. Each part has 4 lights, one for each lane getting into the intersection (l — left, s — straight, r — right) and a light p for a pedestrian crossing.

The link below is an illustration:
http://codeforces.com/predownloaded/ca/56/ca56d64e2a651046905f481f0bf778533c6e77e6.png

An accident is possible if a car can hit a pedestrian. This can happen if the light of a pedestrian crossing of some part and the light of a lane that can get to or from that same part are green at the same time.

Now, Sagheer is monitoring the configuration of the traffic lights. Your task is to help him detect whether an accident is possible.

Input
The input consists of four lines with each line describing a road part given in a counter-clockwise order.

Each line contains four integers l, s, r, p — for the left, straight, right and pedestrian lights, respectively. The possible values are 0 for red light and 1 for green light.

Output
On a single line, print "YES" if an accident is possible, and "NO" otherwise.

Examples
input
1 0 0 1
0 1 0 0
0 0 1 0
0 0 0 1
output
YES
input
0 1 1 0
1 0 1 0
1 1 0 0
0 0 0 1
output
NO
input
1 0 0 0
0 0 0 1
0 0 0 0
1 0 1 0
output
NO
Note
In the first example, some accidents are possible because cars of part 1 can hit pedestrians of parts 1 and 4. Also, cars of parts 2 and 3 can hit pedestrians of part 4.

In the second example, no car can pass the pedestrian crossing of part 4 which is the only green pedestrian light. So, no accident can occur.

working code:

#include <iostream>
using namespace std;

int main() {
	int arr[4][4];
	for(int i = 0;i < 4;i++)
		for(int j = 0;j < 4;j++)
			cin >> arr[i][j];
	for(int i = 0;i < 4;i++)
	{
		if(arr[i][3])
		{
			if(arr[i][0] ||  arr[i][1] || arr[i][2] || arr[(i + 1)%4][0] || arr[(i + 2)%4][1] || arr[(i + 3)%4][2])
			{
				cout << "YES"; return 0;
			}
		}
	}
	cout << "NO";
	return 0;
}

arr[(i + 1)%4][0] || arr[(i + 2)%4][1] || arr[(i + 3)%4][2]

This part drives me insane..


Thanks in advance <3

[jlb]

Have you studied the bitwise operators , masking and other bit manipulation options yet?

http://www.learncpp.com/cpp-tutorial/38-bitwise-operators/

Also in your examples it would probably help you if you identified which line can cause the accident:

Example 1:

1 0 0 1   Yes
0 1 0 0   No
0 0 1 0   No
0 0 0 1   No
output
YES

[Kalcor]

@jlb what makes you sure that bit wise works? it tried the 1 and 1 strat and it got a wrong answer in one of the test cases as you see the code i provided up there did exactly what i did but what made that code get accepted and mine didn't was this part(again):
arr[(i + 1)%4][0] || arr[(i + 2)%4][1] || arr[(i + 3)%4][2]
Which I still do not understand the meaning of.

[dhayden]

I suspect that the description is deliberately confusing. The professor is trying to get you to look at the data and try to figure out how to represent it in your program.

I think the way to represent this is to concentrate on the crosswalks: 1, 2, 3, and 4. The first crosswalk is labeled p1 in the diagram.

When a light is green, it allows a car to cross 2 crosswalks. For example, cars in the left turn lane in section 1 will cross crosswalks 1 and 4. Cars going straight will cross crosswalks 1 and 3, and cars turning right will cross crosswalks 1 and 2.

I think you should create two arrays: bool cars[4] and bool peds[4]. The first one indicates whether a car can cross the given part of the road (after renumbering the sections 0-3 instead of 1-4 of course). The peds array indicates whether a pedestrian can cross the given part of the road. Write code that reads the input and populates these two arrays. Then you can get the answer by simply seeing if corresponding values in the arrays are ever set. In other words, if cars[i] && peds[i] is true, then an accident can occur.

[jlb]

Without seeing what you tried there is no way I can tell you what you did wrong. However this is basically what you may want to consider using bitset operators.

#include <iostream>
#include <bitset>

using namespace std;

int main()
{
    int value[2][4] = {{0b1001, 0b0100, 0b0010, 0b0001},
                       {0b0110, 0b1010, 0b1100, 0b0001}};
    int counter = 0;
    for(auto& itr : value)
    {
        bool possible_accident = false;
        for(auto& values : itr)
        {
            // Check to see if there is a pedestrian ( values % 2).
            // If there is a pedestrian check if there is a car present in any of the lanes.
            // If there is a pedestrian and a car in at least one of the lanes then there is a possibility for an accident.
            if(values % 2 && values & 14)  
            {
                // Just using the bitset<> to print the value in binary.
                std::cout << std::bitset<4>(values);
                std::cout << " possible accident." << std::endl;
                possible_accident = true;
            }
        }
        std::cout << "Case " << ++counter << std::endl;
        if(possible_accident)
            std::cout << " Possible accident." << std::endl << std::endl;
        else
            std::cout << " No possible accident." << std::endl;

    }
    return 0;
}

I'm not going to comment too much on that code you found because, IMO, it just complicates the code.

[ne555]

> it tried the 1 and 1 strat and it got a wrong answer
ah, the 1 and 1 strategy...
¿what the hell are you talking about?

> as you see the code i provided up there did exactly what i did
we can't see that as we can't see your code.


> arr[(i + 1)%4][0] || arr[(i + 2)%4][1] || arr[(i + 3)%4][2]
> This part drives me insane..

arr[i] //the part were pedestrian are crossing
arr[(i+1) % 4] //the part at your right
arr[(i+2) % 4] //in front of you
arr[(i+3) % 4] //the part at your left

arr[i][0] or  arr[i][1] or arr[i][2] //no cars with the pedestrian
	or arr[(i + 1)%4][0] //no cars that come from the right and turn left
	or arr[(i + 2)%4][1] //no cars coming straight from the front
	or arr[(i + 3)%4][2] //no cars that come from the left and turn right 

here's a diagram, the green means that the pedestrian is allowed to cross, the red marks what parts you need to check
https://img0.uploadhouse.com/fileuploads/25134/251340803932a35ab52913457a85eb2b4c97d39c.png


@jlb: look both ways before crossing

[dhayden]

jlb, there is a pedestrian in the crosswalk if values & 1, not if values & 2. The rest of your logic only detects cars entering the intersection. You also have to worry about cars leaving the intersection. For example:
0001
1000
0000
0000

Results in a possible accident because there is a car turning left from section 2, crossing section 1.


Kalcor, reread my post. The tricky part to this problem is that when a light is green, it means that a car will cross TWO crosswalks. You have to account for both.