DEV Community: Miradil

Solving DSA Problems. Eolymp 6254: Timebomb

Miradil — Mon, 18 Mar 2024 10:05:51 +0000

Problem statement

You and your teammates from the anti-bomb squad of the local police have been called to defuse a bomb found in the only pub in town. Fearing the tragic consequences this might produce, you go to the scene as quickly as possible. After some research, you learn that the bad guys have created a tricky way to allow them to defuse the bomb at will. You find a remote control with a button that you can take to a safe place. You also find that it is possible to connect to the bomb through a wireless connection and retrieve an ASCII representation of a code every 2 seconds. The bomb then gets defused if the button is pressed when the code is a number divisible by 6. But you have to be careful. If you press the button when the ASCII representation of the code is not a number divisible by 6 or has an invalid representation for any digit, the bomb will explode instead.

You have to rely on your programming skills to write a program able to tell you if it is safe to press the button, before it blows out the pub (and the beer).

Input data

Consists of an ASCII representation of a code. This code has between 2 and 8 digits. Each digit is represented by 5 rows and 3 columns of characters, which can be either a space or a star character '*'. No other type of character (except for the new line character) will ever appear in the input. There is also one column of spaces (and only spaces) to separate each digit. After the last digit you will find a column of new line characters. Note that although every digit will always be of size 5 × 3, there is no guarantee it will represent a valid digit between 0 and 9 inclusive. The valid 5 × 3 representations for each digit are given below.

The hash '#' characters on the top are there only to mark the 3 columns used for a digit and are not part of the digits' representation.

The code can have leading zeros, hence an ASCII representation of, for example, 00000076 represents the number 76. You may also safely assume that every valid code will correspond to a strictly positive number.

Output data

Print one line with "BEER!!" if it is safe to press the button and defuse the bomb, and "BOOM!!" otherwise.

Examples

Input example #1

***   * * * *** *** *** ***
* *   * * *   *   *   * *  
* *   * *** *** *** *** ***
* *   *   * *     * *   * *
***   *   * *** *** *** ***

Output example #1

BEER!!

Input example #2

  *   * *** *** *** * *
  *   * **    * * * * *
  *   * *** *** *** ***
  *   * *   *   * *   *
  *   * *** *** ***   *

Output example #2

BOOM!!

Input example #3

*** ***
* * *  
*** * *
* * * *
*** ***

Output example #3

BOOM!!

Solution

This is not a hard problem, however, it needs careful data handling. First, we need to identify "numbers": we will have a constant array with predefined numbers and their "star form". After that, we need to process the input. We know that we have five lines of input and each digit is taking three columns. The bundle of three characters in a line defines a digit, so, we also need to know the number of digits or handle it without knowing it. We know that we can have a maximum of 8 digits, so the array length will be that. After that, we process 3+1 characters at a time, the fourth character being whitespace: either space or newline character (for the last digit). If it is space, we move to the next digit, else, if it is newline, we store the next row for each digit:

#include <stdio.h>
#include <string.h>

const char digits[10][16] = {
    {"**** ** ** ****"}, // 0
    {"  *  *  *  *  *"}, // 1
    {"***  *****  ***"}, // 2
    {"***  ****  ****"}, // 3
    {"* ** ****  *  *"}, // 4
    {"****  ***  ****"}, // 5
    {"****  **** ****"}, // 6
    {"***  *  *  *  *"}, // 7
    {"**** ***** ****"}, // 8
    {"**** ****  ****"}, // 9
};

int main(void)
{
    char bombtime[8][16];
    int digitp;  // digit poimnt
    char ws; // whitespace
    char in[4];

    for (int i = 0; i < 5; ++i)  // we need to know at which line we are to store at the right address
    {
        digitp = 0; // at each line, we start storing to 0th index

        while(scanf("%3[* ]%c", in, &ws))  // NOTE 1
        {
            // NOTE 2
            memcpy(bombtime[digitp] + (i * 3), in, 3); // store the next three chars in `bombtime`

            if (ws == '\n')
                break;

            ++digitp;
        }
    }

    //digitp is also the number of digits at this point

    int res = 0, j;

    for (int i = 0; i <= digitp; ++i)
    {
        j = 0;
        for (; j < 10; ++j)
            if (!strcmp(bombtime[i], digits[j]))
            {
                res = res * 10 + j;  // j is digit, shift res to left (* 10), and add j
                break;
            }

        // NOTE 3
        if (j == 10) // No such digit found, gibberish
        {
            res = -1;
            break;
        }
    }

    printf("%s\n", (res % 6) ? "BOOM!!" : "BEER!!");

    return 0;
}

Some notes about the code:

NOTE 1 (scanf): %3[* ] means scanning 3 chars that are either * or space.
NOTE 2 (memcpy): each time we store 3 digits/chars in the needed address, which is [digitp][linenum * 3].
NOTE 3 (j == 10): the task says: there is NO GUARANTEE it will represent a valid digit between 0 and 9 inclusive.

So, if we submit this code:

A+! Yay! You can access the code here. Feel free to contribute your solution in a different language!

Solving DSA Problems. HackerRank: Winning Lottery Ticket

Miradil — Mon, 11 Mar 2024 09:09:01 +0000

Problem statement

The SuperBowl Lottery is about to commence, and there are several lottery tickets being sold, and each ticket is identified with a ticket ID. In one of the many winning scenarios in the Superbowl lottery, a winning pair of tickets is:

Concatenation of the two ticket IDs in the pair, in any order, contains each digit from 0 to 9 at least once.

For example, if there are 2 distinct tickets with ticket ID 129300455 and 56789, (129300455, 56789) is a winning pair.

NOTE: The ticket IDs can be concatenated in any order. Digits in the ticket ID can occur in any order.

Your task is to find the number of winning pairs of distinct tickets, such that concatenation of their ticket IDs (in any order) makes for a winning scenario. Complete the function winningLotteryTicket which takes a string array of ticket IDs as input, and return the number of winning pairs.

Input Format

The first line contains n denoting the total number of lottery tickets in the super bowl.
Each of the next n lines contains a string, where string on a $i^{th}$ line denotes the ticket id of the $i^{th}$ ticket.

Constraints

$\leq n \leq 10^6$
$\leq$ length of ticket_i $≤106\leq 10^6$
sum of lengths of all ticket_i $≤106\leq 10^6$
Each ticket_id consists of digits from $[0,9]\lbrack 0, 9\rbrack$

Output Format

Print the number of pairs in a new line.

Sample Input 0

5
129300455
5559948277
012334556
56789
123456879

Sample Output 0

5

Explanation 0

Pairs of distinct tickets that make for a winning scenario are:

Notice that each winning pair has digits from 0 to 9 at least once, and the digits in the ticket ID can be of any order. Thus, the number of winning pairs is 5.

Solution

This question is a little bit tricky. Of course, we could loop through a couple of tickets and check their "compatibility". However, we need an extra loop (on top of a double loop for pairs of tickets) to check the digits of each ticket pair string. However, we could loop through the list of tickets before and remember their digits, and then compare the pairs. But, how do we store this information, such that we don't need an extra loop for checking compatibility? If we used set (C++), it would be extra O(logn) complexity. Bit manipulation is here to save the day!

The solution is easy to implement, however hard to come up with. Before comparing pairs, we will loop through the tickets and store digits in bits of a number as in bitmask. If a ticket has zero, its bitmask will have 1 in bit 0. Similar will be to other digits, and if all bits are set, then the bitmask will be 0b1111111111, which is equal to 1023 in decimal form. So, if we "merge" to tickets and all bits are set, it is a winning ticket as, all digits are present (remember, order does not matter).

#define ALL_BITS_SET 1023

long winningLotteryTicket(int tickets_count, char** tickets) {
    int *bitmasks = calloc(tickets_count, sizeof(int));
    int len;
    int cnt = 0;

    for (int i = 0; i < tickets_count; ++i)
        for (int j = 0, len = strlen(tickets[i]); j < len; ++j)
            bitmasks[i] |= 1 << (tickets[i][j] - '0'); // set n-th bit to 1

    for (int i = 0; i < tickets_count; ++i)
        for (int j = i + 1; j < tickets_count; ++j)
            if ((bitmasks[i] | bitmasks[j]) == ALL_BITS_SET)
                ++cnt;

    return cnt;
}

Now, if we submit:

Hmm, even though test cases 0-8 were correct, test cases 9-16 timeouted. This means, our solution is correct, but, it should be optimized. So, how can we? First, we can ignore the tickets that contain all digits, as their combination with any ticket is the winning one. Moreover, tickets like 10001 and 0000001 are basically the same, as they contain two same digits. So, we can store them in one storage, and multiply the result by count, thus going over one ticket of each bitmask. So, let's create an array of bitmasks that store the count of such tickets:

#define BITMASK_MAX 1024
#define ALL_BITS_SET ((BITMASK_MAX) - 1)

