In the ever-evolving world of artificial intelligence, fine-tuning models to achieve optimal performance is a critical endeavor. We often find ourselves choosing between different methodologies, particularly when it comes to refining large language models (LLMs) or complex AI systems. Two primary approaches stand out: reinforcement learning (RL) and offline fine-tuning methods like Direct Preference Optimization (DPO).  

At first glance, it might seem logical that these methods, both aiming to improve model performance, would yield similar results. However, practical observations consistently reveal that RL-based fine-tuning often surpasses offline methods. This discrepancy piqued my curiosity, leading me to delve into a fascinating paper by Gokul Swamy et al. that attempts to shed light on this phenomenon.  

Understanding the Methods

Before diving into the core argument, let’s briefly recap the two methods:

• Reinforcement Learning (RL):
  • Imagine training a dog with treats. You provide positive reinforcement (rewards) when the dog performs the desired action. In AI, RL works similarly. The model interacts with an environment, and a “reward model” assesses the quality of its actions. The model learns to maximize these rewards, gradually improving its performance.  
• Offline Fine-Tuning (e.g., DPO):
  • This approach involves training the model on a fixed dataset. There’s no interactive feedback loop; the model learns from the existing data without real-time rewards. DPO, for example, directly optimizes the model’s policy based on preference data.  

The “Generation-Verification Gap”

The paper highlights a crucial concept: the “generation-verification gap.” This gap represents the difference in difficulty between generating an optimal output and verifying its quality. In many tasks, it’s significantly easier to evaluate whether an output is good than it is to produce that output from scratch.  

Consider these examples:

• Writing vs. Editing: It’s often easier to edit a poorly written paragraph into a good one than it is to write a perfect paragraph from a blank page.  
• Image Recognition vs. Image Generation: A model might find it easier to identify a high-quality image than to generate one.  

RL leverages this gap by first training a reward model to accurately assess the quality of outputs. This reward model then guides the model’s learning, effectively breaking down the complex task of generating optimal outputs into two simpler steps: verification and guided generation.  

Why RL Often Wins

The paper’s experiments reveal a surprising finding: simply increasing the amount of training data or performing additional offline training doesn’t close the performance gap. RL’s structured, two-stage approach provides a distinct advantage.  

Here’s why:

• Efficient Learning: By focusing on verification first, RL streamlines the learning process. The reward model acts as a reliable guide, directing the model toward optimal solutions.  
• Exploration and Refinement: RL encourages exploration, allowing the model to discover and refine its strategies based on feedback from the reward model.  
• Handling Complex Tasks: In tasks where the generation-verification gap is significant (e.g., complex reasoning, creative content generation), RL excels.  

Practical Implications

These insights have practical implications for AI practitioners:

• Task Complexity: For complex tasks with a significant generation-verification gap, prioritize RL-based fine-tuning.  
• Resource Optimization: For simpler tasks, offline methods might suffice, saving computational resources.  
• Data vs. Process: Remember that simply adding more data won’t necessarily close the performance gap. Focus on optimizing the learning process.  

Surprising Findings

The experimental results that show that adding more data does not close the performance gap were very interesting. It really shows how important the process of learning is, and not just the amount of data that is provided.  

Conclusion

The “generation-verification gap” provides a compelling explanation for why RL often outperforms offline fine-tuning. It’s a reminder that the learning process is as crucial as the data itself. As AI continues to advance, understanding these nuances will be essential for developing effective and efficient models.  

I encourage you to read the original paper for a deeper dive into the experimental details and theoretical underpinnings: https://arxiv.org/abs/2503.01067

Problem statement

Given two positive integers num1 and num2, find the integer x such that:

• x has the same number of set bits as num2, and
• The value x XOR num1 is minimal.

Note that XOR is the bitwise XOR operation.

Return the integer x. The test cases are generated such that x is uniquely determined.

The number of set bits of an integer is the number of 1‘s in its binary representation.

Example 1:

Input: num1 = 3, num2 = 5
Output: 3
Explanation:
The binary representations of num1 and num2 are 0011 and 0101, respectively.
The integer 3 has the same number of set bits as num2, and the value 3 XOR 3 = 0 is minimal.

