Entering edit mode

Sameer loves celebrating Diwali. He has decorated his house with N LED lights. Some of these are switched on and some of these are switched off currently. He wants to maximize the total beauty of the decoration.

For the i-th light, he gives a beauty score to the light as A[i]. The total beauty of the decoration is the sum of beauty scores of all the lights which are switched on.

A p-switch is a special kind of switch which switches the state of any chosen p consecutive lights. That is, if Sameer uses a p-switch on lights starting from the i-th light, then for every light between i and i+p-1 (both inclusive), the lights which are turned on become off and vice versa.

Sameer has access to a set of such switches, i.e. there is an array M such that for each value M[i] Sameer has a M[i]-switch. He can use any of these switches any number of times on any of the lights. What is the maximum total beauty of the decoration he can achieve using these switches?

**Input**

The first line of the input contains T, the number of testcases.

For each testcase:

- First line contains space separated N and k, i.e. the number of lights and number of switches.
- The next line contains N space separated integers denoting the array A.
- The next line contains N space separated 0's and 1's which denotes whether the i-th light is on or off in the beginning, 1 denoting on and 0 denoting off.
- The next line contains k space separated integers denoting the array M.

**Output**

For each testcase, output a single integer denoting the maximum possible total beauty of the decoration which Sameer can achieve.

**Constraints**

- T <= 10^5
- Sum of N over all testcases <= 10^6
For each testcase,

1 <= k <= N/2

∀i ∈ [1, N], A[i] <= 10^9

∀j ∈ [1,k], M[j] <= N/2

**Sample Testcase**

**Input:**

```
1
5 1
10 2 9 5 7
1 0 0 1 0
```

**Output:**

```
31
```

**Explanation**

Sameer can use the 2-switch in the following order to achieve the following states:

- Apply the 2-switch on the 4th light to get the state 1 0 0 0 1.
- Apply the 2-switch on the 3rd light to get the state 1 0 1 1 1.

We see that in this state, the total beauty is 10+9+5+7 = 31. We can prove that this is the highest possible beauty.

There is an attack happening in the city of Mondstadt. Knights Jean and Kaeya each have a strategy to counter attack, but they cannot agree on which one to use. They choose to play a game to decide which strategy to enact. The game is as follows:

There are some

*n*number of**piles**of**mora/coins**, where the number of mora/coins in each pile can be given by the**array***a1, a2, ... an***Starting with Jean**, each player takes turns to take some action on a**single selected pile of the player's choice**. The actions are of two sorts:**Remove one mora from the pile.**If this was the last mora in the pile then the pile is said to be removed, and nobody can select this pile further**Split the pile into two non-empty piles**, for example a pile of**10**mora can be split into piles of**7**mora and**3**mora.The player which cannot make any further move, i.e., there are no remaining piles to take an action on,

**loses**.

They would play *T* games of this sort, each with different starting piles. If they both play optimally, **predict which knight would win in every game.**

**Input Format**

First line contains a single integer *T*, then the description of *T* games follow:

The first line of each game contains a single integer *n*

The second line of each game contains n space separated integers, a1, a2, ... an

**Constraints**

- 1 <= T <= 10^5
- Sum of n over all games <= 10^6
1 <= ai <= 10^9

**Output Format**

Output *T* lines, each containing either '**Jean**' or '**Kaeya**' according to who won the game.

**Sample Testcase**

**Input**

```
4
1
3
2
2 2
5
84 20 150 64 99
6
2 1 4 1 2 3
```

**Output**

```
Kaeya
Kaeya
Kaeya
Jean
```

Initially given an empty matrix of size N*M, process Q queries of type*i, j, v*.

- Fill value vin empty cell (i,j).
- Print the number of ways to fill up rest of the cells in matrix such that xor of the values in the 4 corner cells of any rectangular submatrix is 0. Note that only values in the range
*[0,(2^30)-1]*can be filled in. Since the number would be pretty large, print the answer modulo 10^9 +7.

Note that after certain query, it might also be possible that there are no ways to fill up the matrix to satisfy the given condition. Print 0 in that case.

