CodeChef - Suraj goes shopping

https://www.codechef.com/problems/ANUBTG

It is winter super sale and all the shops have various offers. Suraj selected N items to buy and he is standing in the billing queue. It was then he noticed the offer "Buy two, get two". That means for every two items you buy, they give you two items for free. However, items can be of varying price, they always charge for 2 most costly items and give other 2 as free. For example, if the items cost 1, 1, 2, 2, then you have to pay 4 and take all 4 items.

Suraj is busy reordering his items to reduce the total price he has to pay. He can separate the items and get them on different bills if needed. Can you tell me what is the least price Suraj has to pay to buy all the Nitems?

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. First line of each test case has single integer N. Second line of each test case has N space separated integers, which are the costs of items Suraj want to buy.

Output

For each test case, output a single line containing the required answer.

Constraints

• 1 ≤ T ≤ 1000
• 1 ≤ N ≤ 1000
• 1 ≤ Cost of items ≤ 1000

Example

Input:
3
4
1 1 2 2
2
10 200
7
1 1 10 2 2 2 1

Output:
4
210
14

Explanation

Example case 1

Suraj pays for 2 costly items and gets other 2 for free.

Example case 2

Suraj has to pay for both the items, he wont get anything for free.

Example case 3

Suraj separates the items into 2 bills. In one bill he pays 12. And in another bill he pays 2.

http://letuscode.in/index.php/2016/07/19/billing-algorithm/

A garments shop has “Buy 2, Get 2” offer for it’s customers. Whatever the items may be, they charge for costliest items from an order and give the cheapest ones free.
However we can divide the items into multiple orders to save more.

For example, Let us say we have 6 items with prices 200, 600, 100, 900, 800, 700. If we take them as one order, we will have to pay 3000.

6 items are divided into two groups {900,800,200,100}, {700,600} because they charge for highest price items. So the total bill would be 900+800+700+600 = 3000
Suppose we divide the items into two groups {900,800,700,600}, {200,100} we need to pay only900+800+200+100 = 2000

Now the problem is, given a list of prices, how do we calculate the minimum amount we need to pay?

This is a simple greedy algorithm. We just need to sort all the prices in descending order and group them into 4 per order. The last order might contain less than 4 items.

int main() {

int t;

cin >> t;

while( t-- ) {

   int n;

   cin >> n;

   vector<int> prices(n);

   int i;

   for(i = 0; i < n; i++)

   {

       cin >> prices[i];

   }

   sort( prices.begin(), prices.end(), greater<int>());

   int amt = 0;

   for(i = 0; i <= n-2; i+=4)

   {

       amt += prices[i]+prices[i+1];

   }

   if(i == n-1)

       amt += prices[n-1];

   cout << amt << endl;

}

return 0;

}

Count the squares

https://www.codechef.com/problems/D6
The problem is: given a set of N points in the plane, how many squares are there such that all their corners belong to this set?

The first line contains t, the number of test cases (about 10). Then t test cases follow.

Each test case has the following form:

• The first line contains an integer N, the number of points in the given set (4 ≤ N ≤ 500).
• Then N lines follow, each line contains two integers X, Y describing coordinates of a point (-50 ≤ X, Y ≤ 50).

Output

For each test case, print in a single line the number of squares that have vertices belong to the given set.

Example

Input:
1
7
0 0
0 1
1 0
1 1
1 2
2 1
2 2

Output:
3

Output details:
The three squares are: 
(0 0), (0 1), (1 1), (1 0)
(1 1), (1 2), (2 2), (2 1)
(0 1), (1 0), (2 1), (1 2)

https://www.codechef.com/status/D6
https://www.codechef.com/viewsolution/10228421