Example 2:

Input: num1 = 1, num2 = 12
Output: 3
Explanation:
The binary representations of num1 and num2 are 0001 and 1100, respectively.
The integer 3 has the same number of set bits as num2, and the value 3 XOR 1 = 2 is minimal.

Constraints:

• 1 <= num1, num2 <= 109

Solution

This is a very nice binary arithmetic problem to sharpen the implementation skills.

The intuition is that we want to use as many of the bits as possible to “turn off” the most significant bits of the initial number by coinciding them with the set bits of num1 (since 1 ^ 1 = 0). If there are any remaining bits to place, the approach would be to use them to set the low significant bits by coinciding them with zeroes in num1 (since 1 ^ 0 = 1).

So, we can generate the optimal solution iteratively by performing following steps:

1. Count the number of bits in num2
2. Clear the set bits from the left to the right in num1 (to reduce the resulting number as much as possible towards zero)
3. Place remaining bits in the free positions from the right to the left (to keep the number as small as possible)

Final result is stored in the variable r, which is set to zero at the start and whose bits are set one by one as we’re constructing the solution.

Apparently, C++ implementation bellow resulted in a VERY fast and memory efficient solution:

class Solution {
public:
    int minimizeXor(int num1, int num2) {
        int c = 0, r = 0;
        
        // count the set bits in num2
        while (num2) {
            c += (num2 & 1);
            num2 >>= 1;
        }
        
        // clear bits from left to right in num1
        int b = (1 << 30); // start from the right
        while (b) {
            if (b & num1) {
                num1 ^= b; // clear the current bit
                r |= b; // set the bit in the solution
                c--;
                if (c == 0) break;
            }
            b >>= 1; // move the bit to the right
        }
        
        // add the remaining bits from right to left
        b = 1;
        while (c) {
            if (!(r & b)) { // if the current position is free...
                r |= b; // ... set it
                c--;
            }
            b <<= 1;
        }
        
        return r;
    }
};

Problem statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 500

Solution

Since there are only 30 numbers and the target < 500, a simple backtracking solution will work well here.

We define a function to keep track of the current index we are at and the current sum we have accumulated. There are two global states – one to keep track of the current set of numbers making up the sum we currently have (current_vec), and an array containing copies of all of the arrays which are confirmed to be solutions (sol).

At each step of the recursion we will try two things:

1. simply skip the number at the current index, keeping the sum intact and increasing the index
2. add the current number to the solution (if it doesn’t exceed the target sum), increasing the sum and leaving the index intact

This way we will be picking the the same number multiple times, as expected by the problem definition.

There are two exit conditions: reaching the sum and reaching the end of the candidate numbers. When we reach the target sum we will copy the current_vec array of the tracked numbers as a separate solution into the sol array, so it can be printed out later.

We start the search from index 0 and sum 0, allowing it to skip the first element if needed.

Side note: this is my first solution on Leetcode implemented in Rust. Personally, I don’t like the fact I had to inject references to targ, current_vec and sol into a function signature and I hope I’ll learn a better way to this in the near future.

impl Solution {
    
    pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut sol: Vec<Vec<i32>> = vec![];
        let mut current_vec: Vec<i32> = vec![];
        
        fn f(idx: usize, sum: i32, cand: &Vec<i32>, targ: &i32, current_vec: &mut Vec<i32>, sol: &mut Vec<Vec<i32>>) {
            // reached the sum
            if sum == *targ {
                sol.push(current_vec.clone());
                return
            }
            
            // reached the end
            if idx == cand.len() {
                return
            }
            
            f(idx + 1, sum, cand, targ, current_vec, sol);
            
            if (sum + cand[idx] <= *targ) {
                current_vec.push(cand[idx]);
                f(idx, sum + cand[idx], cand, targ, current_vec, sol);
                current_vec.remove(current_vec.len() - 1);
            }
            
        };
        
        f(0, 0, &candidates, &target, &mut current_vec, &mut sol);
        
        sol
    }
}

Problem statement

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.

• For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words.

Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6.
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
The output order does not matter. Returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 is s that is equal to the concatenation of any permutation of words.
We return an empty array.

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9.
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words.
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words.
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.

