Educational Codeforces Round 153 (Rated for Div. 2) Editorial

Welcome to the editorial for Educational Codeforces Round 153, Rated for Div. 2. In this editorial, we’ll delve into the solutions with complete logic and approach I used for solving the three problems: “Not a Substring” (Problem A), “Fancy Coins” (Problem B), and “Game on Permutation” (Problem C).

A. Not a Substring

import java.util.*;
public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while (t--> 0) {
      String s = sc.next();
      if (s.equals("()")) {
        System.out.println("NO");
        continue;  //come out of loop to next test case
      } 
      else {
        System.out.println("YES");
        StringBuilder sb1 = new StringBuilder(""); //sb1 is of type (((())))
        for (int i = 0; i < s.length(); i++) sb1.append('(');
        for (int i = 0; i < s.length(); i++) sb1.append(')');
        StringBuilder sb2 = new StringBuilder(""); //sb2 is of type ()()()
        for (int i = 0; i < s.length(); i++) sb2.append("()");
        if (sb1.toString().contains(s)) {
          System.out.println(sb2.toString());
        } else {
          System.out.println(sb1.toString());
        }
      }
    }
    sc.close();
  }
}

LOGIC —

THE LOGIC I REALIZED AFTER SOLVING THIS QUESTION —

The question has told us about a string “s” of “)” and “(“ with a length of “n”. We are asked to find another string of length 2n, which makes a sensible arithmetic valid bracket sequence.

Now there can be three cases:

I: ((((….))))

II: ()()()…

III: combination of the above two cases I and II may be like ()(())()

Now think of this, what is a common substring between I and II: It’s — () and there is no other common substring between I and II

In fact, this () is the only possible length-2 valid bracket sequence and is one pattern that will exist in all valid bracket sequences.

So, s==”()” cannot make a valid t because otherwise t will always contain this. So say no to this.

Now we have already been given the string “s” and we made a valid bracket string “t” of length 2 * s.length i.e., we made the two strings of case I and II of length 2 * s.

Let’s say the string “s” is not () and it exists as a substring in case I.

From our above discussion, we can guarantee that it now cannot be a substring in II and vice versa. Hence all we need to do is print the other string that will not have substring “s”.

LOGIC I worked when giving the contest —

We are given string “s” We need to find another string “t,” of double the length of “s,” which can be a valid arithmetic bracket sequence and also not containing “s” as a substring.

“s” can contain any number of “(“ or “)”, what is needed is it should be double in length.

After observing test cases: The only time when “t” cannot exist will be when “s”=”()”, because the solution “t” has only two cases: “(())” or “()()”

And here “s” is a substring in both. So, for “s”=() return no else yes

Now the real question is how to find “t”

eg: “s”=)( then “t” cannot be ()() because “s” here is a substring possible “t” is (())

Analyzing regular bracket formation can be of three types —

I: all separate: ()()()….

II: one placed inside the other: ((((….))))

III: a combination of the above two

Problem asking? Now we need to find “t” of 2 * s.length() and does not have “s” as a substring.

All we need to do is generate a string of case I and II and check whichever does not contain “s” is our answer.

B. Fancy Coins

import java.util.*;
public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while (t--> 0) {
      int sum = sc.nextInt(); //total amount to pay
      int k = sc.nextInt(); //value k
      int a1 = sc.nextInt(); //coins of value 1
      int ak = sc.nextInt(); //coins of value k
      int fancyk = 0;
      int fancy1 = 0;
      int ans = 0;
      //use ak coins
      int akcoinsused = Math.min(ak, sum / k);
      sum -= k * akcoinsused;
      //use a1 coins
      sum = Math.max(0, sum - a1);
      if (sum > 0) { //still need to pay more time to use fancy coins
        //use fancy coins worth ak
        fancyk = sum / k; //we utilise fancyk to fullest and if sum<k; the division simply returns 0 fancyk used
        fancy1 = sum % k;
        ans = fancyk + fancy1;
        if (a1 >= k - fancy1) { //let's compromise with a1, k-fancy1 is a way of saying by how much can we compromise to reach next k
          fancyk = 1 + sum / k;
          fancy1 = 0;
          int ans2 = fancyk + fancy1;
          ans = Math.min(ans, ans2);
        }
      }
      System.out.println(ans);
    }
    sc.close();
  }
}

LOGIC —

sum = m = total amount to pay
a1 = no of coins worth 1
ak = no of coins worth k
What the questions want us to do is to use as minimum fancy coins as possible

Regular coins — coins worth 1 (~a1 coins) and coins worth k (~ak coins)
Fancy coins — infinite coins worth 1 and k

First we will start by spending ak coins, then a1 coins.
Then finally we will try to use fancy coins to cover the remaining sum.

How many ak coins can we use with the thought that we want to use the maximum number of ak coins?
useak = Math.min(ak, m/k); => m/k = total number of ak coins required.

