If Sarid is a Revealer a = R, his claim about Dhroov is correct, so we simply print b. However, if Sarid is a Deceiver a = D, his claim is false, and we print the opposite of b—if b = R, print D, otherwise print R.

Time Complexity = O(1)

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

int main(){
    char a,b;
    cin>>a>>b;
    if(a=='R'){
        cout<<b<<endl;
    }
    else{
        if(b=='R'){
            cout<<'D'<<endl;
        }
        else{
            cout<<'R'<<endl;
        }
    }
}

a,b = input().split()
if a == 'R':
    print(b)
else:
    if b == 'R':
        print('D')
    else:
        print('R')

We have two options: either use the coupon or don't. To find the best option, we first calculate the total cost without the coupon by summing up the prices of all items. For the cost with the coupon, we reduce each item's price by Y (or make it free if the price is less than or equal to Y) and add the coupon's cost. The final answer is the minimum of these two totals.

Time Complexity = O(N)

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

int main() {
    int n,x,y;
    cin>>n>>x>>y;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int cost_with_coupon = x, cost_without_coupon = 0;
    for(int i=0;i<n;i++){
        cost_with_coupon += max(arr[i]-y,0);
        cost_without_coupon += arr[i];
    }
    cout<<min(cost_with_coupon,cost_without_coupon)<<endl;
    return 0;
}

n,x,y = map(int,input().split())
arr = list(map(int,input().split()))
cost_without_coupon = sum(arr)
cost_with_coupon = x + sum(max(0,i-y) for i in arr)
print(min(cost_without_coupon,cost_with_coupon))

We need to assign the groups of students to taxis in a way that uses the least number of taxis. Here's the step-by-step plan:

• Groups of 4 students: These groups can't share a taxi with anyone else, so we directly add their count to our total number of taxis.

• Groups of 3 students: These groups can share a taxi with groups of 1 student (since 3 + 1 = 4). Pair as many of these groups as possible with single-student groups. If there are still unpaired groups of 3 left, they each need a separate taxi.

• Groups of 2 students: Pair these groups with other groups of 2 students (since 2 + 2 = 4). If there's an odd number of 2-student groups, we can pair one group with a 1-student group. If no single-student group is left, this 2-student group will need its own taxi.

• Groups of 1 student: After all possible pairings, we group the remaining single-student groups in taxis. Each taxi can take up to 4 students, so the number of taxis needed is the ceiling of their count divided by 4.

Final answer is the sum of all these taxis.

Time Complexity = O(N)

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

int main() {
    int n;
    cin >> n;
    vector<int> arr(n), group_count(5,0);
    for(int i=0;i<n;i++) {
        cin>>arr[i];
        group_count[arr[i]]++; //store the count of each group
    }
    int four_people = group_count[4];
    int three_plus_one = min(group_count[3], group_count[1]);
    group_count[1] -= three_plus_one;
    group_count[3] -= three_plus_one;
    int two_plus_two = group_count[2] / 2;
    int no_of_taxis = four_people + three_plus_one + two_plus_two;
    no_of_taxis += group_count[3]; //if groups of 3 people remain
    if(group_count[2]%2){ //if count of groups of 2 people is odd
        no_of_taxis++;
        if(group_count[1]){
            group_count[1]--;
        }
    }
    no_of_taxis += (group_count[1]+3)/4; //4 groups of 1 person are placed in a taxi so we take ceil
    cout<<no_of_taxis<<endl;
    return 0;
}

n = int(input())
arr = list(map(int,input().split()))
group_count = [0]*5
for i in arr:
    group_count[i] += 1   #store the count of each group
four_people = group_count[4]
three_plus_one = min(group_count[3],group_count[1])
group_count[1] -= three_plus_one
group_count[3] -= three_plus_one
two_plus_two = group_count[2]//2
no_of_taxis = four_people + three_plus_one + two_plus_two
no_of_taxis += group_count[3] #if groups of 3 people remain
if group_count[2]%2:  #if count of groups of 2 people is odd
    no_of_taxis += 1
    if group_count[1]:
        group_count[1] -= 1