Constraints:

• 1 <= s.length <= 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• s and words[i] consist of lowercase English letters.

Solution

For any starting index i we know exactly the total length of the substring we expect (sum of all of the word lengths). The challenge is to figure out the order of the words in that substring.

One approach is to move letter by letter and reject all the words which don’t mach a prefix we scanned so far. If at any point we end up with a prefix matching a complete word from our list, we mark that word as used, clear the prefix and continue with the process until the end. After the whole substring has been scanned, we mark the current starting index as one of the solutions only if we used all of the words in the list exactly once. We use a hash map to maintain a histogram of words. This can be optimized a bit further by interrupting the current starting index exploration even earlier if we notice that the word we just counted for was used more times than it exists in the list.

Now, in order to quickly traverse the list based on a incrementally built suffix we use a very simple implementation of suffix tree. Each node implicitly represents a single lowercase letter of the English alphabet. Pointers to 26 child nodes represent the next letter in the word. Each node’s member boolean is_end marks the letter as a final letter of a word in the list. This is used to top the traversal once we hit the node with is_end=true. Finding a word of length L in a list of words of length N is O(L), which is great.

Complete C++ implementation is given below.

class PrefixTree {
public:
    bool is_end = false;
    PrefixTree* next[26];
    
    // insert the word into the tree
    void insert(string word) {
        // start at the root
        PrefixTree *current = this;
        
        for (int i=0;i<word.size();i++) {
            char c = word[i]-'a';
            if (current->next[c] == NULL) {
                current->next[c] = new PrefixTree();
            }
            current = current->next[c];
        }
        
        current->is_end = true;
    }
    
};

class Solution {
public:
    
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        
        int n = words.size();
        int total_n = 0;
        for (int i=0;i<n;i++) total_n += words[i].size();
        
        // construct the prefix tree
        // and word histogram
        PrefixTree *t = new PrefixTree();
        map<string, int> w_h;
        for (int i=0;i<n;i++) {
            t->insert(words[i]);
            w_h[words[i]] = w_h[words[i]] + 1;
        }
        
        // traverse the string trying to start from each letter
        for (int i=0;i<s.size() - total_n + 1;i++) {
            // move through the total number of letter concatenated
            PrefixTree *t_current = t;
            bool stop = false;
            string w;
            map<string, int> w_h_current;
            int j;
            for (j=0;j<total_n && !stop;j++) {
                char c = s[i+j]-'a';
                // current letter doesn't exist as a continuation of the word
                if (t_current->next[c] == NULL) {
                    // cout << "--!-- no child." << endl;
                    if (t_current->is_end) {
                        // start the new word
                        t_current = t; // reset the tree to the root
                        w_h_current[w] = w_h_current[w] + 1;
                        
                        // if we used the word more times than allowed...
                        if (w_h_current[w] > w_h[w]) { stop = true; continue; }
                        w = "";
                        j--;
                        continue;
                    } else {
                        stop = true;
                    }
                } else {
                    // move into the next char
                    w.push_back(c + 'a');
                    t_current = t_current->next[c];
                }
            }
            
            // handle the last word
            if (j == total_n) {
                if (t_current->is_end) w_h_current[w] = w_h_current[w] + 1;
                if (w_h_current[w] > w_h[w]) stop = true;
            }
            
            if (stop) continue;
            res.push_back(i);
        }
        
        return res;
    }
};

In one move, you can choose two indices i and j (1≤i,j≤n; i≠j) and swap ai with aj and bi with bj. You have to perform the swap in both arrays.

You are allowed to perform at most 104 moves (possibly, zero). Can you make both arrays sorted in a non-decreasing order at the end? If you can, print any sequence of moves that makes both arrays sorted.

Input

The first line contains a single integer t (1≤t≤100) — the number of testcases.

The first line of each testcase contains a single integer n (2≤n≤100) — the number of elements in both arrays.

The second line contains n integers a1,a2,…,an (1≤ai≤n) — the first array.

The third line contains n integers b1,b2,…,bn (1≤bi≤n) — the second array.

Output

