Equal Beauty CodeChef SnackDown 2021 Round 1A Question The beauty of an (non-empty) array of integers is defined as the difference between its largest and smallest element. For example, the beauty of the array [2,3,4,4,6] is 6−2=4. An array A is said to be good if it is possible to partition the elements of A into two non-empty arrays B1 and B2 such that B1 and B2 have the same beauty. Each element of array A should be in exactly one array: either in B1 or in B2. For example, the array [6,2,4,4,4] is good because its elements can be partitioned into two arrays B1=[6,4,4] and B2=[2,4], where both B1 and B2 have the same beauty (6−4=4−2=2). You are given an array A of length N. In one move you can: Select an index i (1≤i≤N) and either increase Ai by 1 or decrease Ai by 1. Find the minimum number of moves required to make the array A good. Input Format The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow. Each test
Robot Walk CodeChef SnackDown 2021 Solution
Question
Chef has recently learned robotics and has now been able to construct a robot that's much better than his robots from last year. It's still somewhat limited, but it's definitely more flexible than before. Here are its properties:
- The robot can only move forward towards the direction it faces, and can only face either horizontally or vertically.
- The robot can only turn at 90 degree angles.
- The robot is designed to turn exactly N times.
In addition, this robot is programmable. You can feed it 2N+1 values: a0, f1, a1, f2, a2, ..., fN, aN, where each ai is a positive integer and each fi is either L or R, and then it will perform the following actions:
- Initially face north.
- Move forward by a0 steps.
- If f1 is L, turn left 90 degrees; if f1 is R, turn right 90 degrees.
- Move forward by a1 steps.
- If f2 is L, turn left 90 degrees; if f2 is R, turn right 90 degrees.
- Move forward by a2 steps.
- ...
- If fN is L, turn left 90 degrees; if fN is R, turn right 90 degrees.
- Move forward by aN steps.
Now, Chef wants to test his new robot. Chef has already prepared the 2N+1 values to feed to the robot. However, Chef is very lazy and doesn't want to move, so he wants the robot to return to its starting point exactly. To do so, he can change some of the values, but some changes need time. Specifically,
- Chef can increase or decrease any ai by 1, but this takes 1 second. Also, this change is only allowed if the new ai value is positive.
- Chef can replace any fi by L or R. This takes 0 seconds.
Now, Chef wants to know the minimum number of seconds he needs to accomplish this task. Since Chef is lazy, he asks you to solve this problem for him.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N. The second line contains 2N+1 space-separated values a0, f1, a1, f2, a2, ..., fN, aN.
Output
For each test case, output a line containing a single integer, the minimum number of seconds he needs to accomplish the task. If it is impossible to perform the task, output "NO" (without quotes) instead.
Constraints
- 1 ≤ T ≤ 50
- 1 ≤ N, ai ≤ 500
- fi is either L or R
Example Input
2 3 11 L 7 L 11 R 7 3 11 L 9 L 11 R 7
Example Output
0 2
Explanation
Example case 1. Chef can replace f3 by L, which takes 0 seconds, so that the robot goes back to its starting position. Chef can also replace f1 and f2 by R instead, which also takes 0 + 0 = 0 seconds.
Example case 2. Chef can decrease a1 twice and then replace f3 by L, which takes 2 + 0 = 2 seconds, so that the robot goes back to its starting position. It can be shown that this is the minimum number of seconds Chef needs to accomplish this task.
Program Code in C++
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define f first
#define s second
#define pb push_back
#define endl '\n'
bitset<500008>b1;
bitset<500008>b2;
main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
for(int i=0; i<500008; i++){
b1[i]=0;
b2[i]=0;
}
b1[250000]=1;
b2[250000]=1;
int n;
cin>>n;
vector<int>v1;
vector<int>v2;
int s1=0;
int s2=0;
for(int i=0; i<2*n+1; i++){
if(i%2==0){
int x;
cin>>x;
if(i%4==0){
b1=(b1>>x | (b1<<x));
v1.pb(x);
s1+=x;
}
else{
b2=(b2>>x | (b2<<x));
v2.pb(x);
s2+=x;
}
}
else{
char c;
cin>>c;
}
}
if(n<=2){
cout<<"NO"<<endl;
continue;
}
int mini=1e18;
for(int i=0; i<500008; i++){
if(b1[i]==1){
mini=min(mini, abs(i-250000));
}
}
int mini2=1e18;
for(int i=0; i<500008; i++){
if(b2[i]==1){
mini2=min(mini2, abs(i-250000));
}
}
cout<<mini+mini2<<endl;
}
return 0;
}
Suggested Links
More information
CodeChef is one of the largest online coding platform and SnackDown is one of it's of grandest programs held ever year. SnackDown is a global programming event that invites programmers all over the world to participate in India's most prestigious multi-round programming competition. SnackDown is open to everyone who has a knack in programming.
This question that is Robot Walk is of CodeChef SnackDown 2021 Advanced Practice Contest. Here you will get a brief explanation of the problem and after reading the explanation if you are still stuck and have no clue to understand the problem then you can visit the solution of the question given above.
Hope you learnt something from this explanation and solution. Code it guys, practice coding more and more.
Comments
Post a Comment