long winningLotteryTicket(int tickets_count, char** tickets) {
    int *bitmask_cnt = calloc(BITMASK_MAX, sizeof(int));
    int len;
    int bitmask;
    long cnt = 0;

    for (int i = 0; i < tickets_count; ++i)
    {
        bitmask = 0;

        for (int j = 0, len = strlen(tickets[i]); j < len; ++j)
            bitmask |= 1 << (tickets[i][j] - '0'); // set n-th bit to 1

        ++bitmask_cnt[bitmask]; // group same bitmask tickets
    }

    // ignore bitmask[1023], as tickets with those bitmasks is compatible with any ticket
    for (int i = 0; i < BITMASK_MAX - 1; ++i)
        for (int j = i + 1; j < BITMASK_MAX - 1; ++j)
            if ((i | j) == ALL_BITS_SET)
                cnt += (long)bitmask_cnt[i] * bitmask_cnt[j];  // all combinations of these groups

    /* 
    * each bitmask_cnt[ALL_BITS_SET] is compatible with all of the rest of the tickets
    * and as we need to ignore duplicate tuples:
    * The first "all-digits-included" ticket will have (tickets_cnt - 1) combinations
    * second will have (tickets_cnt - 2) combinations
    * third will have (tickets_cnt - 3) combinations and so on.
    * so, we have arithmetic progression from [tickets_cnt - bitmask_cnt[ALL_BITS_SET], ticket_cnt - 1]
    * sum = n * (a1 + an) / 2 =>  
    * bitmask_cnt[ALL_BITS_SET] * (tickets_cnt - bitmask_cnt[ALL_BITS_SET] + (tickets_cnt - 1)) / 2
    * so, total = bitmask_cnt[ALL_BITS_SET] * (2 * tickets_count - bitmask_cnt[ALL_BITS_SET] - 1)) / 2
    */
    return cnt + (((long)bitmask_cnt[ALL_BITS_SET] * (2 * tickets_count - bitmask_cnt[ALL_BITS_SET] - 1)) / 2);
}

To sum up:

Our bitmask_cnt array indexes are bitmask values of tickets, and values are their count, thus grouping the same bitmask tickets
We iterate through bitmasks (contrary to tickets). If joining two bitmasks results in an all-digits-included ticket, we add the count of all possible combinations of such tickets
We exclude tickets which has all digits from the start of that search. After the loop, we use the arithmetic series formula to find all non-duplicate combinations of full-digit tickets with the rest.

NOTE:
You can see that we cast array elements to long. This is because multiplying int with int results in int, and if there is an overflow in multiplication we will lose data.
If we cast one of the operators to long the result will be long and no data will be truncated.
We could have used long *bitmask_cnt, however, the bigger space would be allocated for that array, which we don't need. Thus, casting during operation is sufficient.

If we submit:

Perfect, it works! Yay! You can find solutions here. Feel free to contribute your solution in a different language!

Solving DSA Problems. LeetCode 142: Linked List Cycle II

Miradil — Mon, 04 Mar 2024 10:16:51 +0000

NOTE: The problem 141: "Linked List Cycle" is a subproblem of this problem, so the solution can be slightly modified to solve that too.

Problem statement

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Example 1

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Constraints

The number of the nodes in the list is in the range $0, 10^4]$ .
$−105≤Node.val≤105-10^5 \leq Node.val \leq 10^5$
pos is -1 or a valid index in the linked-list.

Follow Up

Can you solve it using O(1) (i.e. constant) memory?

Default Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {}

Solution

This is one of the most popular problems in data structures. Although it can be solved in various ways, such as collecting visited nodes in the list and ensuring every time you visit a new node, O(n) space and at least O(nlogn) time complexity would be required. There is a simple algorithm that allows us to solve this problem with O(1) memory space and O(n) time complexity:

Floyd's Cycle Finding Algorithm or Hare-Tortoise Algorithm

This algorithm uses two pointers, where one of the pointers moves twice as fast (hare) than the other one (tortoise). If there is a loop, it is ensured that the fast pointer will loop and catch the slow pointer. So, if pointers meet at the same node, we can conclude that a loop exists:

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast = head, *slow = head;

    while (fast != NULL && fast->next != NULL) // check next steps of `fast` pointer
    {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow)
        {
            // loop found
        }
    }

    return NULL; // no loop found
}

Note: We have solved "Leetcode 141: Linked List Cycle" by this point.

Now, we need to find the beginning node of the loop. This part is a little bit trickier. There are two ways of explaining this part: math (which we will do) and visual.

Visual Explanation

There is an astonishingly detailed visual explanation by Oleksandr Klymenko at Medium. However, we will explore the math explanation.

Math Explanation

So, let's visualize a cycled linked list like this:

Where A is the head of the linked list, B is the cycle start node, and C is where pointers (fast and slow) meet. We know that:

slow moved x + y reaching point C.
fast moved x + y + z + y reaching point C.

We also know that fast moves twice as much as slow. So, fast has traveled twice the length of slow. So, we can conclude that:

2 (x + y) = x + 2 y + z

2 x + 2 y = x + 2 y + z

2 x = x + z

x = z

Turns out, from the point that pointers met till the starting cycle node is the same distance as that of from the head. So, if we put one of the pointers to the head and move at the SAME speed, the pointers will meet exactly at the cycle start node. The slow pointer will travel from A to B by x, and the fast one will travel from C to B by z. So, the overall code will be:

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast = head, *slow = head;

    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow)
        {
            slow = head;
            while (fast != slow)
            {
                fast = fast->next;
                slow = slow->next;
            }

            return slow; // they will meet at the cycle node
        }
    }

    return NULL; // no loop found
}

If we submit this:

Accepted with high runtime efficiency! You can access the code here. Feel free to contribute your solution in a different language!

Solving DSA Problems. CodeForces 1918-A: Brick Wall

Miradil — Mon, 26 Feb 2024 10:14:02 +0000

Problem statement

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

A brick is a strip of size 1 × k, placed horizontally or vertically, where k can be an arbitrary number that is at least 2 (k ≥ 2).

A brick wall of size n × m is such a way to place several bricks inside a rectangle n × m, that all bricks lie either horizontally or vertically in the cells, do not cross the border of the rectangle, and that each cell of the n × m rectangle belongs to exactly one brick. Here n is the height of the rectangle n × m and m is the width. Note that there can be bricks with different values of k in the same brick wall.

The wall stability is the difference between the number of horizontal bricks and the number of vertical bricks. Note that if you used 0 horizontal bricks and 2 vertical ones, then the stability will be −2, not 2.

What is the maximal possible stability of a wall of size n × m?

It is guaranteed that under restrictions in the statement at least one n × m wall exists.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10000), the number of test cases.

The only line of each test case contains two integers n and m (2 ≤ n, m ≤ 10^4).

Output

For each test case, print one integer, the maximum stability of a wall of size n × m.

Example

input

5
2 2
7 8
16 9
3 5
10000 10000

output

2
28
64
6
50000000

Solution

Note: in notation a × b, a is height, b is width.

Even though it seems as a hard problem where you need to calculate different combination of brick lengths and their layout, it is quite easy problem. I chose this problem in order to demonstrate how some problems can be solved easily, without complicating things. When one does many hard problems, they are used to think complicated. So when an easy problem comes, they go into task with that complicated focused mindset and miss simple things (happened to me a lot in chess).

So, what we know:

We need to minimize vertical bricks and maximize the horizontal ones
Then, we need to use smallest bricks, to maximize the benefit: 2x1
We need to avoid using vertical bricks at all

So, if we use 1 × 2 bricks horizontally, we would have m / 2 bricks in one layer, and that being n layers. Easy right? However, what if m is odd? then we would have column left. We can fill it with vertical bricks, however, each vertical brick is decreases stability. So, how do we fill that gap? Easy, we just make the last brick of the row 1 × 3 instead of 1 × 2. In a result, all bricks are placed horizontal, and their count being floor(m / 2) × n:

#include <stdio.h>

int main()
{
    int n, m, t;

    scanf("%d", &t);

    while(t--)
    {
        scanf("%d %d", &n, &m);
        printf("%d\n", m / 2 * n);
    }

    return 0;
}

NOTE: The statement m / 2 should happen first, as we need floor down the division (we do it by using just integer division, no need for extra functions). Otherwise, you would get wrong result.

Accepted! You can access the code here. Feel free to contribute your solution in different language!

Solving DSA Problems. HackerRank: Balanced Brackets

Miradil — Sun, 18 Feb 2024 11:58:39 +0000

Problem statement

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].

Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

By this logic, we say a sequence of brackets is balanced if the following conditions are met:

It contains no unmatched brackets.
The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

Given n strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, return YES. Otherwise, return NO.

Function Description

Complete the function isBalanced in the editor below.
isBalanced has the following parameter(s):

string s: a string of brackets

Returns

string: either YES or NO

Input Format

The first line contains a single integer n, the number of strings.
Each of the next n lines contains a single string s, a sequence of brackets.

Constraints

1 ≤ n ≤ 10³
1 ≤ |s| ≤ 10³
All chracters in the sequences ∈ { {, }, (, ), [, ] }.