For each testcase, print the answer. If it’s impossible to make both arrays sorted in a non-decreasing order in at most 10^4 moves, print -1. Otherwise, first, print the number of moves k (0≤k≤104). Then print i and j for each move (1≤i,j≤n; i≠j).

If there are multiple answers, then print any of them. You don’t have to minimize the number of moves.

Example input

3
2
1 2
1 2
2
2 1
1 2
4
2 3 1 2
2 3 2 3

Example output

0
-1
3
3 1
3 2
4 3

Solution

Knowing we’re asked to sort the array in at most 10^4 steps, and limit for N is 10^2, we can get away with an O(N^2) solution… Bubble sort to the rescue!

When implementing bubble sort we will try to sort primarily on the values of A, and resolve the ties with sorting on the respective values of B. If this yields sorted A and B, it is safe to print out the swaps performed during the bubble sort, or -1 otherwise.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

int main(){

    int t;
    cin >> t;
    while (t--) {

        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for (int i=0;i<n;i++) cin >> a[i];
        for (int i=0;i<n;i++) cin >> b[i];

        vector< pair<int, int> > sol;
        for (int i=0;i<n;i++) {
            for (int j=i+1;j<n;j++) {
                if (a[j] < a[i] || (a[j] == a[i] && b[j] < b[i])) {
                    swap(a[i], a[j]);
                    swap(b[i], b[j]);
                    sol.push_back({ i + 1, j + 1 });
                }
            }
        }

        // check if B is sorted
        int i=1;
        for (;i<n;i++) {
            if (b[i] < b[i-1]) break;
        }
        if (i < n) {
            cout << -1 << endl;
            continue;
        }

        // solution is possible (ignore 10^4 limit, n = 100)
        cout << sol.size() << endl;
        for (int i=0;i<sol.size();i++) cout << sol[i].first << " " << sol[i].second << endl;

    }
    return 0;
}

Then he asks you to shuffle the deck m times. With the j-th shuffle, you should take bj topmost cards and move them under the remaining (n−bj) cards without changing the order.

And then, using some magic, Monocarp tells you the topmost card of the deck. However, you are not really buying that magic. You tell him that you know the topmost card yourself. Can you surprise Monocarp and tell him the topmost card before he shows it?

Input

The first line contains a single integer t (1≤t≤104) — the number of testcases.

The first line of each testcase contains a single integer n (2≤n≤2⋅105) — the number of cards in the deck.

The second line contains n pairwise distinct integers a1,a2,…,an (1≤ai≤n) — the values of the cards.

The third line contains a single integer m (1≤m≤2⋅105) — the number of shuffles.

The fourth line contains m integers b1,b2,…,bm (1≤bj≤n−1) — the amount of cards that are moved on the j-th shuffle.

The sum of n over all testcases doesn’t exceed 2⋅105. The sum of m over all testcases doesn’t exceed 2⋅105.

Output

For each testcase, print a single integer — the value of the card on the top of the deck after the deck is shuffled m times.

Example input

3
2
1 2
3
1 1 1
4
3 1 4 2
2
3 1
5
2 1 5 4 3
5
3 2 1 2 1

Example output

2
3
3

Note

In the first testcase, each shuffle effectively swaps two cards. After three swaps, the deck will be [2,1].

In the second testcase, the second shuffle cancels what the first shuffle did. First, three topmost cards went underneath the last card, then that card went back below the remaining three cards. So the deck remained unchanged from the initial one — the topmost card has value 3.

Solution

The trick is to avoid actual shuffling of the cards (moving any elements of the initial array).

To do that we can simply maintain a single integer to point the index in the array the circular buffer starts. Whenever we read a shuffle, we add the indicated number of cards to the buffer with modulo N (the deck length).

After all shuffling is done we print out the card on the resulting index.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n;
        vector<int> a(n);
        for (int i=0;i<n;i++) cin >> a[i];

        cin >> m;
        int k, c = 0;
        for (int i=0;i<m;i++) {
            cin >> k;
            c = (c + k) % n;
        }
        cout << a[c] << endl;
    }
    return 0;
}