1. public static void main(String[] args) throws IOException {
2. Locale.setDefault(Locale.US);
3. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
4. PrintWriter out = new PrintWriter(System.out,true);
5. Point c = new Point();
6. Point d = new Point();
7. int n = Integer.parseInt(br.readLine());
8. for (int i=0; i<n; i++) {
9. int k = Integer.parseInt(br.readLine());
10. List<Point> points = new ArrayList<Point>(k);
11. Set<Point> set = new HashSet<Point>(2*k);
12. for (int j=0; j<k; j++) {
13. String s = br.readLine().trim();
14. int index = s.indexOf(' ');
15. int x = Integer.parseInt(s.substring(0,index));
16. int y = Integer.parseInt(s.substring(index+1));
17. Point p = new Point(x,y);
18. points.add(p);
19. set.add(p);
20. }
21. int count = 0;
22. for (int x=0; x<k; x++) {
23. Point a = points.get(x);
24. for (int y=x+1; y<k; y++) {
25. Point b = points.get(y);
26. int dx = b.x-a.x;
27. int dy = b.y-a.y;
28. c.x = b.x-dy;
29. c.y = b.y+dx;
30. d.x = c.x-dx;
31. d.y = c.y-dy;
32. if (set.contains(c) && set.contains(d)) {
33. count++;
34. }
35. c.x = b.x+dy;
36. c.y = b.y-dx;
37. d.x = c.x-dx;
38. d.y = c.y-dy;
39. if (set.contains(c) && set.contains(d)) {
40. count++;
41. }
42. }
43. }
44. out.println(count/4);
45. }
46. out.close();
47. }

Check if a string is a double string | Letuscode

Check if a string is a double string | Letuscode
Given a string, we need to check if a string is a double string possibly by deleting a character.
A double string is a repetition of two strings affixed together.
For example the following strings are double strings
"aa", "meme", "abbabb"
Where as the follwing are not double strings
"ab", "abc", "acbab"
However "acbab" can be be a double string if we remove "c" from it.

Case 1:
If the given string is of even length, we simply need to check if it is a double string by checking if the left half and right half are equal.
No need to consider the case of deleting a character because, if we delete a character, it’s length will be odd which will never be a double string.

Case 2:
If the string is of odd length, we have to delete a character before checking if it is a double string. How to find out which character to be deleted?

So it appears that we should try to remove each possible character and check if it is a double string. However since we want to check for a double string,
the left and right half should atleast be similar if not equal.

Consider an example “acbab”, we can divide the string into longer and shorter halves in two ways
("acb", "ab")
("ac", "bab")
Since the first pair of string differ by only character (In other words, their edit distance is just 1)

So we just need to check if the edit distance between the longer and shorter strings is at most 1.

bool is_double(string &input) {
    size_t len = input.size();
    if( len % 2 == 1 )
        return false;
    int i;
    int mid = len/2;
    for( i = 0; i < mid; i++ ) {
        if( input[i] != input[i+mid] )
            return false;
    }
    return true;
}

bool is_sub_seq(string &longer, string &shorter) {
    int i, j;
    bool mismatch = false;
    for( i = 0, j = 0; i < longer.size() && j < shorter.size(); ) {
        if( longer[i] != shorter[j] ) {
            if( mismatch ) {
                return false;//more than one mismatch; not a double string
            }
            else {
                mismatch = true; //one mismatch is fine
                i++; //skip this character from the longer half
            }
        }
        else
        {
            i++;
            j++;
        }
    }
    return true;
}

bool can_be_double(string &input) {
    size_t len = input.size();
    if( len < 2 )
        return false;
    if( len % 2 == 0 )
        return is_double(input);
    else
    {
        string longer = input.substr(0, len/2+1);
        string shorter = input.substr(len/2+1, len/2);
        if( is_sub_seq(longer, shorter) )
            return true;
        shorter = input.substr(0, len/2);
        longer = input.substr(len/2, len/2+1);
        return is_sub_seq(longer,shorter);
    }
}
Read full article from Check if a string is a double string | Letuscode

CodeChef - The Ball And Cups - Finding the number in a shuffled array

https://www.codechef.com/problems/TAVISUAL

All submissions for this problem are available.

At the end of a busy day, The Chef and his assistants play a game together. The game is not just for fun but also used to decide who will have to clean the kitchen. The Chef is a Game Master, so his concern is how to manage the game but not how to win the game like his assistants do.