It is guaranteed that cells won't be repeated in queries.

**Constraints**

- 2 <= N, M <= 10^9
- 1 <= Q <= min(10^6, N*M - 1)
- 0 <= v <= 2^30
- 1 <= i <= N
- 1 <= j <= M

**Input Format For Custom Testing**

**Sample Case 0**

**Sample Input For Custom Testing**

```
2 2 3
1 2 4
2 2 7
2 1 3
```

**Sample Output**

```
536396504
73741817
1
```

**Explanation**

After the 3rd query, 3 cells of the matrix are filled, so the 4th cells can only have value o such that O xor 4 xor 3 xor 7 = 0. Therefore, number of ways = 1.

**Sample Case 1**

**Sample Input For Custom Testing**

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

**Sample Output**

```
489373567
560523804
```

*Franky* is fighting some monsters, nicknamed Jadoos, which generate their energy using the sun.

To counter this, Franky has created a device which can cast long shadows on the battlefield. It consists of **three rods of lengths** *H, d* **and** *h* **welded together at right angles**, and **a light source at the top of the rod of length** *H*. Look at the diagram below to get a better understanding of this device.

Now Franky has *n* different ideas for lengths *(H, d, h)* using which to create the device but is unsure which would be better for combat. Given these n values of lengths *(H, d, h)*, **print the indices of rods sorted from largest shadow generated to smallest shadow generated**. If for two devices, the shadow generated has the same length, output the index of the device which has its **shadow end point farther, first**. If this is the same as well, output the **lower index first**.

**Input Format**

First line contains a single integer *n*

The next *n* lines contains **3** space separated integers, where the *ith* line contains *H, d* and *h* values of the *ith* idea.

**Constraints**

- 1 <= n <= 10^6
- 1<= h < H <= 10^6
- 1 <= d <= 10^6

**Output Format**

Output *n* space separated integers corresponding to the indices sorted in the required order.

**Sample Testcase 0**

**Input:**

```
6
10 2 9
10 1 9
6 1 5
10 1 8
6 2 3
2 1 1
```

**Output**

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

**Explanation**: The shadows generated by the ideas are 18,9, 5, 4, 2 and 1 respectively, so they would be ordered in the way given by the answer.

**Sample Testcase 1**

**Input:**

```
2
10 1 8
5 1 4
```

**Output:**

```
1 2
```

**Explanation :**

The lengths of shadows generated as well as the end point of the shadow generated are equal for both the ideas. So the lower index 1, comes first.

Entering edit mode

Topics involved: Basic Mathematics, Sorting

*Finding Shadow length*

- The basic idea to find the shadow is to find a relation between shadow and the given (H , d , h).
- From the above plot, Slope of line connecting (0,H) -> (d,h) is same as (d,h) -> (d+shadow,0)
- Hence , their ratio should be same , so slope == (H-h)/d == h/Shadow
- Shadow = h*d/(H-h)
- This gives us an O(1) method to directly find the length of the shadow for a particular (H,d,h)

*Sorting the data*

- For each index "i" , append ( Shadow_i , i ) to a new result array.
- Sort this array using any Nlogn sorting algorithm such that first priority of sorting is given to shadow_i , second priority is given to the index "i"
- The above can be achieved using a custom comparator as well.

```
void sortingShadows(vector<vector<int>> &data){
vector< pair<long double,int> > result;
for(int i = 0 ; i< data.size() ; i++){
int H = data[i][0];
int d = data[i][1];
int h = data[i][2];
long double shadow = (long double) h*d/(H-h);
//negative shadow is put to give decreasing order while sorting.
result.push_back(make_pair(-shadow,i));
}
sort(result.begin() , result.end());
// extract the indexes.
vector<vector<int>> sequence;
for(auto i : result){
sequence.push_back(i.second);
}
return sequence;
}
```

```
def sortingShadows(data):
result = []
for i in range(len(data)):
H = data[i][0]
d = data[i][1]
h = data[i][2]
shadow = h*d/(H-h)
# negative sign is put to give decreasing order while sorting.
result.append((-shadow,i))
result.sort()
# extract the indexes
result = [i[1] for i in result]
return result
```