On the first turn of the game, the first player chooses one of his/her cards and puts it on the table (plays it). On the second turn, the second player chooses one of his/her cards such that the integer on it is greater than the integer on the card played on the first turn, and plays it. On the third turn, the first player chooses one of his/her cards such that the integer on it is greater than the integer on the card played on the second turn, and plays it, and so on — the players take turns, and each player has to choose one of his/her cards with greater integer than the card played by the other player on the last turn.

If some player cannot make a turn, he/she loses.

For example, if Alice has 4 cards with numbers [10,5,3,8], and Bob has 3 cards with numbers [6,11,6], the game may go as follows:

• Alice can choose any of her cards. She chooses the card with integer 5 and plays it.
• Bob can choose any of his cards with number greater than 5. He chooses a card with integer 6 and plays it.
• Alice can choose any of her cards with number greater than 6. She chooses the card with integer 10 and plays it.
• Bob can choose any of his cards with number greater than 10. He chooses a card with integer 11 and plays it.
• Alice can choose any of her cards with number greater than 11, but she has no such cards, so she loses.

Both Alice and Bob play optimally (if a player is able to win the game no matter how the other player plays, the former player will definitely win the game).

You have to answer two questions:

• who wins if Alice is the first player?
• who wins if Bob is the first player?

Input

The first line contains one integer t (1≤t≤1000) — the number of test cases. Each test case consists of four lines.

The first line of a test case contains one integer n (1≤n≤50) — the number of cards Alice has.

The second line contains n integers a1,a2,…,an (1≤ai≤50) — the numbers written on the cards that Alice has.

The third line contains one integer m (1≤m≤50) — the number of Bob’s cards.

The fourth line contains m integers b1,b2,…,bm (1≤bi≤50) — the numbers on Bob’s cards.

Output

For each test case, print two lines. The first line should be Alice if Alice wins when she is the first player; otherwise, the first line should be Bob. The second line should contain the name of the winner if Bob is the first player, in the same format.

Example input

4
1
6
2
6 8
4
1 3 3 7
2
4 2
1
50
2
25 50
10
1 2 3 4 5 6 7 8 9 10
2
5 15

Example output

Bob
Bob
Alice
Alice
Alice
Bob
Bob
Bob

Note

Let’s consider the first test case of the example.

Alice has one card with integer 6, Bob has two cards with numbers [6,8].

If Alice is the first player, she has to play the card with number 6. Bob then has to play the card with number 8. Alice has no cards left, so she loses.

If Bob is the first player, then no matter which of his cards he chooses on the first turn, Alice won’t be able to play her card on the second turn, so she will lose.

Solution

If Alice plays first and she has a higher (or equal) max number than Bob, she can throw that card and win. Same applies for Bob.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int t;
    cin >> t;
    while (t--) {
        int n,m;
        cin >> n;
        vector<int> a(n);
        for (int i=0;i<n;i++) cin >> a[i];
        sort(a.begin(), a.end());

        cin >> m;
        vector<int> b(m);
        for (int i=0;i<m;i++) cin >> b[i];
        sort(b.begin(), b.end());
        
        int ma = a[n-1];
        int mb = b[m-1];

        if (ma >= mb) cout << "Alice" << endl;
        else cout << "Bob" << endl;
        if (mb >= ma) cout << "Bob" << endl;
        else cout << "Alice" << endl;
    }
    return 0;
}

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given an array a of n positive integers.

Let LIS(a) denote the length of longest strictly increasing subsequence of a. For example,

• LIS([2,1,1,3]) = 2.
• LIS([3,5,10,20]) = 4.
• LIS([3,1,2,4]) = 3.

We define array a′ as the array obtained after reversing the array a i.e. a′=[an,an−1,…,a1].

The beauty of array a is defined as min(LIS(a),LIS(a′)).

Your task is to determine the maximum possible beauty of the array a if you can rearrange the array a arbitrarily.

Input

The input consists of multiple test cases. The first line contains a single integer t (1≤t≤10^4)  — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤2⋅10^5)  — the length of array a.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤10^9)  — the elements of the array a.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5.

Output

For each test case, output a single integer  — the maximum possible beauty of a after rearranging its elements arbitrarily.