Output Format

For each string, return YES or NO.

Sample Input

STDIN           Function
-----           --------
3               n = 3
{[()]}          first s = '{[()]}'
{[(])}          second s = '{[(])}'
{{[[(())]]}}    third s ='{{[[(())]]}}'

Sample Output

YES
NO
YES

Explanation

The string {[()]} meets both criteria for being a balanced string.
The string {[(])} is not balanced because the brackets enclosed by the matched pair { and } are not balanced: [(]).
The string {{[[(())]]}} meets both criteria for being a balanced string.

Solution

This is a quite popular problem in data structures. Considering the closing bracket should match the last opened bracket, we always need to know the last added opening bracket. Thus, we can use stack! However, C does not provide one, unlike C++. Instead, we can simulate it with an array and pointer (or index) at the top of the stack. Notice: the stack pointer points to the top element, not the next "empty" slot, thus, we start at -1, as there are no items in the stack initially.

char* isBalanced(char* s) {

    char *stack = calloc(strlen(s), sizeof(char));
    int top = -1; // index of the top of the "stack"

    ...
}

So, we just need to store opening brackets, and pop them (or move the stack pointer) when the relative closing bracket comes as the next symbol:

char* isBalanced(char* s) {
    char *stack = calloc(strlen(s), sizeof(char));
    int top = -1; // index of the top of the "stack"

    while(*s)
    {
        if (*s == '(' || *s == '{' || *s == '[')  // opening bracket, just add to stack
            stack[++top] = *s++;  // move stack pointer and get next string character
    }
    ...
}

Now, we just need to pop items from the stack if a matching closing bracket is spotted. Also, we need to consider if a closing bracket comes when the stack is empty:

char* isBalanced(char* s) {

    char *stack = calloc(strlen(s), sizeof(char));
    int top = -1; // index of the top of the "stack"

    while(*s)
    {
        if (*s == '(' || *s == '{' || *s == '[')  // opening bracket, just add to stack
            stack[++top] = *s++;  // move stack pointer and get next string character
        else // it is a closing bracket
            if (top != -1 && ((*s == ')' && stack[top] == '(') ||
                              (*s == '}' && stack[top] == '{') ||
                              (*s == ']' && stack[top] == '[')))
                --top, ++s;  // "pop" element
            else
                break;
    }
    ...
}

Instead of having that many "and"s and "or"s, we can use a little "magic". If we look at ascii table (numbers are in decimal):

( is 40, ) is 41
[ is 91, ] is 93
{ is 123, } is 125

The difference between these closing brackets is either 1 or 2! So, we can do simple if:

char* isBalanced(char* s) {

    char *stack = calloc(strlen(s), sizeof(char));
    int top = -1; // index of the top of the "stack"

    while(*s)
    {
        if (*s == '(' || *s == '{' || *s == '[')  // opening bracket, just add to stack
            stack[++top] = *s++;  // move stack pointer and get next string character
        else // it is a closing bracket
            if (top != -1 && ((*s - stack[top]) == 1 || (*s - stack[top] == 2)))  // distance between opening/closing brackets are 1,2,2
                --top, ++s;
            else
                break;
    }
    ...
}

If the difference is not 1 or 2, we simply abort the loop. At the end, we just want to make sure that our stack is empty and that we processed all characters in s (and of course, we must free calloc-ed stack variable). So, the full code:

char* isBalanced(char* s) {

    char *stack = calloc(strlen(s), sizeof(char));
    int top = -1; // index of the top of the "stack"

    while(*s)
    {
        if (*s == '(' || *s == '{' || *s == '[')  // opening bracket, just add to stack
            stack[++top] = *s++;  // move stack pointer and get next string character
        else // it is closing bracket
            if (top != -1 && ((*s - stack[top]) == 1 || (*s - stack[top] == 2)))  // distance between opening/closing brackets are 1,2,2
                --top, ++s;
            else
                break;
    }

    free(stack);

    // return yes, if stack is empty, i.e. all opening brackets are closed
    // and iterated through whole string without interruption
    return (*s == 0 && top == -1) ? "YES" : "NO";
}

If we submit:

If we do this in C++, the logic would be exactly the same, but by using the stack data structure, provided by C++:

string isBalanced(string s) {
    stack<char> st;
    int i = 0;

    for (; i < s.length(); ++i)
    {
        if (s.at(i) == '(' || s.at(i) == '{' || s.at(i) == '[')  // opening bracket, just add to stack
            st.push(s.at(i));  // add bracket to stack
        else // it is closing bracket
            if (!st.empty() && (abs(s.at(i) - st.top()) <= 2))  // distance between opening/closing brackets are 1,2,2
                st.pop();  // remove opened bracket from stack
            else
                break;
    }

    // return yes, if the stack is empty, i.e. all opening brackets are closed
    // and iterated through whole string without interruption
    return (i >= s.length() && st.empty()) ? "YES" : "NO";
}

Perfect, it works! Yay! You can find solutions here. Feel free to contribute your solution in a different language!

Solving DSA Problems. LeetCode 58: Length of Last Word

Miradil — Sun, 11 Feb 2024 13:32:19 +0000

Problem statement

Given a string s consisting of words and spaces, return the length of the **last* word in the string*.

A word is a maximal substring consisting of non-space characters only.

Example 1

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Example 2

Input: s = " fly me to the moon "
Output: 4
Explanation: The last word is "moon" with length 4.

Example 3

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

Constraints

1 <= s.length <= $10^4$
s consists of only English letters and spaces ' '.
There will be at least one word in s.

Default Code

int lengthOfLastWord(char* s) {}

Solution

One would think that this is an easy task, where you get the whole string, parse it, and get the length of the last word. It is correct, however, considering we are solving in C, there is a better way to do it. However, we are going to do both approaches. Even though it does not really matter in this case, considering input is read and parsed before passing it to the given function, we will explore both options.

Approach 1: Parse string with `strtok`

So, that's what comes to the mind first: parse by space, and get the last word and its length! So, let's do that. Remember that, the parsing function in C is strtok:

int lengthOfLastWord(char* s)
{
    char* token = strtok(s, " ");
    char *last_word = NULL;

    while (token != NULL)
    {
        last_word = token;
        token = strtok(NULL, " ");
    }

    return strlen(last_word);
}

If we submit this:

Okay, submission is accepted, but stats can be better. Let's try another approach.

Approach 2: Parse string with `sscanf`

With sscanf one would ask? You see, scanf and relative functions get string values quite different by nature: it scans the string to the value TILL WHITESPACE. So, we can use it to get words by whole.

int lengthOfLastWord(char* s)
{
    char word[10001];
    int len = 0;

    while(sscanf(s, "%s%n", word, &len) > 0)
        s += len;

    return strlen(word);
}

So, what did we do:

Used %n to get the number of scanned characters
Move the pointer to the next word after each scan.
Continue till the EOF, and return the length of the last scanned string.

Simple, as that! So, if LeetCode allowed us, we could have done this without even storing the string, parsing right from stdin. This would have increased both the memory and runtime of the program. If we submit this solution:

We got the best time in runtime! That's perfect, however, we still kind of use a lot of memory (mostly because of word[10000]). So, what if we drop all tools and try a hardcore loop search?

Approach 3: Loop search

Of course, we can do everything the old-fashioned way:

int lengthOfLastWord(char* s)
{
    int count = 0;
    int i = strlen(s) - 1;

    // we can check this without checking `i`
    // because there is always at least one word
    while (s[i] == ' ')
        --i;

    while (i >= 0 && s[i] != ' ')
        ++count, --i;

    return count;
}

And if we submit:

Accepted with the best time, and better memory usage! Yay!

You can access the code here. Feel free to contribute your solution in a different language!

How to detect field changes in Django

Miradil — Wed, 10 Jan 2024 16:58:09 +0000

The Problem

While working on Django project, we have every now and then needed to know if a specific field of model has changed or not, and act accordingly. Let's say, you are developing a logistics website, and want to store status changes of packages whenever there is one. So, you would have model structure similar to something like this:

from django.contrib.auth import get_user_model
from django.db import models

UserModel = get_user_model()

class Status(models.Model):
    name = models.CharField(max_length=32, unique=True)


class Package(models.Model):
    user = models.ForeignKey(UserModel, on_delete=models.CASCADE)
    shipment_cost = models.DecimalField(max_digits=6, decimal_places=2)
    weight = models.DecimalField(max_digits=5, decimal_places=2)
    status = models.ForeignKey(Status, on_delete=models.CASCADE)


class PackageStatusHistory(models.Model):
    package = models.ForeignKey(Package, on_delete=models.CASCADE)
    from_status = models.ForeignKey(Status, on_delete=models.CASCADE, related_name='from_status', null=True)
    to_status = models.ForeignKey(Status, on_delete=models.CASCADE, related_name='to_status')
    created_at = models.DateTimeField(auto_now_add=True)

Then, one would add post_save signals, and register the status change:

