Being Code Expert: CSES

Showing posts with label CSES. Show all posts

Finding Periods

A period of a string is a prefix that can be used to generate the whole string by repeating the prefix. The last repetition may be partial. For example, the periods of abcabca are abc, abcabc and abcabca.

Your task is to find all period lengths of a string.

Example:

Input:  s = "abcabca"
Output: 3 6 7

Approach

Java

import java.util.Arrays;
import java.util.Vector;

public class FindingPeriods {
    public static void main(String[] args) {

        String s = "abcabca";

        int[] res = findingPeriods(s);

        System.out.println(Arrays.toString(res));
    }

    static int[] findingPeriods(String s) {
        int n = s.length();
        int[] zarray = new int[n];
        int x = 0, y = 0;

        Vector<Integer> res = new Vector<>();
        for (int i = 1; i < n; i++) {
            zarray[i] = Math.max(0, Math.min(zarray[i - x],
                         y - i + 1));
            while (i + zarray[i] < n && s.charAt(zarray[i]) ==
                      s.charAt(i + zarray[i])) {
                x = i;
                y = i + zarray[i];
                zarray[i]++;
            }
            if (zarray[i] + i == n)
                res.add(i);
        }
        res.add(n);
        int[] ans = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }

        return ans;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> findingPeriods(string s)
{
    int n = s.size();
    vector<int> zarray(n, 0);
    int x = 0, y = 0;

    vector<int> res;
    for (int i = 1; i < n; i++)
    {
        zarray[i] = max(0, min(zarray[i - x], y - i + 1));
        while (i + zarray[i] < n && s[zarray[i]] == s[i +
                                       zarray[i]])
        {
            x = i;
            y = i + zarray[i];
            zarray[i]++;
        }
        if (zarray[i] + i == n)
            res.push_back(i);
    }
    res.push_back(n);

    return res;
}

int main()
{
    string s = "abcabca";

    vector<int> res = findingPeriods(s);

    for (int i = 0; i < res.size(); i++)
        cout << res[i] << " ";
    return 0;
}

Shortest Subsequence

You are given a DNA sequence consisting of characters A, C, G, and T.

Your task is to find the shortest DNA sequence that is not a subsequence of the original sequence.

Example:

Input: s = "ACGTACGT"
Output: TTA

Approach

Java

public class ShortestSubsequence {
    public static void main(String[] args) {

        String s = "ACGTACGT";

        System.out.println(shortestSubsequence(s));

    }