no_of_taxis += (group_count[1]+3)//4 # 4 groups of 1 person are placed in a taxi so we take ceil
print(no_of_taxis)

This is an implementation-based problem where we need to brute-force through all possible configurations. The key idea is to divide the grid into two parts:

• Cells belonging to the 'Y': These are the two diagonals starting from the top corners and meeting at the center, and the vertical line extending downward from the center.
• Non-'Y' cells: All the other cells in the grid.

The goal is to minimize the number of operations needed to: - Make all cells in the 'Y' pattern have the same value. - Ensure all non-'Y' cells have a different value from the 'Y' cells.

For each test case, we brute-force through all combinations of assigning values to the 'Y' cells and non-'Y' cells, counting the number of changes needed to achieve the desired configuration. We then choose the configuration with the minimum number of changes.
For example, all 0 at Y and all 1 at Non-Y, all 2 at Y and all 0 at Non-Y, etc.

Time Complexity = O(N²)

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

int minimumOperationsToWriteY(vector<vector<int>>& grid) {
    vector<int> count_y(3),count_non_y(3);
    int n=grid.size();
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if((i==j && i<n/2) // diagonal from top-left to center
               || (i==n-j-1 && i<n/2) //diagonal from to-right to center
               || (i>=n/2 && j==n/2)) //vertical line from center to bottom
            {
                count_y[grid[i][j]]++;
            }
            else count_non_y[grid[i][j]]++;
        }
    }
    int min_ops = INT_MAX,sum_y=0,sum_non_y=0;
    for(auto i: count_y){
        sum_y+=i;
    }
    for(auto i: count_non_y){
        sum_non_y+=i;
    }
    for(int i=0;i<3;i++){
        int ops_to_make_y_equal = sum_y-count_y[i];
        for(int j=0;j<3;j++){
            if(i==j)continue;
            int ops_to_make_non_y_equal = sum_non_y-count_non_y[j];
            min_ops=min(min_ops,ops_to_make_y_equal+ops_to_make_non_y_equal);
        }
    }
    return min_ops;
}

int main() { 
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<vector<int>> arr(n,vector<int>(n));
        for(auto &i: arr){
            for(auto &j: i){
                cin>>j;
            }
        }
        cout<<minimumOperationsToWriteY(arr)<<endl;
    }
    return 0;
}

def minimum_operations_to_write_y(grid):
    count_y = [0] * 3
    count_non_y = [0] * 3
    n = len(grid)
    
    for i in range(n):
        for j in range(n):
            if (i == j and i < n // 2) or (i == n - j - 1 and i < n // 2) or (i >= n // 2 and j == n // 2):
                count_y[grid[i][j]] += 1
            else:
                count_non_y[grid[i][j]] += 1

    min_ops = float('inf')
    sum_y = sum(count_y)
    sum_non_y = sum(count_non_y)

    for i in range(3):
        ops_to_make_y_equal = sum_y - count_y[i]
        for j in range(3):
            if i == j:
                continue
            ops_to_make_non_y_equal = sum_non_y - count_non_y[j]
            min_ops = min(min_ops, ops_to_make_y_equal + ops_to_make_non_y_equal)

    return min_ops

t = int(input())
for _ in range(t):
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    print(minimum_operations_to_write_y(arr))

Key observation is that we can group the dancers by alternating positions — one group contains dancers at odd positions, and the other contains dancers at even positions. Now, for elements of a group to have same color, they must have a common factor which divides every element of that group. This is calculated by taking the Greatest Common Divisor(GCD) of all the elements of the group. To prevent neighbors from having the same color, the GCD of one group shouldn't divide any element of the other group.

Finally, we check:
- If the GCD of odd-positioned dancers divides any even-positioned dancers' energy.
- If the GCD of even-positioned dancers divides any odd-positioned dancers' energy.

If one group's GCD works without dividing any element of the other group, it's the answer. If neither GCD works, print 0.

Time Complexity = O(N)

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

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<ll> arr(n);
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        ll odd_gcd=0, even_gcd=0;
        for(int i=0;i<n;i++){
            if(i%2){
                even_gcd=__gcd(even_gcd,arr[i]);
            }
            else{
                odd_gcd=__gcd(odd_gcd,arr[i]);
            }
        }
        bool isOddValid=true,isEvenValid=true;
        for(int i=0;i<n;i++){
            if(i%2){
                if(arr[i]%odd_gcd==0){
                    isOddValid=false;
                }
            }
            else{
                if(arr[i]%even_gcd==0){
                    isEvenValid=false;
                }
            }
        }
        if(isOddValid){
            cout<<odd_gcd<<endl;
        }
        else if(isEvenValid){
            cout<<even_gcd<<endl;
        }
        else{
            cout<<0<<endl;
        }
    }
    return 0;
}