Example input

3
3
6 6 6
6
2 5 4 5 2 4
4
1 3 2 2

Example output

1
3
2

Note

In the first test case, a = [6,6,6] and a′ = [6,6,6]. LIS(a)=LIS(a′) = 1. Hence the beauty is min(1,1)=1.

In the second test case, a can be rearranged to [2,5,4,5,4,2]. Then a′ = [2,4,5,4,5,2]. LIS(a)=LIS(a′)=3. Hence the beauty is 3 and it can be shown that this is the maximum possible beauty.

In the third test case, a can be rearranged to [1,2,3,2]. Then a′ = [2,3,2,1]. LIS(a)=3, LIS(a′)=2. Hence the beauty is min(3,2)=2 and it can be shown that 2 is the maximum possible beauty.

Solution

The key observation is LIS(a) = LDS(a’). We don’t have to reverse the array or traverse it from the other side, we just need to know that longest increasing and longest decreasing sub-sequence should have lengths as close to each other, so the min(LIS(a), LIS(a’)) is maximized.

By constructing a frequency table we can greedily construct the solution for LIS(a) by picking all of the values in the increasing order, and then construct the LDS(a) by picking all of the values that appear more than once (since we already used them once for LIS) in the decreasing order. Having a number appear more than 2 times doesn’t matter since we can inject it so it doesn’t have any effect on the resulting LIS and LDS.

Now, the constructed LIS and LDS have dis-balanced lengths – we constructed the LIS first so it will be longer than LDS. In order to fix that we should balance it using the elements which appear only once. In ideal case, we should use half of them for LIS and the other half for LDS. This means that the solution is multiple + single / 2.

The last observation is that one of these elements can be used twice when counting the lengths of LIS and LDS, since it will be a common element on which LIS stops and LDS starts. To account for that, we modify our final solution to be multiple + (single + 1) / 2

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main(){
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        map<unsigned long long, long long> f;
        unsigned long long k;
        for (int i=0;i<n;i++) {
            cin >> k;
            f[k] = f[k] + 1;
        }

        int single = 0, multiple = 0;
        for (auto it=f.begin();it!=f.end();it++) {
            if (it->second > 1) multiple++;
            else single++;
        }
        cout << multiple + (single + 1) / 2 << endl;
    }

    return 0;
}

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given a permutation p of integers from 0 to n−1 (each of them occurs exactly once). Initially, the permutation is not sorted (that is, pi>pi+1 for at least one 1≤i≤n−1).

The permutation is called X-sortable for some non-negative integer X if it is possible to sort the permutation by performing the operation below some finite number of times:

• Choose two indices i and j (1≤i<j≤n) such that pi&pj=X.
• Swap pi and pj.

Here & denotes the bitwise AND operation.

Find the maximum value of X such that p is X-sortable. It can be shown that there always exists some value of X such that p is X-sortable.

Input

The input consists of multiple test cases. The first line contains a single integer t (1≤t≤104)  — the number of test cases. Description of test cases follows.

The first line of each test case contains a single integer n (2≤n≤2⋅105)  — the length of the permutation.

The second line of each test case contains n integers p1,p2,…,pn (0≤pi≤n−1, all pi are distinct)  — the elements of p. It is guaranteed that p is not sorted.

It is guaranteed that the sum of n over all cases does not exceed 2⋅105.

Output

For each test case output a single integer — the maximum value of X such that p is X-sortable.

Example input

4
4
0 1 3 2
2
1 0
7
0 1 2 3 5 6 4
5
0 3 2 1 4

Example output

2
0
4
1

Note

In the first test case, the only X for which the permutation is X-sortable are X=0 and X=2, maximum of which is 2.

Sorting using X=0:

• Swap p1 and p4, p=[2,1,3,0].
• Swap p3 and p4, p=[2,1,0,3].
• Swap p1 and p3, p=[0,1,2,3].

Sorting using X=2:

• Swap p3 and p4, p=[0,1,2,3].

In the second test case, we must swap p1 and p2 which is possible only with X=0.

Solution

The first observation is we must swap only the numbers which are not in their spot, so the first thing we’ll do is sort the array so we can check for each number if it needs to be moved at all.