The game requires players to find the only ball under one of the N cups after their positions are changed in a special way. At the beginning of the game, The Chef places N cups in a row and put a ball under the C-th cup from the left (the cups are numbered from 1 to N). All players can see the initial position of the ball. Then Chef performs Q flip operations. Each flip operation is defined by two integers L and R such that 1 ≤ L ≤ R ≤ N and consists in reversing the segment [L, R] of cups. Namely, Chef swaps L-th and R-th cups, (L+1)-th and (R−1)-th cups, and so on. After performing all the operations Chef asks his assistants to choose a cup that they think the ball is under it. Who can guess the position of the ball will win the game, and of course, the others will have to clean the kitchen.

The Chef doesn't want to check all the N cups at the end of the game. He notes down the value of C and the pairs (L, R) and asked you, the mastered programmer, to determine the cup that contains the ball.

Input

The first line of the input contains a single integer T, denoting the number of test cases. The description of Ttest cases follows. The first line of each test case contains three space-separated integers N, C and Q, denoting the total number of cups, the initial position of the ball and the number of flip operations Chef will perform. Each of the following Q lines contains two space-separated integers L and R, denoting the ends of the segment of the current flip operation.

Output

For each test case output on a separate line the final position of the ball.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 100000 (10⁵)
• 1 ≤ C ≤ N
• 1 ≤ Q ≤ 10000 (10⁴)
• 1 ≤ L ≤ R ≤ N

Example

Input:
1
5 2 3
1 4
3 5
1 5

Output:
1

http://letuscode.in/index.php/2015/12/11/finding-number-shuffled-array/

Given an array [1, 2, 3,…N], we apply a series of reversal operations on different range of indices [L,R].
How to find out the position of a number after these operations are applied?

For example consider an array of 5 numbers [1, 2, 3, 4, 5] and the number 2.

Reverse elements between 1, and 3, the array becomes [3, 2, 1, 4, 5]
Reverse elements between 3, and 5, the array becomes [3, 2, 5, 4, 1]
Reverse elements between 2, and 5, the array becomes [3, 1, 4, 5, 2]

So the final position of 2 is 5.

If we want to track just one number, we need not perform reversal operations everytime. This process takes O(n^2) time in worst case.

As we perform the reversal operations, we just need to track what is the new position of target number.

How do we track the position?
Consider the positions L = left, R= right, C = current
After we reverse the elements between L, R, C will be placed x steps before R

C – L = R – X
X = R + L – C
The new position of C will be (R+L-C)
The position of C will not be altered if we are reversing the part which includes C.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

  int t;

  cin >> t;

  while(t--)

  {

    int n,c,q;

    cin >> n >> c >> q;

    int i;

    vector<int> nums(n);

    for( i = 0; i < n; i++ )

    {

      nums[i] = i+1;

    }

    for( i = 0; i < q; i++ )

    {

      int l,r;

      cin >> l >> r;

      if( c >= l && c <= r )

      c = l+r-c;

    }

    cout << c << endl;

  }

  return 0;

CodeChef Open the Dragon Scroll - Maximum Xor of two bit patterns | Letuscode

https://www.codechef.com/problems/DRAGNXOR
Maximum Xor of two bit patterns | Letuscode
Given two numbers A, B, What is the maximum value of A' XOR B', where A', B' are obtained by permuting the binary representations of A, B respectively.
For example assume A = 3, B = 1 and they are represented in 4 bits. A = 0011, B = 0001 in binary. Suppose A' = 1100, B' = 0010, then we get the A' ^ B' = 1110 = 13. So 13 is the answer. For no other values of A', B', the XOR will be maximum.
Let us look at another example A = 3, B = 7, again represented using 4 bits. A' = 0011, B' = 1101 and A' ^ B' = 0011 ^ 1101 = 1110 = 14. So 14 is the answer.
This problem was originally appeared on Codechef. The problem has 3 inputs N (number of bits), A, B. How many 1s are possible in the result number?
Since 1^0 = 1 and 0^1 = 1, to get a 1 in the final result, We should have a

• 1 bit in A, and 0 bit in B or
• 0 bit in A, and 1 bit in B

