ADACRA - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Alei Reyes
Primary Tester: Hussain Kara Fallah
Secondary Tester: Kacper Walentynowicz
Editorialist: Hussain Kara Fallah

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given a string consisting of characters U,D. In a move you can select a consecutive substring and flip all characters belonging to. (U changes to D and vice versa). What’s the minimum number of moves to make all characters equal?

EXPLANATION:

The first thing that will come up to our minds is that we should split the string from the beginning into a block of consecutive ‘U’ characters, followed immediately by a block of consecutive ‘D’ characters, then a block of ‘U’ characters, then a block of ‘D’ characters… etc. (Of course if our string starts with D then the letters are the opposite). And flip the D blocks.

The number of D blocks = (The number of U blocks) or (the number of U blocks + 1)

If our string starts with D then

The number of U blocks = (The number of D blocks) or (the number of D blocks + 1)

so our answer would be [number of blocks / 2] (of course rounded down).

Example:

Consider our string was “UUUDDUUUDDDUU”

We would split it into :

[UUU] , [DD] , [UUU] , [DDD] , [UU]

The best solution is to flip [DD] , [DDD]

Another Example :

Consider our string was “DDDUDDUU”

We would split it into :

[DDD] , [U] , [DD] , [UU]

Here because the number of U blocks is equal to number of D blocks then flipping the blocks of any letter would be optimal.

Why is this always correct?

If we are looking for a better solution than the mentioned above, then we should flip at least 2 of our targeted blocks at once. But that’s impossible because we would affect at least one proper block between them (consisting of characters equal to our final character) and we must return it to its original state again and that’s impossible without an additional move.

Consider we tried to obtain a better strategy in the first example:

That means that we would change all D letters to U in one move. It’s only possible by flipping the substring [DDUUUDDD] (or any substring formed by extending this one from left or right), but doing this would change U letters to D and we need to return them back to U, and this will cost us at least one operation.

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution: [Here] 444
TESTER’s solution: [Here] 555

5 Likes
2

useless. Even couldn’t explain simple thing

1 Like
3

#include<stdio.h>
int flip(char *a, char c)
{
int i,count=0;
for(i=0;a[i]!=’\0’;i++)
{
if(a[i]==c)
{
while(a[++i]==c);
++count;
}
}
return count;
}
int main()
{
char a[50];
int t,u,d;
scanf("%d",&t);
while(t–)
{
scanf("%s",&a);
u=flip(a,‘U’);
d=flip(a,‘D’);
printf("%d",u>d?d:u);
}
return 0;
}

Runs perfectly on my machine but not accepted by codechef. Saying wrong answer.

4

@Vijju123

My code is also seems working correct.But not accepted in code chef :frowning:
class Ada_and_crayons {
private static InputReader in = new InputReader(System.in);
public static void main(String[] args)throws Exception
{
int T= in.readInt();
StringBuilder sb = new StringBuilder();
while(T-- >0)
{
String str = in.readString();
char chr[] = str.toCharArray();
int U_count=0;
int D_count=0;
for(int i =0;i<chr.length;i++)
{
if(chr[i]==‘U’)
{
U_count++;
}
else if(chr[i]==‘D’)
{
D_count++;
}
}
char ch=’ ';
if(U_count< D_count++)
{
ch=‘U’;
}
else
{
ch=‘D’;
}
int seg=0;
int i =0;
while(i<chr.length)
{
if(chr[i]==ch)
{
seg++;
while(i<chr.length && chr[i]==ch)
{
i++;
}
}
else
{
i++;
}
}
sb.append(seg+"\n");
}
System.out.println(sb);
}
}

5

What is the problem with my code
CodeChef: Practical coding for everyone

6

my code is=
#include
using namespace std;

int main()
{int t;
cin>>t;
while(t>0)
{char s[100];
int i,p=0,c1=0,c2=0;
cin>>s;
for(i=0;i!=’\n’;i++)
{
if(s[i]==‘U’)
{
if(p==1)
{continue;}
else
{
c1++;
p=1;
}
}
else if(s[i]==‘D’)
{
if(p==2)
{continue;
}
else
{
c2++;
p=2;
}
}
}
if(c1>=c2){cout<<c2<<endl;}
else
{cout<<c1<<endl;}
t–;
}
return 0;
}

again and again it is showing wrong answer but in my machine it is working fine

7

Useless tutorials are here but important ones are not :frowning:

4 Likes
8

They will be uploaded in few hours, have some patience please.

1 Like
9

At some point of time in past, these tutorials wouldn’t have been that useless for you mate.

8 Likes
10