@receiver(post_save, sender=Package)
def register_status_change(sender, instance: Package, **kwargs):
    old_status_id = ...
    if instance.status_id != old_status_id:
        # There is a status change
        PackageStatusHistory.objects.create(package_id=instance.id,
                                            from_status_id=old_status_id,
                                            to_status_id=instance.status_id)

The problem is, we do not know the old status id! If somewhere in the code we do package.status = new_status, the status field of that class/model has changed, and old value is lost. There are some ways to tackle this problem, and we will analyze some of them.

Note:
We manually added 5 statuses: Created, InPreparation, Shipped, Received, Delivered.
We also added one package with id=1 for testing.

Solution 1: The easy way?

Any person who has used post_save signal a lot knows that signal sends the updated field as an argument. That is, **kwargs contains update_fields which is a frozenset. That would help us right?

Not really. There are several drawbacks of this method:

If you change the value of field to its current value (that is, the value stays the same, no change), if would be reflected in update_fields, which is not suitable for us.
This frozenset is not automatically generated by Django. It contains only the fields that you explicitly passed in save() method. This makes it hard for us to develop and maintain the code. I am not going to test this; however, you are free to do so.

Solution 2: Query the old value

We know that Django models contain the old values that we manually changed, until refresh_from_db() is called. We can use this to our advantage: what if we get the old status from database, and check it with "dirty" Django model?

@receiver(post_save, sender=Package)
def register_status_change(sender, instance: Package, **kwargs):
    old_status_id = Package.objects.get(id=instance.id).status_id
    if instance.status_id != old_status_id:
        # There is a status change
        PackageStatusHistory.objects.create(package_id=instance.id,
                                            from_status_id=old_status_id,
                                            to_status_id=instance.status_id)

If we check:

>>> from cache_fields.models import *
>>> package = Package.objects.get()
>>> package
<Package: 1: Created>
>>> package.status_id
1
>>> package.status_id = 2
>>> package.status
<Status: InPreparation>
>>>
>>> PackageStatusHistory.objects.filter(package_id=package.id)
<QuerySet []>
>>> package.save()
>>> package.status
<Status: InPreparation>
>>> PackageStatusHistory.objects.filter(package_id=package.id)
<QuerySet []>
>>>

What? Why our status history is empty? Here is why: we are using post_save, so the database call for old value happens AFTER we write a new value to the database. We could have switched to pre-save signal (so that we read old value before we update database), however, we need to add extra handler: when the package is created for the first time, it has no id to pass to PackageStatusHistory:

@receiver(pre_save, sender=Package)
def register_status_change(sender, instance: Package, **kwargs):
    old_status_id = instance.id and Package.objects.get(id=instance.id).status_id

    if instance.status_id != old_status_id:
        # There is a status change
        PackageStatusHistory.objects.create(package_id=instance.id,
                                            from_status_id=old_status_id,
                                            to_status_id=instance.status_id)

Now, if we try this:

>>> from cache_fields.models import *
>>> package = Package.objects.get()
>>> package
<Package: 1: Created>
>>> package.status_id = 2
>>> package.status
<Status: InPreparation>
>>> PackageStatusHistory.objects.filter(package_id=package.id)
<QuerySet []>
>>> package.save()
>>> package.status
<Status: InPreparation>
>>> PackageStatusHistory.objects.filter(package_id=package.id)
<QuerySet [<PackageStatusHistory: 1: 1 -> 2>]>
>>>

Notice how we used old_status_id = instance.id and Package.objects.get(id=instance.id).status_id
It is a nice shortcut for if statement: and statement executes second part (right-hand part) ONLY IF the first part is "True".
In our case, if id is None, second part is not executed, so value is old_status_id = None
If it is valid value, second part is executed: old_status_id = Package.objects.get(id=instance.id).status_id

So, it works? Yes, however, it is not the best implementation. Every time you have change (even if not in status field) you will execute an extra database call, which, for large systems will slow you down.

Solution 3: Overwrite init

This method allows us to save extra database calls. Considering that Django models are just Python classes containing database object data, we can use our own fields to save old data:

class Package(models.Model):
    user = models.ForeignKey(UserModel, on_delete=models.CASCADE)
    shipment_cost = models.DecimalField(max_digits=6, decimal_places=2)
    weight = models.DecimalField(max_digits=5, decimal_places=2)
    status = models.ForeignKey(Status, on_delete=models.CASCADE)

    def __init__(self, *args: Any, **kwargs: Any) -> None:
        super().__init__(*args, **kwargs)
        self.cached_status_id = self.status_id

When the object is fetched from database first time, we will have a "duplicate" status field. However, if anywhere in the code, we change the status field, we will have historical data in cached_status_id field. Pretty cool, huh? Notice how we us status_id instead of status, because it is easier to handle integers, rather than objects. Moreover, if not handled correctly (let's say, select_related is not used while fetching) then, you will have extra database calls to Status model.

We can also now use post_save signal, as we handle data right at the beginning. Now if we implement the signal:

@receiver(post_save, sender=Package)
def register_status_change(sender, instance: Package, **kwargs):
    if instance.status_id != instance.cached_status_id:
        # There is a status change
        PackageStatusHistory.objects.create(package_id=instance.id,
                                            from_status_id=instance.cached_status_id,
                                            to_status_id=instance.status_id)

Which results in:

>>> from cache_fields.models import *
>>> package = Package.objects.get()
>>> package
<Package: 1: InPreparation>
>>> package.status_id
2
>>> package.cached_status_id
2
>>> package.status_id = 3
>>> PackageStatusHistory.objects.filter(package_id=package.id)
<QuerySet [<PackageStatusHistory: 1: 1 -> 2>]>
>>> package.save()
>>> package.status_id
3
>>> PackageStatusHistory.objects.filter(package_id=package.id)
<QuerySet [<PackageStatusHistory: 1: 1 -> 2>, <PackageStatusHistory: 1: 2 -> 3>]>
>>>

We prevented extra database calls, yay! We can extend this method saving the dict of the model as variable (by using model_to_dict function) and then we would have access to old value of every field! You can also extend this logic to mixin, as explained in this StackOverflow answer. However, I personally prefer this method, having a class variable for each cached field, which is a little hard to maintain, however, efficient.

Solution 4: Third-Party Libraries

There is also similar implementation with mixin as third-party library: Django Dirty Fields. There is not much explaining to do, so let's just test it:

The code:

@receiver(post_save, sender=Package)
def register_status_change(sender, instance: Package, **kwargs):
    old_status_id = instance.get_dirty_fields(check_relationship=True).get("status", None)

    if instance.status_id != old_status_id:
        # There is a status change
        PackageStatusHistory.objects.create(package_id=instance.id,
                                            from_status_id=old_status_id,
                                            to_status_id=instance.status_id)

The result:

>>> from cache_fields.models import *
>>> package = Package.objects.get()
>>> package
<Package: 1: Shipped>
>>> package.status_id
3
>>> package.cached_status_id
3
>>> package.is_dirty(check_relationship=True)
False
>>> PackageStatusHistory.objects.filter(package_id=package.id)
<QuerySet [<PackageStatusHistory: 1: 1 -> 2>, <PackageStatusHistory: 1: 2 -> 3>]>
>>> package.status_id = 4
>>> package.is_dirty(check_relationship=True)
True
>>> package.get_dirty_fields(check_relationship=True)
{'status': 3}
>>> package.save()
>>> package.status_id
4
>>> PackageStatusHistory.objects.filter(package_id=package.id)
<QuerySet [<PackageStatusHistory: 1: 1 -> 2>, <PackageStatusHistory: 1: 2 -> 3>, <PackageStatusHistory: 1: 3 -> 4>]>
>>>

It works, nice! You can get access to the whole code from this repository. Feel free to add your ideas/suggestions!

Solving DSA Problems. HackerRank: Queen's Attack II

Miradil — Wed, 10 Jan 2024 16:51:48 +0000

Problem statement

You will be given a square chess board with one queen and a number of obstacles placed on it. Determine how many squares the queen can attack.

A queen is standing on an $\times n$ chessboard. The chess board's rows are numbered from $1$ to $n$ , going from bottom to top. Its columns are numbered from $1$ to $n$ , going from left to right. Each square is referenced by a tuple, $(r, c)$ , describing the row, $r$ , and column, $c$ , where the square is located.

The queen is standing at position $r_q, c_q)$ . In a single move, she can attack any square in any of the eight directions (left, right, up, down, and the four diagonals). In the diagram below, the green circles denote all the cells the queen can attack from $(4, 4)$ :

There are obstacles on the chessboard, each preventing the queen from attacking any square beyond it on that path. For example, an obstacle at location $(3, 5)$ in the diagram above prevents the queen from attacking cells $(3, 5)$ , $(2, 6)$ , and $(1, 7)$ :

Given the queen's position and the locations of all the obstacles, find and print the number of squares the queen can attack from her position at $r_q, c_q)$ . In the board above, there are $24$ such squares.

Function Description

Complete the queensAttack function in the editor below.