So, either ak_required exceeds ak given to us or otherwise we can utilize all the ak.
We will get the number of ak we will be putting to use.

So, remaining sum => sum = sum — (value of useak)

=> sum -= Math.min(k * ak, (m/k) * k);

=> we are multiplying here with k since we need to find values by subtracting the actual worth of useak coins.
sum -= k * (ak_coins_used)
Note that: (m/k) * k => actually represents something equivalent to Math.floor(m/k) * k

=> since we are calculating the number of coins, we would be needing a floor value.

Now we are to utilize a1 coins? What will be the best possible way?
remaining sum => sum = sum — 1 * a1;
=> sum -= a1
So, if sum <= 0 => we are sufficient enough to pay the sum by ourselves without needing fancy coins.

Otherwise, if sum [sum > 0] is still left to be covered now it’s time to use fancy coins:
Again to use the minimum possible no. of fancy coins we will try to use the k worth fancy coins first in the same way we did as above.
fancyk = (sum/k) * k; again here we are here considering how many k worth fancy coins could be used.
remaining sum => sum -= (sum/k) * k;

Now time to use fancy1 worth 1 coins: i.e., if sum is still not become zero and is left to cover
fancy1 = remaining sum = sum

So, our answer = minimum number of fancy coins used = fancyk + fancy1

NOTE:
We could have directly done this in above steps instead of again reducing sum:
fancyk = sum/k;
fancy1 = sum%k;

But the above formulas help us to realize, And seeing testcase III and realizing their magnitude:
Conclusion:
sum % k > sum / k + 1
That means using one more fancyk coin reduces our total usage of fancy coins by compromising in the start by spending lesser a1 coins as done in testcase 3.
Hence to minimize usage of fancy coins we will prefer:
fancyk = sum/k + 1 when a1 >= k — sum % k
a1 >= k — fancy1 or, a1 >= k = sum % k => is a way of finding out that to reach next k to use fancyk coins, are there enough a1 coins to compromise.

Now we also need to check whether doing the compromise was beneficial or became a burden.
So, just compare the two answers at last for the greedy and the compromise and return the minimum answer.

C. Game on Permutation

import java.util.*;
public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while (t--> 0) {
      int n = sc.nextInt();
      int arr[] = new int[n];
      for (int i = 0; i < n; i++) {
        arr[i] = sc.nextInt();
      }
      int count = 0;
      int fm = arr[0]; //firsmin
      int sm = Integer.MAX_VALUE; //secondmin
      for (int i = 0; i < arr.length; i++) {
        fm = Math.min(fm, arr[i]);
        if (arr[i] > fm && sm > arr[i]) {
          sm = arr[i];
          count++;
        }
      }
      System.out.println(count);
    }
    sc.close();
  }
}

LOGIC —

Alice makes the first move.
A chip is placed on a number, the next player needs to move the chip to the next lower number.
The one unable to make a move wins the game.

We need to find the number of indexes that are lucky for Alice to win in the array.

Some observations:
Picking the first element is never an option; otherwise, Bob will win the game, since he won’t be able to make a move.
If Alice uses the second index, she can only win if the first index is strictly smaller than the second index.

What’s the perfect strategy for Alice to win?
How about we think of indexes for which, if Bob were to put chips on, he would lose? In other words, places from where the chip cannot be moved further to the left.
That condition would be a[j] > a[i] for every j < i. And it should occur only once in any subarray.
That’s the perfect winning strategy for Alice.

For that to happen, we take two variables: firstmin (fm) and secondmin (sm).
If our current element becomes something like: sm < curr && curr < fm
If we find the above condition, then curr is a winning position for Alice,
and we will update curr = sm and move forward.

Note: You might think of a wrong idea that if the number of elements to the left of any index (i) is smaller and odd in frequency, we can guarantee that Alice will win.
No, you cannot guarantee that because what if Bob moves the chip directly to the second-to-last piece? Nothing’s stopping him from doing so, right.

LINK TO CODES

All the codes are available on my GitHub repo — repo link

DO THIS OR I WILL BE SAD 🥺

It would be great if you can also share your explanation with us if you did something different and would consider it worth sharing otherwise best of luck solving these problems.

Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing article.

Who am I?

Just someone who is enthusiastic to write what he likes. Tech blogs, latest tech news, tutorials, Coding question solutions, Editorials, Interview Tips and many more stuff that you are bound to like.

Also, I write articles for freelancing so you can contact me through the below link.

If you liked this article, do support me in this endeavor by following me on medium and get latest updates to my amazing and helpful articles.

You can encourage me to write more on: https://ko-fi.com/medusaverse

I will be happy to Connect with you : https://linktr.ee/harshit_raj_14

Did my articles amaze you? Why not subscribe to my newsletter to get the first update whenever I upload a new one:

https://medium.com/@Harshit_Raj_14/subscribe