Well even simple problems need proofs. and proofs are usually harder than the problem. If I asked are prime numbers infinite you would tell yes because it’s clear that they are. But can you prove that easily?
Proofs are necessary for even simple problems, if this problem seems very easy for you and I am making it more complicated then you can skip them, but just saying that you need to do this without a proof is not ideal (even if the proof is complicated)
if you really think it’s useless you should say why and what can we fix? not just throw a comment.

6 Likes
11

I agree with @deadwing97 . Its easy to throw tantrums. If you really want something to fix, then suggest something. OR atleast, bring it up POLITELY. You know, never hurts being nice ^^

1 Like
12

You dont take strings with"&’ character. Try making it ("%s",a) in scanf. Also, make sure your string length is ATLEAST 1 MORE than given in cosntraints. Else ‘\0’ wont be stored in it, resulting in infinite loop/undefined behaviour.

13

for i in range(int(input())):
s=input()
seg=0
count_u=s.count(‘U’)
count_d=s.count(‘D’)

if count_d<count_u:
    s=s+'U'
else:
    s=s+'D'
for i in range(len(s)):
    if count_d<count_u:
        if s[i] =='D' and s[i+1]=='U':
            seg=seg+1
    else:
        if s[i]=='U' and s[i+1]=='D':
            seg=seg+1               
print(seg)

whats wrong with this code any one suggest

14 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int t;
	cin >> t;
	while(t--) {
		string s;
		cin >> s;
		int sU = 0;
		int sD = 0;
		for(int i = 0; i < s.size(); i++) {
			if(i == 0) {
				if(s[i] == 'U') {
					sU++;
				}
				if(s[i] == 'D') {
					sD++;
				}
			} else {
				if(s[i] == 'U' && s[i - 1] == 'D') {
					sU++;
				}
				if(s[i] == 'D' && s[i - 1] == 'U') {
					sD++;
				}
			}
		}
		cout << min(sU, sD) << endl;
	}
}

Every time a character changes from ‘U’ to ‘D’ then I add the segment of U by 1 and segment of D if ‘D’ changes to ‘U’ then I took the minimum of those.

15

What is wrong with my code ?? Anybody plz ?
#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
string str;
cin>>str;
int len = str.length();
int groupU=0,groupD=0;
for(int i=0;i<len;i++)
{
if(str[i] == ‘U’)
{
if(str[i] == str[i+1])
{
continue;
}
else if(str[i] != str[i+1])
{
groupU++;
}
}
if(str[i] == ‘D’)
{
if(str[i] == str[i+1])
{
continue;
}
else if(str[i] != str[i+1])
{
groupD++;
}
}
}
if(groupD>groupU)
{
cout<<groupU<<endl;
}
else if(groupD<groupU)
{
cout<<groupD<<endl;
}
}
return 0;
}

16

Can anyone suggest any test cases I have tried almost every test case and the answers are correct acc. to question but not accepted by code chef

Here is my code:

for _ in range(int(input())):
s = input()
u_cnt = s.count(‘U’)
d_cnt = s.count(‘D’)
s = list(s)
steps = 0
ctr = 0

if u_cnt > d_cnt:
    char = 'D'
else:
    char = 'U'
for i in s:
    if i == char and ctr == 0:
        steps += 1
        ctr = 1
    
    elif i == char:
        continue
    
    else:
        ctr = 0

print(steps)
17

The Editorial is a little complicated.

To flip the crayons in one direction, you start from the outside in. If the outside crayons are the same direction, then pick that direction. Then ignore them, and all their neighbours of the same direction, for the rest of the puzzle.

Then look at the next layer in. Because you have now ignored all the outside crayons of the ‘correct’ direction, you will have a layer on each end of the wrong direction. At a minimum, that will take two moves to remove. But the game doesn’t care whether you flip each end separately or flip both ends at the same time and everything else between them (and then flip the insides back again). So do that instead. That will make the outside crayons the ‘correct’ direction. So ignore them again.

Then look at the next layer in… and so on. Until you’re left with a single line of crayons facing the ‘wrong’ direction. One flip will put them right.

This is functionally equivalent to stripping all leading/trailing characters of the direction you’re “ignoring”. Repeatedly strip those characters and change direction until you’ve got no crayons left. The number of strips will be the answer.

(If the outside crayons aren’t the same direction at the start, then they will be once you’ve removed the leading crayons of one direction.)

Python 3.6 implementation here: CodeChef: Practical coding for everyone

18

One way to understand the correct answer is to focus on the transitions between U and D, rather than the crayons themselves. Flipping a set of crayons can eliminate the transition at the start and at the end of the flip set, but will leave any other transitions in place. So we need enough flips to remove all transitions, that is, half the transition count rounded up.

T = int(input())
for tx in range(T):
    S = input().strip()
    trans = S.count("UD") + S.count("DU")
    print((trans+1)//2)