loading...

Daily Coding Challenge #93

wingkwong profile image Wing-Kam ・2 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
Codeforces Round #658 (Div. 2) - C2 - Prefix Flip (Hard Version)
https://codeforces.com/contest/1382/problem/D
*/

#include <bits/stdc++.h>
using namespace std; 
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)

int main()  
{ 
    FAST_INP;
    int n,t;
        string s1,s2;
    cin >> t;
    while(t--){
        // make s1 to all zeros
        // make all zeros to s2
        cin >> n >> s1 >> s2;
        s1+='0', s2+='0';
        vector<int> v1, v2;
        for(int i=1;i<=n;i++){
            if(s1[i]!=s1[i-1]) v1.emplace_back(i);
            if(s2[i]!=s2[i-1]) v2.emplace_back(i);
        }
        v1.insert(v1.end(), v2.rbegin(), v2.rend());
        cout << v1.size() << " ";
        for(int k:v1) cout << k << " ";
        cout << endl;
    }
    return 0;
} 

/*
Palindrome Reorder
https://cses.fi/problemset/task/1755/

Given a string, your task is to reorder its letters in such a way that it becomes a palindrome (i.e., it reads the same forwards and backwards).

Input

The only input line has a string of length n consisting of characters A–Z.

Output

Print a palindrome consisting of the characters of the original string. You may print any valid solution. If there are no solutions, print "NO SOLUTION".

Constraints
1≀n≀106
Example

Input:
AAAACACBA

Output:
AACABACAA
*/

#include <bits/stdc++.h>
using namespace std; 
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)
typedef long long ll; 
const ll MOD = 1000000007;

int main()  
{ 
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r", stdin);
    // freopen("output.txt","w", stdout);
    // #endif
    FAST_INP;
    string s;
    cin >> s;
    int cnt[26]={}, odd=0;
    for(char c:s) cnt[c-'A']++;
    for(int i=0;i<26;i++) {
        if(cnt[i]&1) odd++;
    }
    if(odd>1){
        cout << "NO SOLUTION" << endl;
        return 0;
    } 

    // Example: 
    // AAAACACBA
    // AAAC(first) B(middle) CAAA(last)

    string first="", middle="", last="";
    for(int i=0;i<26;i++){
        if((cnt[i]&1)^1){
            for(int j=0;j<cnt[i]/2;j++){
                first+=(char)('A'+i);
            }
        }
    }
    for(int i=0;i<26;i++){
        if(cnt[i]&1){
            for(int j=0;j<cnt[i];j++){
                middle+=(char)('A'+i);
            }
        }
    }
    last=first;
    reverse(last.begin(),last.end());
    cout << first+middle+last << endl;
    return 0;
} 

There are other programming solutions in the following repositories below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

πŸ† A Collection of my LeetCode Solutions with Explanations πŸ†

GitHub logo wingkwong / hackerrank

πŸ† A Collection of my HackerRank Solutions with Explanations πŸ†

GitHub logo wingkwong / codeforces

πŸ† A Collection of my Codeforces Solutions with Explanations πŸ†

GitHub logo wingkwong / atcoder

πŸ† A Collection of my AtCoder Solutions with Explanations πŸ†

GitHub logo wingkwong / cses

πŸ† A Collection of my CSES Solutions with Explanations πŸ†

GitHub logo wingkwong / timus

A Collection of my Timus Solutions

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

pic
Editor guide