Since swapping operation doesn’t change the positioning of the elements not participating in the swap, we know the order of the swaps doesn’t matter for the final solution. The only this that matters are the pairs of numbers participating in the swaps. Since this chain of swaps must use all of the unsorted numbers, we know the X we’re searching for must allow swapping any of the pairs in this chain. Effectively, this means applying the AND operation to all of the numbers which are out of position will give us our X.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int t;
    cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<unsigned long long> a(n);
        for (int i=0;i<n;i++) cin >> a[i];

      	// make a sorted copy of A
        vector<unsigned long long> b(a);
        sort(b.begin(), b.end());

        long long sol = -1;
        for (int i=0;i<n;i++) {
          	// needs to be swapped?
            if (a[i] != b[i]) {
              	// handle the first number
                if (sol == -1) sol = a[i]; 
                else sol &= a[i];
            }
        }
        cout << sol << endl;
    }

    return 0;
}

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given a palindromic string s of length n.

You have to count the number of indices i (1≤i≤n) such that the string after removing si from s still remains a palindrome.

For example, consider s = “aba”

1. If we remove s1 from s, the string becomes “ba” which is not a palindrome.
2. If we remove s2 from s, the string becomes “aa” which is a palindrome.
3. If we remove s3 from s, the string becomes “ab” which is not a palindrome.

A palindrome is a string that reads the same backward as forward. For example, “abba”, “a”, “fef” are palindromes whereas “codeforces”, “acd”, “xy” are not.

Input

The input consists of multiple test cases. The first line of the input contains a single integer t (1≤t≤10^3)  — the number of test cases. Description of the test cases follows.

The first line of each testcase contains a single integer n (2≤n≤10^5)  — the length of string s.

The second line of each test case contains a string s consisting of lowercase English letters. It is guaranteed that s is a palindrome.

It is guaranteed that sum of n over all test cases does not exceed 2⋅10^5.

Output

For each test case, output a single integer  — the number of indices i (1≤i≤n) such that the string after removing si from s still remains a palindrome.

Example input

3
3
aba
8
acaaaaca
2
dd

Example output

1
4
2

Note

The first test case is described in the statement.

In the second test case, the indices i that result in palindrome after removing si are 3,4,5,6. Hence the answer is 4.

In the third test case, removal of any of the indices results in “d” which is a palindrome. Hence the answer is 2.

Solution

Brute-force solution is to remove each character and check if the remaining string is palindrome, which has a complexity of O(N^2).

We can do better. First, we have to realize that removing any character at index i will shift all of the remaining letters after index i to the left, breaking the palindrome in most of the cases. The only time the palindrome won’t be broken is if the removed character belongs to the consecutive series of the same letters in the middle of the palindrome.

To show this is true we will represent our palindrome X as a concatenation of three strings: prefix P, center C and suffix S, where P = reverse(S) and center is a string made of all the same letters, so X = P + C + S. Since we can remove only a single letter, removing anything from either P or S will break the constraint P = reverse(S), so the resulting string won’t be a palindrome. The only remaining option is to remove a character from C.

Now, to prove that removing any letter from C works, we will have to consider the parity of lengths of X, P, C and S. Irrelevant of the parity of the length of X, strings P and S have the same length, so their sum must be even. This means that the parity of C is equal to the parity of X, which makes C “the center” of the palindrome. If after deleting anything from C we get a palindrome, the X will stay palindrome as well. This is always true since C is made of a series of repeated letters.

So the only thing we need to do is to count the number of repeated letters in the middle of the string, which has a complexity of O(N) – way better than O(N^2) brute force.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(){

    int t;
    cin >> t;
    while (t--) {
        int n; cin >> n;
        string s; cin >> s;

        int sol = 0;
        int x = n / 2;
        char c = s[x];
      
        // move left
        for (int i=x;i>=0;i--) {
            if (s[i] != c) break;
            sol++; 
        }
		
      	// move right
        for (int i=x+1;i<n;i++) {
            if (s[i] != c) break;
            sol++; 
        }

        cout << sol << endl;
    }

    return 0;
}