Entering edit mode

**Topics Involved :** Mathematics , DSU

If only one p-switch is given, we can think of some way to flip a required bit in the array.

We can perform two consecutive operations, as follows:

Here, we flipped the 1st bulb (0-indexed), but in doing so also flipped the 4th bulb. As we can see from this example, if we try to flip ith bulb in such a way, (i+p)th bulb would also be flipped.

Hence, in a way, we can create p sets, where the 1st set contains bulbs on (0,p,2p,3p...) indices, 2nd set contains bulbs on (1,p+1,2p+1,....) indices and so on, and we can flip the states on any consecutive elements in a single set.

From this, we can observe this if there are even number of '0' (bulb state) in some set, we can flip the states on consecutive elements within the set to make it so that there are no '0' in this set, but if there are odd number of '0', 1 '0' would be left, as that would not be able to pair with another '0' to become '1'. But, we can place that zero anywhere in the set, and for the optimal answer, we will always choose the one with the least beauty value within the set.

Hence, we will get an answer, where if there are even number of '0' in a set, we add the beauty of all the elements belonging in the set, but if there are odd number of '0' in the set, we add the beauty of all the elements except the minimum one.

Only one case is left here, because by doing only one p-switch operation on the original string, we can change the sets which contain even number of '0' to odd number of '0', and vice versa.

**Proof for the above statement**: Taking any p-switch on any index, we can see that all the points in the range [i....i+p-1] belong to different sets. As they belong to different sets, and the states of all the bulbs would be changed. Let's say in some set, odd number of '0' were present, and the element in this range was '0', it would be changed to '1' which would change the parity of number of '0'.

Hence, changing the parity, we need to calculate the answer again, and output the max of both the cases (one we calculated above, and one calculated here).

The effect of all the switches can be produced by taking one switch with p = gcd of all the switch values.

**Proof**

Let's say we have two switches, with values a and b (WLOG, assume a<b)

Look at the following image for reference:

As we can see, we created a switch with value b-a, by using switches with value a and b.After this, we can use switches with value b-a and a to create a switch of a-(b-a), and so on...

We can observe that this is exactly the algorithm for calculating gcd of a and b. Hence, we can use the value of a switch to be gcd of a and b to get the same effect.

This can also be extended for multiple switches.

Hence, given multiple switches as in the question, we can calculate gcd of all the switch values and calculate the maximum beauty using that by the approach discussed.

```
vector<int> dsu;
int find(int a)
{
if(a==dsu[a])
return a;
return dsu[a]=find(dsu[a]);
}
void unn(int a,int b)
{
a=find(a);
b=find(b);
dsu[a]=b;
}
int solve(string s,vector<int> arr,vector<int> m)
{
int mx=0;
for(auto x:arr)
mx+=x;
int mx2=mx;
int n=arr.size();
int k=m.size();
dsu.assign(n,{});
for(int i = 0;i < n;i++)
{
dsu[i]=i;
}
int g=0; // gcd of all the switches
for(auto x:m)
g=__gcd(x,g);
for(int i = 0;i < g; i++) // creating the sets
{
int j=i;
while(j<n)
{
unn(i,j);
j+=g;
}
}
map<int,int> indexMap; // for ease
int id=0;
for(int i = 0; i < n; i++)
{
if(indexMap.find(find(i))==indexMap.end())
{
indexMap[find(i)]=id++;
}
}
vector<vector<int>> v(id);
vector<int> cnt(id);
for(int i = 0;i < n;i++)
{
v[indexMap[find(i)]].push_back(arr[i]);
if(s[i]=='0')
cnt[indexMap[find(i)]]++,cnt[indexMap[find(i)]]%=2;
}
for(int i = 0;i < id;i++) // calculating the answer
{
sort(v[i].begin(),v[i].end());
if(cnt[i]==0) // using current parity of the sets
mx-=v[i][0];
else // after changing the parity of the sets
mx2-=v[i][0];
}
return max(mx,mx2);
}
```

Loading Similar Posts