THEGME - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Sibasish Ghosh

Tester: Pritish Nayak

Editorialist: Sibasish Ghosh

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic Maths

PROBLEM:

Two teams, A and B, are playing N matches against each other. Some of the matches have already been completed i.e., the results are known for these matches. For the other matches, the results are unknown. Team A has the power to willingly win, draw, or lose a match in all the remaining matches. Your task is to tell the minimum number of remaining matches Team A must win to make sure they win the tournament, i.e., the final score of Team A must be strictly greater than the final score of Team B.

Point distribution:

  • Win: 3 points to winning team
  • Draw: 1 point to both teams
  • Loss: 0 points to losing team

QUICK EXPLANATION:

Team A can apply the following strategy for the remaining matches to ensure winning the tournament:

Win the least number of matches so that they are in the lead. After that, draw every match.

EXPLANATION:

While calculating the scores for both teams, forget about the draws. They are useless because they don’t change the difference in points between the two teams.

Notice that as soon as Team A gets a score higher than Team B, Team A can win the tournament. Because it can simply draw the remaining matches and the point difference between the two teams remains the same. So Team A can apply the following strategy for the remaining matches to ensure winning the tournament:

Win the least number of matches so that they are in the lead. After that, draw every match.

Now try to implement the approach on your own. Refer to the solutions below for implementation details if you are facing difficulties.

SOLUTIONS:

Setter's/Editorialist's Solution 
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
 
using namespace std;
typedef long long int ll;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("input3.txt","r",stdin);
    // freopen("output3.txt","w",stdout);
    ll t=1;
    cin>>t;
    while(t--)
    {
        ll n,i,winA=0,winB=0,ans=0,rem=0,f=0;
        cin>>n;
        string s;
        cin>>s;
        for(auto ch:s)
        {
            if(ch == 'W')
                winA++;
            else if(ch == 'L')
                winB++;
            else if(ch == '?') rem++;
        }
        if(winA > winB)
        {
            cout<<"0\n";
            continue;
        }
        for(i=1;i<=rem;i++)
        {
            winA++;
            if(winA > winB)
            {
                f=1;
                ans=i;
                break;
            }
        }
        if(f)
            cout<<ans<<"\n";
        else cout<<"-1\n";
    }
    return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
int main()
{
   int t;
   cin>>t;
 
   assert(t<=1000);assert(t>=1);
 
   while(t--)
   {
      int n;
      cin>>n;
      assert(n<=1000);assert(n>=1);
 
      string s;
      cin>>s;
      assert(s.length()==n);
 
      int A=0,B=0,Q=0;
 
      for(auto x:s)
         if(x=='W')A+=3;
         else if(x=='L')B+=3;
         else if(x=='D')A+=1,B+=1;
         else if(x=='?')Q++;
         else abort();
 
      int ok=1;
      for(int i=0;i<=Q;i++)
         if(A+3*i>B){
            cout<<i<<'\n';
            ok=0;
            break;
         }
 
      if(ok)cout<<-1<<'\n';
   }
 
   return 0;
}

Feel free to write your approach in the comments :slight_smile:

2 Likes