queensAttack has the following parameters:

int n: the number of rows and columns in the board
nt k: the number of obstacles on the board
int r_q: the row number of the queen's position
int c_q: the column number of the queen's position
int obstacles[k][2]: each element is an array of $2$ integers, the row and column of an obstacle

Returns

int: the number of squares the queen can attack

Input Format

The first line contains two space-separated integers $n$ and $k$ , the length of the board's sides and the number of obstacles.
The next line contains two space-separated integers $r_q$ and $c_q$ , the queen's row and column position.
Each of the next $k$ lines contains two space-separated integers $r [i]$ and $c [i]$ , the row and column position of $o b s t a c l e [i]$ .

Constraints

$\leq 10^5$
$\leq k \leq 10^5$
A single cell may contain more than one obstacle.
There will never be an obstacle at the position where the queen is located.

Subtasks

For $\%$ of the maximum score:

$\leq 100$
$\leq k \leq 100$

For $\%$ of the maximum score:

$\leq 1000$
$\leq k \leq 10^5$

Sample Input 0

4 0
4 4

Sample Output 0

9

Explanation 0

The queen is standing at position $(4, 4)$ on a $\times 4$ chessboard with no obstacles:

Sample Input 1

5 3
4 3
5 5
4 2
2 3

Sample Output 1

10

Explanation 1

The queen is standing at position $(4, 3)$ on a $\times 5$ chessboard with $k = 3$ obstacles:

The number of squares she can attack from that position is $10$ .

Sample Input 2

1 0
1 1

Sample Output 2

0

Explanation 2

Since there is only one square, and the queen is on it, the queen can move 0 squares.

Solution

Hard-Coded solution

At first glance, this is not that hard to solve. We will have just bunch of if statements, and handle each of them accordingly. Let's have array of possible moves for each direction (8 in total). To make it more chess-like, let's make it $\times 3$ (later explained why). So, the initial possible moves at each direction would be:

#define min(a, b) ((a) < (b) ? (a) : (b))

int queensAttack(int n, int k, int r_q, int c_q, int obstacles_rows, int obstacles_columns, int **obstacles)
{
    int possible[3][3];
    possible[1][1] = 0; // not used

    possible[0][1] = n - r_q; // up
    possible[1][2] = n - c_q; // right
    possible[1][0] = c_q - 1; // left
    possible[2][1] = r_q - 1; // down

    possible[0][0] = min(possible[0][1], possible[1][0]); // up left
    possible[0][2] = min(possible[0][1], possible[1][2]); // up right
    possible[2][0] = min(possible[2][1], possible[1][0]); // down left
    possible[2][2] = min(possible[2][1], possible[1][2]); // down right
}

If you think 2D array visually, the structure of possible makes sense. [0][0] would be top-left, and [2][2] would correspond to bottom-right corner.

The possible moves to up, right, left and down directions are obvious. However, in diagonals, it is the minimum of two adjacent directions (see image examples above, or think that, it should be able to move in two directions simultaneously, so shortest one stops first). Now, we just need to understand where each obstacle is compared to queen, and update corresponding value:

#define min(a, b) ((a) < (b) ? (a) : (b))

int queensAttack(int n, int k, int r_q, int c_q, int obstacles_rows, int obstacles_columns, int **obstacles)
{
    int possible[3][3];
    possible[1][1] = 0; // not used

    possible[0][1] = n - r_q; // up
    possible[1][2] = n - c_q; // right
    possible[1][0] = c_q - 1; // left
    possible[2][1] = r_q - 1; // down

    possible[0][0] = min(possible[0][1], possible[1][0]); // up left
    possible[0][2] = min(possible[0][1], possible[1][2]); // up right
    possible[2][0] = min(possible[2][1], possible[1][0]); // down left
    possible[2][2] = min(possible[2][1], possible[1][2]); // down right

    int r_o, c_o;
    for (int i = 0; i < k; ++i)
    {
        r_o = obstacles[i][0];
        c_o = obstacles[i][1];

        if (r_o == r_q)
        {
            if (c_o < c_q) // obstacle is to the left
                possible[1][0] = min(possible[1][0], c_q - c_o - 1);
            else // obstacle is to the right
                possible[1][2] = min(possible[1][2], c_o - c_q - 1);
        }
        else if (c_o == c_q)
        {
            if (r_o < r_q) // obstacle is to the bottom
                possible[2][1] = min(possible[2][1], r_q - r_o - 1);
            else // obstacle is to the top
                possible[0][1] = min(possible[0][1], r_o - r_q - 1);
        }
        else if (abs(r_o - r_q) == abs(c_o - c_q)) // diagonal
        {
            if (r_o > r_q && c_o < c_q) // top-left diagonal
                possible[0][0] = min(possible[0][0], r_o - r_q - 1);
            else if (r_o > r_q && c_o > c_q) // top-right diagonal
                possible[0][2] = min(possible[0][2], r_o - r_q - 1);
            else if (r_o < r_q && c_o < c_q) // bottom-left diagonal
                possible[2][0] = min(possible[2][0], r_q - r_o - 1);
            else // bottom-right diagonal
                possible[2][2] = min(possible[2][2], r_q - r_o - 1);
        }
    }

    int sum = 0;

    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            sum += possible[i][j];

    return sum;
}

Each time, get obstacle, we first check if it is in queen's way. If it is, we find which direction it is, and minimize that direction given obstacles coordinates. If we submit this code:

Yay, it worked! Of course, it did we almost hard coded everything. When I saw this problem, this solution came to my mind. However, I wanted solution that would satisfy me. I never went with solution above (wrote it for the sake of this post). We are better than this right? What if we remove all if statements and have optimal code which finds needed arrays element and minimizes it?

Elegant Solution

First, we need to understand how we can map r and c to indexes of possible. The thing is, we do not even need the indexes of obstacles. Knowing the difference of obstacle indexes with queen indexes gives plenty information to us. So, if we take:

diffr = r_q - obstacle[i][0]
diffc = obstacle[i][1] - c_q (because of the directions, read further)
Let's consider non-diagonal directions
- Either diffr or diffc will be zero.
- If diffr is zero, it means we need possible[1][?]
- If diffc is negative, it means it is in left, so possible[1][0]
- If diffc is positive, it means it is in right, so possible[1][2]
- If diffc is zero, it means we need possible[?][1]
- If diffr is positive, it means it is in top, so possible[0][1]
- If diffr is negative, it means it is in bottom, so possible[2][1]
Now, let's consider diagonal directions
- diffr == diffc
- If both negative, bottom-left, so possible[2][0]
- If both positive, top-right, so possible[0][2] (that is why we took obstacle[i][1] - c_q, to have same positive and negatives)
- Otherwise, it is possible[0][0] or possible[2][2]

Too much analysis, I know. However, one can see that, we are basically focused on sign of differences. Considering the sign is either -1, 0 or 1, one can map these statements into single line of code. That's right, the index of needed value is [1 - sign(diffr)][1 - sign(diffc)]. If we analyze statements above:

If diffr is zero, it is possible[1][?], and the same for diffc
If diffr or diffc is negative, it is index 2: possible[2][?] or possible[?][2]
Otherwise, it is index 0

So, we can wrap all those if statements into this perfect one-liner:

possible[1 - sign(diffr)][1 - sign(diffc)] = min(possible[1 - sign(diffr)][1 - sign(diffc)], max(abs(diffr), abs(diffc)) - 1);

Perfect, isn't it?) We have the part max(abs(diffr), abs(diffc)) - 1) as we need non-zero value (in case it is on top, right, left or bottom). How would our sign function be? Well, as expected right?

int sign(int a)
{
    return (a > 0) ? 1 : ((a < 0) ? -1 : 0);
}

What if I told you, we can be more elegant?

int sign(int a)
{
    return (a > 0) - (a < 0);
}

I am leaving you two alone to get to know each other...

So, our whole solution would be:

#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))

int sign(int a)
{
    return (a > 0) - (a < 0);
}

int queensAttack(int n, int k, int r_q, int c_q, int obstacles_rows, int obstacles_columns, int **obstacles)
{
    int possible[3][3];
    possible[1][1] = 0; // not used

    possible[0][1] = n - r_q; // up
    possible[1][2] = n - c_q; // right
    possible[1][0] = c_q - 1; // left
    possible[2][1] = r_q - 1; // down

    possible[0][0] = min(possible[0][1], possible[1][0]); // up left
    possible[0][2] = min(possible[0][1], possible[1][2]); // up right
    possible[2][0] = min(possible[2][1], possible[1][0]); // down left
    possible[2][2] = min(possible[2][1], possible[1][2]); // down right

    int diffr, diffc;
    for (int i = 0; i < k; ++i)
    {
        diffr = obstacles[i][0] - r_q;
        diffc = c_q - obstacles[i][1];

        if (!diffr || !diffc || abs(diffr) == abs(diffc))
        {
            possible[1 - sign(diffr)][1 - sign(diffc)] = min(possible[1 - sign(diffr)][1 - sign(diffc)], max(abs(diffr), abs(diffc)) - 1);
        }
    }

    int sum = 0;

    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            sum += possible[i][j];

    return sum;
}

