- At first , we want to say sorry for our many mistakes. Please forgive us those mistakes like Bad statement ,capitalization , Bolding , Lack of latex/Pretty formating etc. we are totally unaware of those mistakes. Next time we will try to overcome those mistakes .
- Second one , Our B was match with one of codechef problem. But we are totally unaware of that. If we knew that we must be removed that problem .
- It was just a practice contest . So if you enjoy a little bit , it's out pleasure.
There Have many Solution and approach of any problem . We will discuss here only one approach for every problem which we found easy way .
Contest Announcement link : https://codeforces.net/blog/entry/83016
Previousely you could only virtually , now the contest is open for practice .
Invitation link for the contest : https://codeforces.net/contestInvitation/df49ade9db566204acd3653a7c3cacad088f6f1e
For a square-Field exclude the pillar we can choose any of four side of the pillar.. But answer will be the maximum one. Suppose think in a 5*5 Field a pillar on (4,3).
- Right side you can choose max 1*1 field ( Blue Area ). Right = (L-x)*(L-x)
- Upper side you can choose max 2*2 field (Yellow Area) . Upper = (y-1)*(y-1)
- Left side you can choose max 3*3 field ( Green Area ) . Left = (x-1)*(x-1)
- Down side you can choose max 2*2 field (Orange Area ) . Down = (L-y)*(L-y)
So Left one is the max .
mx = max( (L-x) , (y-1) , (x-1) , (L-y) )
answer = mx*mx = 3*3 = 9
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll l;
cin >> l;
ll x, y;
cin >> x >> y;
ll mx=max(max(max(l-x,x-1LL),y-1LL),l-y);
cout<<mx*mx<<endl;
return 0;
}
Idea & Tutorial & Solution : Rudro25
Find the two subarray (s1, s2; |s1| >= |s2|) with maximum length and they are different(it is not allowed to choose an any index of the array for both subarray) where all elements are equal to 0.
At first |s1| = |s2| = 0
It is proved that other subarrays are unnecessary.
It is also proved that if((|s1| / 2) > |s2|) Alice will win. Otherwise Bob will win.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[1000005];
int main()
{
int n, ct = 0;
cin >> n;
vector <int> ve;
ve.push_back(ct);
for(int i = 0; i < n; i++){
cin >> a[i];
if(a[i] == 0) ++ct;
else{
ve.push_back(ct);
ct = 0;
}
}
ve.push_back(ct);
sort(ve.rbegin(), ve.rend());
int alice = (ve[0] + 1) / 2;
int bob = ve[0] / 2;
bob = max(bob, ve[1]);
if(bob >= alice) cout << "Bob" << endl;
else cout << "Alice" << endl;
return 0;
}
Idea : Rudro25 Tutorial & Solution : Muhammad_Saidul_Islam
Here we can try for all , from 1 to string-length .
And for 1 , we will try to make no of appearence for all character is 1 from A to Z which are present .For this we will delete or insert as we need.
And for 2 , we will try to make no of appearence for all character is 2 from A to Z which are present .For this we will delete or insert as we need.
And for 3 , we will try to make no of appearence for all character is 3 from A to Z which are present .For this we will delete or insert as we need.
-----------
-----------
-----------
-----------
#include <bits/stdc++.h>
using namespace std;
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
int cnt[26];
int main(){
FastIO
string s;
cin>>s;
long long len=s.length();
for(int i=0;i<len;i++) cnt[s[i]-'A']++;
long long ans = 1e18;
for(int i=1;i<=len;i++){
long long sum = 0;
for(int j=0;j<26;j++){
if(cnt[j]) sum += abs(cnt[j]-i)*1ll*(j+1);
}
ans = min(ans, sum);
}
cout<<ans<<endl;
return 0;
}
Idea : Muhammad_Saidul_Islam Tutorial & Solution : Rudro25
Muhammad_Saidul_Islam's solution with less complexity :
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ct[27];
int main()
{
string st;
cin >> st;
for(int i = 0; i < st.size(); i++)
++ct[st[i] - 'A' + 1];
ll ans = 1e17;
for(ll i = 1; i <= 26; i++){
ll c = 0;
if(ct[i] > 0){
for(int j = 1; j <= 26; j++){
if(ct[j] != 0){
ll v = abs(ct[i] - ct[j]);
c += (v * j);
}
}
ans = min(ans, c);
}
}
cout << ans << endl;
return 0;
}
Here we have make a team with x energy one with two other people greater than equal 3x energy as much as can. So its always optimal to get lowest n killed. Just sort the array .
Use two loop like below with two pointers .
j=n+1;
for i=1 to i=n
for j=present_value to j=3*n
if(found two people geater than equal 3x eanergy than i-th people) ans++,j++,break;
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
int main()
{
FastIO
ll n;
cin>>n;
n*=3;
vector<ll> a(n);
for(ll i=0;i<n;i++) cin>>a[i];
sort(a.begin(),a.end());
ll ans = 0,j=n/3;
for(ll i = 0; i < n/3; i++){
ll cnt=0;
for( ;j<n;j++){
if(a[j]>=(3LL*a[i])) cnt++;
if(cnt==2LL){
j++,ans++; break;
}
}
}
cout << ans << endl;
return 0;
}
Idea & Tutorial & Solution : Rudro25
E. Absolute value and divisors
Here we can solve it easily using k vaule . Cause max value of k is 10^3.
- In the input can be contain with duplicate value but we don't need those .Cause we have to find unique pair.. So we just take the unique value by set . And store those value to a vector.Cause we can access vector index easily.
- Then we use 2 loop.
for i=1 to v.size()
for j=i+1 to v.size()
ll dif=v[j]-v[i] , if(dif>k) break, else if(dif%k==0) ans+=2; // here we use +=2 cause if there have pair
(1,5) then there have must be (5,1) pair and both are unique.
Here, the main tricks is ,, 2nd loop continue at most 10^3 time .Cause vector is sorted (we use set before) and there have not any duplicate value.. So,(v[j]-v[i]) > 10^3
before continue the 2nd loop for 10^3+1 times.
So, max complexity is(10^5 * 10^3 = 10^8)
And it passed easily with time limit.
#include<bits/stdc++.h>
using namespace std;
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
int main() {
FastIO
int n, k;
cin >> n >> k;
set<int> se;
for (int i = 1; i <= n; i++) {
int a; cin >> a;
se.insert(a);
}
vector<int> v(se.begin(), se.end());
n = v.size();
long long ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int d = v[j] - v[i];
if (d > k) break;
if (k % d == 0) {
ans += 2;
}
}
}
cout << ans << '\n';
return 0;
}
Idea : Muhammad_Saidul_Islam Tutorial & Solution : Rudro25
Muhammad_Saidul_Islam's solution with less complexity :
#include<bits/stdc++.h>
using namespace std;
vector <int> di;
void divisors(int x){
for(int i = 1; i * i <= x; i++){
if(x % i == 0){
di.push_back(i);
if(i * i != x) di.push_back(x / i);
}
}
sort(di.begin(), di.end());
}
int main()
{
int n, k;
cin >> n >> k;
divisors(k);
vector <int> ve;
map <int, int> mp;
for(int i = 0; i < n; i++){
int a;
cin >> a;
if(mp[a] == 0){
ve.push_back(a);
mp[a] = 1;
}
}
sort(ve.begin(), ve.end());
long long int ans = 0;
for(int i = 0; i < ve.size(); i++){
for(int j = 0; j < di.size(); j++){
int v = ve[i] + di[j];
if(mp[v] == 1) ++ans;
}
}
cout << ans * 2 << endl;
return 0;
}
We have to find the longest sorted minimum sub-sequence (LSMS) .
string ss[30] .
Here if s[i]='a' then ss[0] store from 0 to i LSMS string which last character is a.
if s[i]='b' then ss[1] store from 0 to i LSMS string which last character is b.
if s[i]='c' then ss[2] store from 0 to i LSMS string which last character is c.
-----------
-----------
-----------
suppose think s=abab..
For 1st index the LSMS is a. How can we find that, we can easily made a loop from ss[0] to ss[0] and find the maximum length one.Here longest sorted minimum one ss[0]=" " and then we add 'a' with that longest sorted minimum string . ss[0] = ss[0]+ 'a' = a.
For 2nd index The LSMS is ab.. we can easily made a loop from ss[0] to ss[1] and find the maximum length one..Here longest sorted minimum one ss[0]=a and then we add 'b' with thatlongest sorted minimum string . ss[1] = ss[0]+ 'b' = ab.
For 3rd index The LSMS is aa.. we can easily made a loop from ss[0] to ss[0] and find the maximum length one..Here longest sorted minimum one ss[0]=a and then we add 'a' with thatlongest sorted minimum string . ss[0] = ss[0]+ 'a' = aa.
For 4-th index The LSMS is aab.. we can easily made a loop from ss[0] to ss[1] and find the maximum length one..Here longest sorted minimum one ss[0]=aa and then we add 'b' with that longest sorted minimum string . ss[1] = ss[0]+ 'b' = aab.
Then just make a loop from 0 to 25 check ss[0] to ss[25] to find the longest sorted minimum sub-sequence .
#include <bits/stdc++.h>
using namespace std;
#define loser return 0
#define ll long long
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
string ss[30];
int main(){
FastIO
ll n;
string s,answer;
cin>>s;
ll len=s.length();
for(ll i=0;i<len;i++){
ll ch=s[i]-'a';
ll mx=0;
string aux;
for(ll j=0;j<=ch;j++){
if((ss[j].size())>mx){
aux=ss[j];
mx=ss[j].size();
}
}
ss[ch]=aux+s[i];
if(ss[ch].size()>answer.size()) answer=ss[ch];
else if(ss[ch].size()==answer.size()) answer=min(answer,ss[ch]);
}
cout<<answer.size()<<endl;
cout<<answer<<endl;
loser;
}
Idea & Tutorial & Solution : Rudro25
waiting for the next round and thanks for the editorial.
Since these problems are unofficial and CF does not give them ratings, Can you mention what are them based on your experience?
In problem D : Let's take this input :
2
1 3 3 4 6 6
The editorial solution output is 1 team, but it can be 2 like this : 1 3 4 and 3 6 6
Am I wrong ?
$$$ 3 \times 3 \nleq 6$$$