CHEFCH - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester: Pushkar Mishra
Editorialist: Florin Chirica

PROBLEM

You’re given a string of + and - symbols. A string is called a chain if it does not have two or more equal characters. Our target is to convert the given string into a chain. For doing that, you can flip a character (from + to - and vice versa) of the string. Find out minimum number of flips needed.

QUICK EXPLANATION

We can notice that by fixing the first character, the rest of the chain is also fixed. There are two ways to fix the first character, by putting either + or -. For both of these possibilities, we can find minimum number of flips needed and take minimum of both to get our final answer.

EXPLANATION

Fixing first character fixes entire chain

We can notice that by fixing the first character, the rest of the chain is also fixed.

If the first character is +, the second one must be -, the third one must be + and so on.
So, the final string will be something like +-+-+- which is a valid chain.

Similarly, we can say the same when the first character of chain is -.

Computing minimum number of flips needed to convert a string init into a fixed chain fin

Given two strings init and fin (init is the initial string, fin is the desired chain), the task now becomes to compute number of positions i where init[i] \neq fin[i]. If we find such a position, we’re forced to make a flip. Otherwise, we don’t need any flip.

Computing the final answer

There are two possibilities for chain fin given as follows.

  • +-+- \dots
  • -+-+- \dots

So we can try each one of these. For each case, we can compute the number of differing position between it and the initial array as stated above.

As we have to find overall minimum number of flips needed, we can take minimum of both of these cases.

Time Complexity

Since computing the number of differing position between two strings of size n takes O(n) time. We do this for two cases, so the overall complexity is also O(n).

Subtask 1 Solution
As length of string s is very small (|s| \leq 10), we can brute-force over all possible flips in s. As each character can be either + or -, there are total 2^n possibilities which will be at max 1024 for the given n.

Time Complexity
We are brute-forcing over all possible 2^n strings, for a fixed string we need \mathbb{O}(n) time. So overall time required will \mathbb{O}(2^n * n)

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester’s solution

Setter’s solution

2 Likes
2

I solved it this way:
Assumed that the desired string starts with a ‘-’ and then compared how many changes I’ve to make for it (checked if the input string character matches the expected character, if not, incremented the count by 1).
Now, we have the number of changes we are supposed to make if we want the string to start with a ‘-’. And the number of changes we are required to make if the string starts with a ‘+’ is n-count. Hence, the desired answer is minimum(count,n-count).

My solution

1 Like
3

Wish I could test my solution but can’t test it after it is over but I took a slightly different approach.

  1. convert input to binary string by replacing - with 1 and + with 0
  2. Generate an ideal binary string of the same length
  3. Convert binary string to an int or hex or whatever just something that you can XOR
  4. XOR the input value and ideal value get count the number of 1’s in the binary string
  5. Repeat 2 through 4 but generate ideal string starting with 0
  6. Compare the two different counts and return the smallest value

Would this have worked?

4

I use same logic in Java but i got error wrong ans pls any body help me with me code…
MyJavaCode

5

@skiGeek- i believe it should work.

public class FixTheChain {

public static void main(String[] args) {
	
	String chain="---+-+-+++";
	chain=chain.trim().replace(" ","").replace("-", "1").replace("+", "0");
	Integer val =  Integer.parseInt(chain,2);
	
	//generate ideal string1
	String str1="";
	String idealStr1="";
	String  idealStr2 =""; 
	for(int i=0;i<chain.length();i++){
		idealStr1+= i%2==0?"0":"1";
		idealStr2+= i%2==0?"1":"0";
	}
	Integer idealVal1 =  Integer.parseInt(idealStr1,2);
	Integer idealVal2 =  Integer.parseInt(idealStr2,2);
	System.out.println(Integer.toBinaryString(val));
	System.out.println(Integer.toBinaryString(idealVal1));
	System.out.println(Integer.toBinaryString(idealVal2));
	int dec1=val^idealVal1;
	int dec2=val^idealVal2;
	System.out.println(Integer.toBinaryString(dec1));
	System.out.println(Integer.toBinaryString(dec2));
	int finalVal1=Integer.toString(dec1).replace("0", "").length();
	int finalVal2=Integer.toString(dec2).replace("0", "").length();
	
	System.out.println (finalVal1>finalVal2?finalVal1:finalVal2);
	
	

}

}

6

Yep looks basically the same to my solution. My only other idea would be rather than looping through to get the ideal string would be to figure out the formula for a the decimal equivalent of the binary value that would be produced by a binary alternating string of that length. I can figure out the looping code but was trying to figure out a mathematical formula that given n bits this would be the decimal value of the ideal string.

IE: input string of 7 the ideal string would have a value of 2^6+2^4+2^2+2^0 now if I could just recall how to convert that into an equation.

7

MY SOLUTION IS ON

MY CODE IS GIVEING RIGHT ANSWER FOR EVERY CASE
PLZ HELP ME TO FIND THE BUG.

8

http://www.codechef.com/viewsolution/6204629
50 points for the subtask 3 , but WA for above two tasks even when am getting correct results. HELP

9

thanks @akshayspeaks

10

Can you provide sample test cases I think my solution is right I am not able to find my mistake please can you help?
https://www.codechef.com/viewsolution/15734498