No ifs, no control, just pure math. ELEGANT!

Now, if we submit:

Perfect, it works! Yay! You can find solutions here. Feel free to contribute your solution in different language!

Solving DSA Problems. Azerbaijan Qualification 2023: Problem C

Miradil — Fri, 05 Jan 2024 21:44:04 +0000

This problem is from ICPC competition that one of my followers participated (and asked for explanation) on October 22, 2023.

Problem statement

Your task is to determine the number of symmetry axis of the given Roman Numeral.

The following table from Wikipedia displays how the Roman Numerals are written:

Individual decimal places	Thousands	Hundreds	Tens	Units
1	M	C	X	I
2	MM	CC	XX	II
3	MMM	CCC	XXX	III
4		CD	XL	IV
5		D	L	V
6		DC	LX	VI
7		DCC	LXX	VII
8		DCCC	LXXX	VIII
9		CM	XC	IX

Note that:

• The numerals for 4, 9, 40, 90, 400 and 900 are written using "subtractive notation" where the first symbol is subtracted from the larger one (for example, for 40 ("XL") 'X' (10) is subtracted from 'L' (50)). These are the only subtractive forms in standard use.

• A number containing several decimal digits is built by appending the Roman numeral equivalent for each, from highest to lowest.

• Any missing place (represented by a zero in the place-value equivalent) is omitted.

• The largest number that can be represented in the Roman notation is 3999 (MMMCMXCIX).

• The letters I, V, X, M, and only those, are vertically symmetric, the letters I, X, C, D, and only those, are horizontally symmetric.

For example, 200 have the horizontal symmetry only (because CC have the vertical axis, but does not have horizontal one), 2000 have the vertical symmetry only(MM have the vertical axis of symmetry, placed between the letters, but does not have horizontal one), the number 1001 (MI) have no axis of symmetry at all, and the number 30 (XXX) have both axis (vertical one is placed in the middle of the second X letter).

Input

The first line of the input file contains a single integer T - the number of Roman numbers in the test
(1 ≤ T < 4000).

Each of the following T lines contains a single integer: the decimal representation of the Roman Numeral.

The integers are between 1 and 3999, inclusively.

Output

For each numeral, output - if the Roman numeral on it has horizontal symmetry, | if it has vertical symmetry, + if it has both, and ? if it has neither.

Example

Solution

This question seems really easy but is a little tricky to solve. First, I tried to solve it without constructing the roman notation as string. Despite the fact that you can find horizontal symmetry, finding vertical is near impossible with that method. Because for vertical, we need compare left and right part of string:

So, let's convert Arabic numbers to roman:

char roman[20]; // Roman numerals will not exceed 20 characters
int i = 0;

while (num > 0)
{
    if (num >= 1000)
    {
        roman[i++] = 'M';
        num -= 1000;
    }
    else if (num >= 900)
    {
        roman[i++] = 'C';
        roman[i++] = 'M';
        num -= 900;
    }
    else if (num >= 500)
    {
        roman[i++] = 'D';
        num -= 500;
    }
    else if (num >= 400)
    {
        roman[i++] = 'C';
        roman[i++] = 'D';
        num -= 400;
    }
    else if (num >= 100)
    {
        roman[i++] = 'C';
        num -= 100;
    }
    else if (num >= 90)
    {
        roman[i++] = 'X';
        roman[i++] = 'C';
        num -= 90;
    }
    else if (num >= 50)
    {
        roman[i++] = 'L';
        num -= 50;
    }
    else if (num >= 40)
    {
        roman[i++] = 'X';
        roman[i++] = 'L';
        num -= 40;
    }
    else if (num >= 10)
    {
        roman[i++] = 'X';
        num -= 10;
    }
    else if (num >= 9)
    {
        roman[i++] = 'I';
        roman[i++] = 'X';
        num -= 9;
    }
    else if (num >= 5)
    {
        roman[i++] = 'V';
        num -= 5;
    }
    else if (num >= 4)
    {
        roman[i++] = 'I';
        roman[i++] = 'V';
        num -= 4;
    }
    else
    {
        roman[i++] = 'I';
        num--;
    }
}
roman[i] = 0;

Hard coded, but easy, right? Now, we need figure out the symmetry:

Horizontal Symmetry:

This one is pretty easy. For roman numeral to be horizontally symmetric, all of its numerals should be symmetric. So, even if one numeral is not symmetric, the whole number is not symmetric. We can even handle this when converting from Arabic to roman, making horizontal false, when we add non-symmetric letter to array:

bool horizontal = true, vertical = true;
char roman[20]; // Roman numerals will not exceed 20 characters
int i = 0;

while (num > 0)
{
    if (num >= 1000)
    {
        roman[i++] = 'M';
        num -= 1000;
        horizontal = false;
    }
    else if (num >= 900)
    {
        roman[i++] = 'C';
        roman[i++] = 'M';
        num -= 900;
        horizontal = false;
    }
    else if (num >= 500)
    {
        roman[i++] = 'D';
        num -= 500;
    }
    else if (num >= 400)
    {
        roman[i++] = 'C';
        roman[i++] = 'D';
        num -= 400;
    }
    else if (num >= 100)
    {
        roman[i++] = 'C';
        num -= 100;
    }
    else if (num >= 90)
    {
        roman[i++] = 'X';
        roman[i++] = 'C';
        num -= 90;
    }
    else if (num >= 50)
    {
        roman[i++] = 'L';
        num -= 50;
        horizontal = false;
    }
    else if (num >= 40)
    {
        roman[i++] = 'X';
        roman[i++] = 'L';
        num -= 40;
        horizontal = false;
    }
    else if (num >= 10)
    {
        roman[i++] = 'X';
        num -= 10;
    }
    else if (num >= 9)
    {
        roman[i++] = 'I';
        roman[i++] = 'X';
        num -= 9;
    }
    else if (num >= 5)
    {
        roman[i++] = 'V';
        num -= 5;
        horizontal = false;
    }
    else if (num >= 4)
    {
        roman[i++] = 'I';
        roman[i++] = 'V';
        num -= 4;
        horizontal = false;
    }
    else
    {
        roman[i++] = 'I';
        num--;
    }
}
roman[i] = 0;

That's it, now we know if our roman notation is horizontally symmetric or not.

Vertical Symmetry:

This part is a little tricky. As we saw image above, depending on length of roman notation we need to have more checks. So, if our length is odd, we need to check symmetry of middle letter. If it is symmetric, (or length is even) we compare left and right substring of roman notation, making sure they are the same and contain only vertically symmetric letters. So, we would do something like this:

bool is_vertically_symmetric(char letter)
{
    return (letter == 'I' || letter == 'V' || letter == 'X' || letter == 'M');
}

// SOME CODE HERE

int l, r;  // left and right index

if (i % 2) // if length is odd
{
    if (!is_vertically_symmetric(roman[i / 2]))  // check middle letter
        vertical = false;
    else
    {
        l = i / 2 - 1;
        r = i / 2 + 1;
    }
}
else
{
    l = i / 2 - 1;
    r = l + 1;
}

while (vertical && r < i && l >= 0)
{
    if (roman[l] != roman[r] || !is_vertically_symmetric(roman[l]))
        vertical = false;

    l--, r++;
}

That's it! So, our whole code looks like this:

#include <stdio.h>
#include <stdbool.h>

bool is_vertically_symmetric(char letter)
{
    return (letter == 'I' || letter == 'V' || letter == 'X' || letter == 'M');
}

char get_symmetry(int num)
{
    bool horizontal = true, vertical = true;

    char roman[20]; // Roman numerals will not exceed 20 characters
    int i = 0;

    while (num > 0)
    {
        if (num >= 1000)
        {
            roman[i++] = 'M';
            num -= 1000;
            horizontal = false;
        }
        else if (num >= 900)
        {
            roman[i++] = 'C';
            roman[i++] = 'M';
            num -= 900;
            horizontal = false;
        }
        else if (num >= 500)
        {
            roman[i++] = 'D';
            num -= 500;
        }
        else if (num >= 400)
        {
            roman[i++] = 'C';
            roman[i++] = 'D';
            num -= 400;
        }
        else if (num >= 100)
        {
            roman[i++] = 'C';
            num -= 100;
        }
        else if (num >= 90)
        {
            roman[i++] = 'X';
            roman[i++] = 'C';
            num -= 90;
        }
        else if (num >= 50)
        {
            roman[i++] = 'L';
            num -= 50;
            horizontal = false;
        }
        else if (num >= 40)
        {
            roman[i++] = 'X';
            roman[i++] = 'L';
            num -= 40;
            horizontal = false;
        }
        else if (num >= 10)
        {
            roman[i++] = 'X';
            num -= 10;
        }
        else if (num >= 9)
        {
            roman[i++] = 'I';
            roman[i++] = 'X';
            num -= 9;
        }
        else if (num >= 5)
        {
            roman[i++] = 'V';
            num -= 5;
            horizontal = false;
        }
        else if (num >= 4)
        {
            roman[i++] = 'I';
            roman[i++] = 'V';
            num -= 4;
            horizontal = false;
        }
        else
        {
            roman[i++] = 'I';
            num--;
        }
    }
    roman[i] = 0;

    int l, r; // left and right index

    if (i % 2) // if length is odd
    {
        if (!is_vertically_symmetric(roman[i / 2])) // check middle letter
            vertical = false;
        else
        {
            l = i / 2 - 1;
            r = i / 2 + 1;
        }
    }
    else
    {
        l = i / 2 - 1;
        r = l + 1;
    }

    while (vertical && r < i && l >= 0)
    {
        if (roman[l] != roman[r] || !is_vertically_symmetric(roman[l]))
            vertical = false;

        l--, r++;
    }

    if (horizontal && vertical)
        return '+';
    else if (horizontal)
        return '-';
    else if (vertical)
        return '|';

    return '?';
}