So the total number 1s possible in the result is Minimum( 1s in A, 0s in B) + Minimum( 0s in A, 1s in B). The remaining bits are Zeros.
How should we arrange these bits to get the maximum value? All 1s should be pushed to left (Most significant bits). So the result will be of the form 1111…00
    public static void main(String []args) {
        Scanner reader = new Scanner(System.in);
        int t = reader.nextInt();
        while( t-- > 0 ) {
            int nBits = reader.nextInt();
            int a = reader.nextInt();
            int b = reader.nextInt();
            System.out.println(maxXor(nBits, a, b));
        }
    }
    private static int maxXor(int n, int a, int b) {
        int aBits = Integer.bitCount(a);
        int bBits = Integer.bitCount(b);
        int ones = Math.min(aBits, n-bBits) + Math.min(bBits, n-aBits);
        return ((1 << ones)-1) << (n-ones);
    }
Read full article from Maximum Xor of two bit patterns | Letuscode

Minimum number of squares formed from a rectangle

Minimum number of squares formed from a rectangle
Given a rectangle of some length and width, How do you divide them into minimum number of squares? This is a problem from Codechef.

For example give a rectangle of size 2 x 4, we can make them into two squares of 2 x 2.
Similarly a rectangle of size 3 x 7, can only be divided into 21 squares each of size 1 x 1.

So what is the logic behind this?
The length and width should be divided in same equal parts, and that part should as greater as possible. So we have to find the GCD(Greatest Common Divisor) of the length and width of the rectangle. Then the minimum number of squares can be calculated by
l/g * w/g. where l = length, w = width, g = GCD(l,w)

	int gcd(int x, int y) {
	while( x % y > 0 )
	{
	int r = x % y;
	x = y;
	y = r;
	}
	return y;
	}
	int main() {
	int t;
	cin >> t;
	while( t-- )
	{
	int n,m;
	cin >> n >> m;
	int g = gcd(n,m);
	cout << (n/g)*(m/g) << endl;
	}
	return 0;
	}

Read full article from Minimum number of squares formed from a rectangle

Problem solving with programming: Ambiguous permutations

Problem solving with programming: Ambiguous permutations
Given a permutation of numbers from 1 to N, We can represent it in two ways.

For example, let us consider a permutation from 1 to 5
P = [2 4 1 5 3]
This representation directly indicates the position of each number. i.e 2 is first, 4 is second and so on.

Alternatively, this can also be represented in inverse permutation form.
A = [3 1 5 2 4] 
Assuming 1-based index, each number at the index 'i' indicates that the number 'i' is positioned at A[i] in the actual permutation. So this means that 1 appears at index 3, 2 appears at index 1, and so on.

There are some cases when the actual permutation and the inverse permutation are same. We call it as anambiguous permutation. Now the problem is how do we check if the give permutation is an ambiguous permutation?

The solution is simple. We have to create an inverse permutation in another array, and check if it is same as the original permutation. Calculating the inverse permutation is discussed in my previous post.

	bool isAmbiguous(vector<int>& arr) {
	int i;
	vector<int> inverse(arr.size());
	for( i = 0; i < arr.size(); i++ )
	{
	inverse[arr[i]-1] = i+1;
	}
	for( i = 0; i < arr.size(); i++ )
	{
	if( arr[i] != inverse[i] )
	return false;
	}
	return true;
	}

http://codehob.blogspot.com/2015/04/spoj-problem-permut2-ambiguous.html

     BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

     int n=Integer.parseInt(br.readLine());

     while(n!=0){

     int per[]=new int[n+1];

     int inper[]=new int[n+1];

     String str[]=br.readLine().split(" ");

     for(int i=1;i<=n;i++){

     per[i]=Integer.parseInt(str[i-1]);

     inper[per[i]]=i;

     }

     boolean isAmbigous=true;

     for(int i=1;i<=n;i++){

     if(per[i]!=inper[i]){

     isAmbigous=false;

     break;

     }

     }

Read full article from Problem solving with programming: Ambiguous permutations