from math import gcd
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int,input().split()))
    odd_gcd,even_gcd = 0,0
    for i in range(n):
        if i%2:
            odd_gcd = gcd(odd_gcd,arr[i])
        else:
            even_gcd = gcd(even_gcd,arr[i])
    isOddValid,isEvenValid = True,True
    for i in range(n):
        if i%2:
            if arr[i]%even_gcd==0:
                isEvenValid = 0
        else:
            if arr[i]%odd_gcd==0:
                isOddValid = 0
    if isOddValid:
        print(odd_gcd)
    elif isEvenValid:
        print(even_gcd)
    else:
        print(0)

The key idea in this problem is that the Bitwise AND operation is monotonic. This means that as we AND more numbers together, the result either stays the same or gets smaller, but it will never get larger. We can use this property to help find the smallest m such that the AND of all numbers from n to m equals x.

To efficiently find this m, we use binary search. We set the search range as: low = n, high = 5 * 10^18 (since n can be as large as 10^18). For each midpoint mid, we calculate the AND of numbers from n to mid and compare it to x.

Instead of ANDing all the numbers between n and mid one by one (which would take too long for large numbers), we use a faster method based on the most significant bit (MSB). Here's how it works:

• If n and mid share the same most significant bits, the AND result will keep those bits.
• As soon as n and mid differ in one bit, all the bits after that will be 0. This happens because when the higher bit differs between two numbers, lower bits in the range would have flipped at least once. We compute the AND for n to mid and adjust our search range:

If the result is less than or equal to x, it means we're close to a solution. So, we reduce the search range by setting high = mid - 1 (to find a smaller m). If the result is greater than x, we increase the search range by setting low = mid + 1 (to increase the number of elements in the AND operation). After the binary search, we check if the low(which is our m) we found matches all the bits of x. If it does, we print the answer. If not, we print -1, meaning no such m exists.

Time Complexity = O(log(5 × 10¹⁸) × O(log₂N))

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

ll andRange(ll n, ll mid){
    ll and_of_range = 0;
    for(int i=61;i>=0;i--){
        if(((1ll<<i)&n) != ((1ll<<i)&mid)){    //Bits differ so all the lower bits from here will be 0
            break;
        }
        else{
           and_of_range |= (n & (1ll<<i));    //Bits are same so we add the bit to our answer
        }
    }
    return and_of_range;
}

int main() {
    int t;
    cin>>t;
    while(t--){
        ll n,x;
        cin>>n>>x;
        ll low = n, high = 5e18;
        while(low<=high){
            ll mid = low + (high-low)/2;
            ll and_of_range = andRange(n,mid);
            if(and_of_range<=x){
                high = mid - 1;    //search in the left half
            }
            else{
                low = mid + 1;    //search in the right half
            }
        }
        if((low&x)==x){    //verify the found answer
            cout<<low<<endl;
        }
        else{
           cout<<-1<<endl;
        }
    }
    return 0;
}

def andRange(n, mid):
    and_of_range = 0
    for i in range(61, -1, -1):
        if ((1 << i) & n) != ((1 << i) & mid):
            break
        else:
            and_of_range |= (n & (1 << i))
    return and_of_range

t = int(input())
for _ in range(t):
    n, x = map(int, input().split())
    low, high = n, 5 * 10**18
    while low <= high:
        mid = low + (high - low) // 2
        and_of_range = andRange(n, mid)
        if and_of_range <= x:
            high = mid - 1
        else:
            low = mid + 1
    if (low & x) == x:
        print(low)
    else:
        print(-1)