int main()
{
    int t, num;
    scanf("%d", &t);

    while (t--)
    {
        scanf("%d", &num);
        printf("%c\n", get_symmetry(num));
    }

    return 0;
}

Pretty compact and clean! Considering that as of writing this post there is no online judge system for problem to submit my solution, I am going to test it manually:

It works, yay! You can test it with more input cases, if you want. You can access the code here. The python version contains a little bit different method of conversion from Arabic to roman. Feel free to contribute solution in different language!

Solving DSA Problems. Eolymp 4036 & 4038: Pre-Order/Post-Order Traversal of a Tree

Miradil — Fri, 05 Jan 2024 21:39:59 +0000

Problem statement

These are two identical problems: Eolymp 4036 and 4038.

The following problem statement is that of 4038, but explanation covers both problems.

Given an array of integers. Create a Binary Search Tree from these numbers. If the inserted value equals to the current node, insert it to the right subtree.

Write method PostOrder that makes Post-Order traversal of a tree. In this traversal method the left subtree is visited first, then the right subtree and finally the root node.

Write the code according to the next interface:

class TreeNode
{
public:
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Tree
{
public:
    TreeNode *head;
    Tree() : head(NULL) {};

    void Insert(int val); // Insert number val to Binary Search Tree
    void PostOrder(void); // Print the vertices of a tree according to post-order traversal
};

You can create (use) additional methods if needed.

Input data

The first line contains number n (1 $≤n≤\leq n \leq$ 100). The second line contains n integers.

Output data

Create the Binary Search Tree from input data. Print the vertices of a tree according to post-order traversal.

Examples

Input example #1

6
14 9 1 14 20 13

Output example #1

14 9 1 13 14 20

Solution

First, we need to understand binary search tree. It is a tree, where each node has at most two children (thus binary). For each subtree, the left contains values less than subtree root value, and the right contains the values more than that. Considering that the first value is always the root of the whole tree, we can derive the next insertion steps: if the new value is less than root node, we go to left, otherwise to right subtree. we iterate through each subtree (again, if less go left, if more go right) until we find a empty node. When empty node is found we add the value there. This makes our binary search tree sorted always, which is one of the benefits of this data structure (check problem statement image). So, our insert function would look like this:

void insert(Node *&node, int n)
{
    if (node == NULL)  // found empty place
    {
        node = new Node(n);
        return;
    }

    if (n < node->val)  // if less, go left
        insert(node->left, n);
    else
        insert(node->right, n);  // if same or more, go right
}

That's it! Our binary tree is done! The next step is to add traversal functions. So, if we want to print sorted output, we would always print the left subtree (lower values), then current node, then right subtree (higher values). However, we are asked preorder (4036) and postorder (4038) output. Then, we just change the order of printing:

void PreOrder(Node *node)
{
    if (node == NULL)
        return;

    printf("%d ", node->val);
    PreOrder(node->left);
    PreOrder(node->right);
}

void PostOrder(Node *node)
{

    if (node == NULL)
        return;

    PostOrder(node->left);
    PostOrder(node->right);
    printf("%d ", node->val);
}

So, the whole code looks like this:

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

class Node
{
public:
    int val;
    Node *left, *right;

    Node(int n)
    {
        val = n;
        left = right = NULL;
    }
};

class Tree
{
public:
    Node *head;

    Tree()
    {
        head = NULL;
    }

    void insert(int n)
    {
        insert(head, n);
    }