    static String shortestSubsequence(String s) {
        int l = 0, r = 0;
        int a = 0, b = 0, c = 0, d = 0;
        int n = s.length();
        String res = "";
        while (l < n) {
            a = 0;
            b = 0;
            c = 0;
            d = 0;
            if (s.charAt(l) == 'A')
                a += 1;
            if (s.charAt(l) == 'C')
                b += 1;
            if (s.charAt(l) == 'G')
                c += 1;
            if (s.charAt(l) == 'T')
                d += 1;

            r = l + 1;
            while (r < n && a + b + c + d != 4) {
                if (s.charAt(l) == 'A')
                    a += 1;
                if (s.charAt(l) == 'C')
                    b += 1;
                if (s.charAt(l) == 'G')
                    c += 1;
                if (s.charAt(l) == 'T')
                    d += 1;
                r++;
            }
            if (a + b + c + d == 4)
                res += s.charAt(r - 1);
            l = r;
        }
        if (a + b + c + d == 4)
            res += 'A';
        else if (a == 0)
            res += 'A';
        else if (b == 0)
            res += 'C';
        else if (c == 0)
            res += 'G';
        else if (d == 0)
            res += 'T';
        return res;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

string shortestSubsequence(string s)
{
    int l = 0, r = 0;
    bool a = 0, b = 0, c = 0, d = 0;
    int n = s.size();
    string res = "";
    while (l < n)
    {
        a = 0, b = 0, c = 0, d = 0;
        a += (s[l] == 'A');
        b += (s[l] == 'C');
        c += (s[l] == 'G');
        d += (s[l] == 'T');
        r = l + 1;
        while (r < n && a + b + c + d != 4)
        {
            a += (s[r] == 'A');
            b += (s[r] == 'C');
            c += (s[r] == 'G');
            d += (s[r] == 'T');
            r++;
        }
        if (a + b + c + d == 4)
            res += s[r - 1];
        l = r;
    }
    if (a + b + c + d == 4)
        res += 'A';
    else if (!a)
        res += 'A';
    else if (!b)
        res += 'C';
    else if (!c)
        res += 'G';
    else if (!d)
        res += 'T';
    return res;
}
int main()
{

    string s = "ACGTACGT";

    cout << shortestSubsequence(s) << "\n";

    return 0;
}

String Matching

Given a string and a pattern, your task is to count the number of positions where the pattern occurs in the string.

Example:

Input: text = "saippuakauppias", str = "pp"
Output: 2

Approach

Java

public class StringMatching {
    public static void main(String[] args) {
        String text = "saippuakauppias", str = "pp";

        System.out.println(stringMatching(text, str));

    }

    static int[] prefixArray(String s) {
        int n = s.length();
        int[] prefix = new int[n];
        for (int i = 1; i < n; i++) {
            int j = prefix[i - 1];
            while (j > 0 && s.charAt(i) != s.charAt(j))
                j = prefix[j - 1];
            if (s.charAt(i) == s.charAt(j))
                j++;
            prefix[i] = j;
        }
        return prefix;
    }

    static int stringMatching(String text, String str) {

        text = str + "#" + text;
        int[] v = prefixArray(text);
        int cnt = 0;
        for (int i = 0; i < v.length; i++) {
            if (v[i] == str.length())
                cnt++;
        }
        return cnt;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> prefixArray(string s)
{
    int n = s.length();
    vector<int> prefix(n);
    for (int i = 1; i < n; i++)
    {
        int j = prefix[i - 1];
        while (j > 0 && s[i] != s[j])
            j = prefix[j - 1];
        if (s[i] == s[j])
            j++;
        prefix[i] = j;
    }
    return prefix;
}
int stringMatching(string text, string str)
{

    text = str + "#" + text;
    vector<int> v = prefixArray(text);
    int cnt = 0;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] == str.size())
            cnt++;
    }
    return cnt;
}
int main()
{
    string text = "saippuakauppias", str = "pp";

    cout << stringMatching(text, str) << "\n";

    return 0;
}

Flight Discount

Your task is to find a minimum-price flight route from Syrjala to Metsala. You have one discount coupon, using which you can halve the price of any single flight during the route. However, you can only use the coupon once.

Example:

Input:  n = 3, m = 4, edges = {{1, 2, 3}, {2, 3, 1}, {1, 3, 7}, {2, 1, 5}}
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const long long inf = 10000000000000000LL;

const long long N = 100005;
long long vis[N];
long long dis1[N], dis2[100005];

void dijkistrasAlgorithm(long long s, long long dis[],
                         vector<pair<long long, long long>> adj[])
{
    priority_queue<pair<long long, long long>> q;

    //initialize with very big number
    for (int i = 1; i < N; i++)
        dis[i] = inf;
    dis[s] = 0;
    q.push({0, s});

    //mark visited array as not visited
    memset(vis, 0, sizeof(vis));

    //iterate till the end of queue
    while (!q.empty())
    {

        long long a = q.top().second;

        //remove from the queue
        q.pop();

        //if already visited
        if (vis[a])
            continue;

        //mark as visited
        vis[a] = 1;
        for (auto edge : adj[a])
        {
            long long b = edge.first;
            long long w = edge.second;

            //relaxation
            if (dis[a] + w < dis[b])
            {
                dis[b] = dis[a] + w;
                q.push({-dis[b], b});
            }
        }
    }
}

long long flightDiscount(int n, int m,
                         vector<vector<long long>> &edges)
{

    vector<pair<long long, long long>> adj1[n + 1];
    vector<pair<long long, long long>> adj2[n + 1];

    for (long long i = 0; i < m; i++)
    {
        long long a = edges[i][0];
        long long b = edges[i][1];
        long long w = edges[i][2];

        adj1[a].push_back({b, w});
        adj2[b].push_back({a, w});
    }
    dijkistrasAlgorithm(1, dis1, adj1);
    dijkistrasAlgorithm(n, dis2, adj2);
    long long mn = inf;
    for (auto edge : edges)
    {
        long long a = edge[0];
        long long b = edge[1];
        long long w = edge[2];
        mn = min(mn, dis1[a] + dis2[b] + w / 2);
    }
    return mn;
}
int main()
{

    long long n = 3, m = 4;

    vector<vector<long long>> edges = {{1, 2, 3},
                                       {2, 3, 1},
                                       {1, 3, 7},
                                       {2, 1, 5}};

    cout << flightDiscount(n, m, edges) << "\n";

    return 0;
}

High Score

You play a game consisting of n rooms and m tunnels. Your initial score is 0, and each tunnel increases your score by x where x may be both positive or negative. You may go through a tunnel several times.

Your task is to walk from room 1 to room n. What is the maximum score you can get?

Example:

Input:  n = 4, m = 5, edges = {{1, 2, 3}, {2, 4, -1}, {1, 3, -2}, {3, 4, 7}, {1, 4, 4}}
Output: 5

Approach

C++

#include <bits/stdc++.h>
using namespace std;

long long dis[2505];
const long long M = 1e16;
vector<long long> adj[2505], adj2[2505];
bool vis[2505], vis2[2505];
void dfs(long long s)
{

    //if already visited
    if (vis[s])
        return;

    //mark as visted
    vis[s] = 1;

    //call for all the adjacency list
    //of current node
    for (auto i : adj[s])
        dfs(i);
}
void dfs2(long long s)
{

    //if already visted
    if (vis2[s])
        return;

    //mark as visted
    vis2[s] = 1;

    //call for all the adjacency list of the current
    //node
    for (auto i : adj2[s])
        dfs2(i);
}
long long highScore(long long n, long long m, vector<vector<long long>> &edges)
{

    for (long long i = 1; i <= n; i++)
        dis[i] = M;
    dis[1] = 0;
    for (long long i = 0; i < m; i++)
    {
        long long a = edges[i][0];
        long long b = edges[i][1];

        adj[a].push_back(b);
        adj2[b].push_back(a);
    }
    dfs(1);
    dfs2(n);
    for (long long i = 0; i < n; i++)
    {

        for (auto edge : edges)
        {
            long long a = edge[0];
            long long b = edge[1];
            long long w = -edge[2];
            if (dis[b] > dis[a] + w)
            {
                dis[b] = dis[a] + w;
                if (i == n - 1 && vis[b] && vis2[b])
                {
                    return -1;
                }
            }
        }
    }
    return -dis[n];
}
int main()
{
    long long n = 4, m = 5;

    vector<vector<long long>> edges = {{1, 2, 3},
                                       {2, 4, -1},
                                       {1, 3, -2},
                                       {3, 4, 7},
                                       {1, 4, 4}};

    cout << highScore(n, m, edges) << "\n";

    return 0;
}

Home

Finding Periods

Shortest Subsequence

String Matching

Flight Discount

High Score