    void insert(Node *&node, int n)
    {

        if (node == NULL)
        {
            node = new Node(n);
            return;
        }

        if (n < node->val)
            insert(node->left, n);
        else
            insert(node->right, n);
    }
};

void PreOrder(Node *node)
{
    if (node == NULL)
        return;

    printf("%d ", node->val);
    PreOrder(node->left);
    PreOrder(node->right);
}

void PostOrder(Node *node)
{
    if (node == NULL)
        return;

    PostOrder(node->left);
    PostOrder(node->right);
    printf("%d ", node->val);
}

int main()
{
    int n, a;
    Tree t;

    scanf("%d", &n);

    while (n--)
    {
        scanf("%d", &a);
        t.insert(a);
    }

    // PreOrder(t.head);
    PostOrder(t.head);
    printf("\n");

    return 0;
}

So, if we test our code:

The first one is postorder, and the second is preorder. It works! Now, if we submit:

Two A's! Yay! You can access the code here. Feel free to contribute your solution in different language!

Solving DSA Problems. Eolymp 325: Dangerous route

Miradil — Fri, 05 Jan 2024 21:34:15 +0000

Problem statement

In one country there are n cities, some of which are connected by two-way routes. Cities are numbered by integers from 1 to n. In times of financial crisis the level of the crime in a state rose and the crime groups are organized. The most dangerous of these was "Timur and his gang" led by a notorious criminal circles by Timur, that commit robberies on most of the roads. As a result, some roads became dangerous to drive.

Baha must get out of city 1 and go to city n. Since he appreciate his life too much (and his wallet also), he decided to cheat Timur and go to destination by the least dangerous route, even if it is not the shortest. Baha defined the level of the danger for each road as an integer from 0 (safe) to 10^6 (very dangerous). The danger of the route is the maximum value among the dangers of the roads that make up this route.

Help him to choose the safest route (one which has the minimum possible risk).

Input data

First line contains two integers n and m (2 ≤ n, m ≤ 10^6). Each of the next m lines defines one road and contains three integers:

a, b (1 ≤ a, b ≤ n) - cities, connected with the road;
c (0 ≤ c ≤ 10^6) - the danger of the road.

Any two cities can be connected by several roads.

Output data

One integer - the danger of the most safe route.

Examples

Input example #1

3 2
1 2 1
2 3 1

Output example #1

Input example #2

6 7
1 2 1
2 3 2
3 4 3
4 6 5
2 6 10
2 5 7
5 6 1

Output example #2

Solution

The first algorithm that can come to mind is to use DFS or BFS, however, in those algorithms, you would have a hard time to keep track of route (and the graph can be circular, which makes things harder) and the maximum danger in that route. As the problem implies, we need to take the least dangerous way, in which the least is defined by maximum danger on the trip. So, we can sort the nodes based on their danger level, and then traverse the nodes until we find our destination.

This type of problems is usually solved with disjoint set data structure. We are going to view each node as different set, and then, merge these sets, until we connect 1 to n. For each set, we are going to remember the parent/representative of each node in that set. In the beginning, each node is parent of itself.

int parent[MAX];

int repr(int node)
{
    if (node == parent[node]) return node;
    return parent[node] = repr(parent[node]);
}

This recursion sets the parent for each node in the disjoint set. When we merge two sets, we change second set's node's parents to the parent of the first set. So:

int unite(int x, int y)
{
    int repr1 = repr(x);
    int repr2 = repr(y);

    // sanity check, make sure you are not connecting already connected
    if (repr1 != repr2)
        parent[repr2] = repr1;

}

As stated above, we also need to sort the edges based on their danger levels. For this, we will use qsort with comparator. After sorting, we are going to merge disjoint sets, until nodes 1 and n are connected, that is, repr(1) = repr(n). So, the overall code looks like this:

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000001

int parent[MAX];

typedef struct
{
    int x, y, danger;
} edge;

int repr(int node)
{
    if (node == parent[node])
        return node;

    return parent[node] = repr(parent[node]);
}

void unite(int x, int y)
{
    int x1 = repr(x);
    int y1 = repr(y);

    // sanity check, make sure you are not connecting already connected
    if (x1 != y1)
        parent[x1] = y1;
}

int comp(const void *e1, const void *e2)
{
    return ((edge *)e1)->danger - ((edge *)e2)->danger;
}

int main()
{
    edge edges[MAX];

    int n, m, i;
    scanf("%d %d", &n, &m);

    // In the beginning, each node is its parent
    for (i = 1; i <= n; ++i)
        parent[i] = i;

    for (i = 0; i < m; ++i)
        scanf("%d %d %d", &edges[i].x, &edges[i].y, &edges[i].danger);

    qsort(edges, m, sizeof(edge), comp); // sort by ascending danger

    for (i = 0; i < m; ++i)
    {
        unite(edges[i].x, edges[i].y);

        if (repr(1) == repr(n)) // update parents, and check if 1 and n is connected
            break;
    }

    printf("%d\n", edges[i].danger);

    return 0;
}

If we submit this code:

Hmmm... We got grade D, because we are using more resources? Maybe it is because we have static max size array, what if we do it dynamic, and give minimal size?

int *parent;

// Rest of the functions

int main()
{
    edge *edges;
    int n, m, i;
    scanf("%d %d", &n, &m);

    parent = (int *)malloc((n + 1) * sizeof(int));
    edges = (edge *)malloc(m * sizeof(edge));

    // Rest of the code

    free(parent);
    free(edges);
}

AND THE EXPECTED RESULT IS:

What, the same?? Hold on a minute. What is the problem then?

Maybe, let's try to write this code in C++:

#include <bits/stdc++.h>
#define MAX 1000001

using namespace std;

struct edge
{
    int x, y, danger;
} edges[MAX];

vector<int> parent;

int repr(int node)
{
    if (node == parent[node])
        return node;

    return parent[node] = repr(parent[node]);
}

void unite(int x, int y)
{
    int x1 = repr(x);
    int y1 = repr(y);

    if (x1 != y1)
        parent[x1] = y1;
}

int f(edge a, edge b)
{
    return a.danger < b.danger;
}

int main()
{
    int n, m, i;
    scanf("%d %d", &n, &m);

    parent.resize(n + 1);

    for (i = 1; i <= n; i++)
        parent[i] = i;

    for (i = 0; i < m; i++)
        scanf("%d %d %d", &edges[i].x, &edges[i].y, &edges[i].danger);

    sort(edges, edges + m, f);

    for (i = 0; i < m; i++)
    {
        unite(edges[i].x, edges[i].y);

        if (repr(1) == repr(n))
            break;
    }

    printf("%d\n", edges[i].danger);
    return 0;
}

What if we submit this?

Wow, A+? So, what is the difference? Is it because of we used vector?

Appears no. I also found out while solving this problem. According to Scott Meyers, in his Effective STL book - item 46, std::sort is about 670% faster than qsort due to the fact of inline. 670% Carl, 670%!

Anyways, we managed to score A+! Yay! You can access the code here. Feel free to contribute your solution in different language!

Solving DSA Problems. The 2023 Nordic Collegiate Programming Contest: Problem K

Miradil — Fri, 05 Jan 2024 21:18:31 +0000

This problem is from ICPC competition that I participated in on 7th of October 2023.

Problem statement

Karl is an aspiring C programmer, and is excited by the risks and rewards of low-level manual memory management. In the program he currently develops, he stores a string containing N non-zero bytes into a buffer named "buf". By mistake he accidentally made the buffer 2*N* bytes in size. The last bytes N of the buffer consists of only zero-bytes.

Now Karl needs to know the value N, the size of the string, in a separate part of the program. Traditionally you would recover the length of a string using the strlen function, which reports the position of the first zero-byte in the provided buffer using a linear scan. However, Karl finds that this is much too slow, and that it defeats the advantage of using C in the first place. Can you help Karl efficiently recover N without crashing his program?

The contents of the buffer in sample interaction 3 are shown here.

Interaction

This is an interactive problem where interaction proceeds in rounds. In each round your program can attempt to read a byte from the buffer or report the answer (the value of N):

read

Write a line containing "buf[i]" if you want to try to read byte i of the buffer. If $\leq i \leq 2N$ , then you will get the value of the byte stored in the buffer at index i. If $i < N$ then this will be an integer between 1 and 255, otherwise it will be 0. If $\geq 2N$ or $i < 0$ , you will get the response "Segmentation fault (core dumped)" and your program should exit.

write

Write a line containing "strlen(buf) = M" if you want to report that you think that $N = M$ . Afterwards your program should exit. Your submission will be accepted if you answered correctly, if you did not trigger a segmentation fault, and if you did not attempt to read entries from the buffer too many times.

A maximum of $2⌈log2N⌉2\lceil log_2N\rceil$ reads can be made. If your program attempts to read from the buffer after reaching the limit, it will get the response "Too many reads" and your program should then exit.

It is guaranteed that $\leq N \leq 10^{18}$ .

Solution

This is a little bit different kind of problem. We do not have any input, but we can interact with program. As indicated in problem, we cannot do linear search, as we will hit request limit. We also cannot randomly query the data, as if we are out of bounds, we will get error message and end the program. So, we need a different approach. Let's do this in steps:

Step 1: Find the first zero

Let's see how far we can query each time. If we know that, *i*th element is non-zero, it means, string length is at least $i + 1$ which in turn means, buffer size is at least $2 (i + 1)$ . If we can estimate the max buffer size at each step, we can easily query and index in that range, without going out of bounds! If we start from index 2 (as $\geq 2$ ), we can easily find the zero we need.

#include <stdio.h>

int main()
{
    long long ind = 2, res, nonzeroind = 1;
    printf("buf[%lld]\n", ind);

    int bufval;

    while ((res = scanf("%d", &bufval)) == 1)
    {
        if (bufval > 0)
        {
            nonzeroind = ind;
            ind = (2 * ind + 1);
            printf("buf[%lld]\n", ind);
        }
        else
        {
            // Next step
        }
    }

    return 0;
}

The code while ((res = scanf("%d", &bufval)) == 1) is used in case there is string answer (segmentation fault or too many requests), we should end the program, but, we might also skip it, as our program is never going to trigger those.

Step 2: Binary Search

Now that we have found the index of zero, the length we are searching for is between last non-zero value index and index of zero. After this, for optimality, we can use binary search, and find the bordering zero and non-zero values, which is our needed result. So, we can change our code:

#include <stdio.h>

int main()
{
    long long ind = 2, res, nonzeroind = 1;
    setvbuf(stdout, NULL, _IONBF, 0);
    printf("buf[%lld]\n", ind);

    int bufval;

    while ((res = scanf("%d", &bufval)) == 1)
    {
        if (bufval > 0)
        {
            nonzeroind = ind;
            ind = (2 * ind + 1);
            printf("buf[%lld]\n", ind);
        }
        else
        {
            while (ind - nonzeroind > 1)
            {
                long long newind = (nonzeroind + ind) / 2;
                printf("buf[%lld]\n", newind);

                scanf("%d", &bufval);

                if (bufval)
                    nonzeroind = newind;
                else
                    ind = newind;
            }

            printf("strlen(buf) = %lld\n", nonzeroind + 1);
            return 0;
        }
    }

    return 0;
}

The line setvbuf(stdout, NULL, _IONBF, 0); is used to not buffer the output. Usually, printf prints after output buffer size is maximized, but with this command, it never buffers, writing as soon as it gets the string. If we do not use this, our solution won't be accepted.

If we run this code, with the example in the picture above:

Seems like it works! It also took 4 steps, which is upper bound for us. So, if we submit this code:

Passed all 146 cases! Yay! You can access the code here. Feel free to contribute your solution in different language!

DEV Community: Miradil

Solving DSA Problems. Eolymp 6254: Timebomb

Input data

Output data

Examples

Input example #1

Output example #1

Input example #2

Output example #2

Input example #3

Output example #3

Solving DSA Problems. HackerRank: Winning Lottery Ticket

Input Format

Constraints

Output Format

Sample Input 0

Sample Output 0

Explanation 0

Solving DSA Problems. LeetCode 142: Linked List Cycle II

Example 1

Example 2

Example 3

Constraints

Follow Up

Default Code

Floyd's Cycle Finding Algorithm or Hare-Tortoise Algorithm

Visual Explanation

Math Explanation

Solving DSA Problems. CodeForces 1918-A: Brick Wall

Input

Output

Example

input

output

Solving DSA Problems. HackerRank: Balanced Brackets

Function Description

Returns

Input Format

Constraints

Output Format

Sample Input

Sample Output

Explanation

Solving DSA Problems. LeetCode 58: Length of Last Word

Example 1

Example 2

Example 3

Constraints

Default Code

Approach 1: Parse string with strtok

Approach 2: Parse string with sscanf

Approach 3: Loop search

How to detect field changes in Django

The Problem

Solution 1: The easy way?

Solution 2: Query the old value

Solution 3: Overwrite init

Solution 4: Third-Party Libraries

Solving DSA Problems. HackerRank: Queen's Attack II

Function Description

Returns

Input Format

Constraints

Subtasks

Sample Input 0

Sample Output 0

Explanation 0

Sample Input 1

Sample Output 1

Explanation 1

Sample Input 2

Sample Output 2

Explanation 2

Hard-Coded solution

Elegant Solution

Solving DSA Problems. Azerbaijan Qualification 2023: Problem C

Problem statement

Input

Output

Example

Approach 1: Parse string with `strtok`

Approach 2: Parse string with `sscanf`