testUser44's blog

By testUser44, history, 5 months ago, In English

Solution: 2237B - Annoying the Ghost

Hint 01

We are given that the final array $$$b$$$ is strictly increasing ($$$b_1 \lt b_2 \lt \dots \lt b_n$$$). We construct this final array from left to right. Since we can only add ducks, an initial pile $$$a_j$$$ can be transformed into a target pile $$$b_i$$$ if and only if $$$a_j \le b_i$$$.

Hint 02

If we decide which elements of $$$a$$$ map to which elements of $$$b$$$, the number of adjacent swaps required to reorder them into their final positions is exactly the number of inversions created by our choice.


Greedy Approach

Since $$$b$$$ is strictly increasing ($$$b_1 \lt b_2 \lt \cdots \lt b_n$$$), the condition $$$a_j \le b_i$$$ becomes easier to satisfy as $$$i$$$ increases. Therefore, it is best to process the elements of $$$b$$$ from left to right.

For each $$$b_i$$$, we choose the leftmost unused position $$$j$$$ such that $$$a_j \le b_i$$$. This greedy choice works perfectly because:

  1. Choosing an earlier valid element leaves later elements available for the larger values of $$$b$$$ coming up next.
  2. Taking the leftmost available element minimizes the distance it has to travel, which keeps the number of swaps as small as possible.

Counting Swaps

Suppose the element chosen for $$$b_i$$$ is at position $$$j$$$. To move it to its correct spot, it must swap past every element to its left that hasn't been used yet. Elements that are already matched don't count because they have already been moved out of the way.

So, the number of swaps needed for position $$$j$$$ is simply the number of unmatched positions before it:

$$$|\{k \lt j \mid k \text{ has not been matched yet}\}|$$$

While this can be optimized using a Fenwick Tree (Binary Indexed Tree) to query prefix sums in $$$O(\log n)$$$ time, the constraints here allow us to just use a simple loop to count unmatched elements in $$$O(n)$$$ time per step. Summing these counts up for all elements gives us our final answer. If we ever find a $$$b_i$$$ that cannot match with any available $$$a_j$$$, it's impossible, so we output -1.

int n, ans = 0;
cin >> n;
vector<int> a(n), b(n), seen(n + 1);

for (int& it : a) cin >> it;
for (int& it : b) cin >> it;

for (int i = 0; i < n; ++i) {
    bool ok = false;
    for (int j = 0; j < n; ++j) {
        if (a[j] <= b[i] && !seen[j]) {
            ok = true;
            seen[j] = 1;
            break;
        }
        if (!seen[j]) {
            ++ans;
        }
    }
    if (!ok) {
        cout << -1 << endl;
        return;
    }
}

cout << ans << endl;

Complexity Analysis

  • Time Complexity: $$$\mathcal{O}(n^2)$$$ per test case. Since $$$\sum n \le 2000$$$, an $$$n^2$$$ approach easily runs well within the 1.5-second time limit.
  • Space Complexity: $$$\mathcal{O}(n)$$$ to store the arrays and the tracking (seen) array.

Full text and comments »

  • Vote: I like it
  • -22
  • Vote: I do not like it

By testUser44, history, 10 months ago, In English

Salam everyone,

This blog is a simple and practical guide on how to practice competitive programming, how to learn new algorithms, when to read others’ code, and how to prepare for NOI / OI-style contests. Everything here is based on practice ideas, written in easy English, with no extra theory.


1. How to Learn a New Algorithm

Do NOT learn algorithms first. Learn them when you need them.

Correct way to learn an algorithm:

  1. Pick a problem.
  2. Think seriously for about 15 minutes.
  3. If you are stuck, read the editorial.
  4. If the editorial uses a new algorithm or idea you don’t know:
  • Read one article about it (USACO Guide, CP-Algorithms, or CF blog).
  • Understand the idea, not memorise it.
  • Implement it in that same problem.
  1. Move on to the next problem.

Why this works:

  • You learn the algorithm in context.
  • You remember when to use it, not just what it is.
  • Important algorithms appear again naturally in future problems.

Do NOT:

  • Study algorithms by topic first.
  • Memorise without using.
  • Spend many days only on theory.

2. How to Practice Daily (Exact Routine)

Main daily practice (most important)

Try to practice 90–180 minutes every day.

  1. Open Codeforces Problemset.
  2. Choose a rating range where you can solve about 30–40% of problems.
  3. Sort problems by newest first.
  4. Pick a problem.

For each problem:

  • Think 15 minutes very seriously.
  • If new ideas keep coming, continue.
  • If you are stuck, read the editorial.
  • Always implement the solution.
  • Add a one-line comment: what did you learn from this problem?

Repeat 2–5 problems per day, depending on difficulty.


Extra daily thinking (optional but strong)

  • Pick one harder problem.
  • Think about it during:
  • School

  • Walking
  • Shower
  • No coding, only thinking.

This improves idea generation.


Weekly practice

  • Join every Codeforces and AtCoder contest you can.
  • Virtual the contests you miss.
  • If preparing for NOI, do one OI-style virtual contest per week.

3. I Can’t Implement Myself — Should I See Others’ Code?

Short answer: Yes, but only in the correct order.

Correct order:

  1. Try to implement the solution yourself first.
  2. If:
  • You understand the idea,
  • But your code is messy or buggy,
  1. Then:
  • Look at one clean editorial or solution code.
  • Only to understand structure.
  1. Close it.
  2. Rewrite the solution from scratch.

Never do this:

  • Copy-paste code.
  • Read others’ code before trying.
  • Use others’ code as a shortcut.

Rule to remember: Idea from editorial is fine. Code from others is last resort. Always rewrite yourself.


4. How to Prepare for NOI

NOI is an OI-style contest:

  • Long problems
  • Subtasks
  • Deep thinking
  • Time management matters a lot

Main NOI preparation plan

1. Base practice (daily)

  • Grind Codeforces problems using the 30–40% rule.
  • This builds speed, idea generation, and confidence.

2. Weekly OI virtual (very important)

Once per week:

  • Do one full OI-style contest.
  • Treat it like a real contest:
  • Read all problems.

  • Go for subtasks.
  • Manage time carefully.

After the contest:

  • Upsolve only problems you can understand.
  • Focus on why subtasks work and how to extend them.

OI time management strategy (example)

For 3 problems in 4 hours:

  1. Read all problems (15 minutes).
  2. Think about each for ~15 minutes.
  3. Order them from easiest to hardest.
  4. Spend about 1 hour per problem.
  5. If after ~50 minutes you are still stuck:
  • Implement subtasks.
  • Move on.

Do not tunnel on one problem.


Key NOI skills to build

  • Subtask thinking
  • Partial solutions
  • Brute force → optimisation
  • Time allocation
  • Staying calm for long contests

Final Rules to Remember

  • Reading editorials is not cheating.
  • Learning fast is better than solving alone.
  • Implementation is mandatory.
  • Live contests train independence.
  • NOI needs long focus and subtask skill.
  • Consistency matters more than talent.

Thanks for reading. I hope this helps you practice smarter and prepare better. Best of luck with your competitive programming journey.

Full text and comments »

  • Vote: I like it
  • -30
  • Vote: I do not like it

By testUser44, history, 13 months ago, In English

Why do we need Binary Exponentiation?

In competitive programming, we often need to calculate expressions like a^b. A simple approach might be to use pow(a, b) or a loop, but both are inefficient or unsafe.

Let’s understand why and how we can improve it.


1. The Basic Approach

We can multiply a by itself b times:

int a = 2, b = 13, ans = 1; 
const int M = 1e9 + 5;

for(int i = 0; i < b; ++i) {
    ans *= a;
    ans %= M; // To avoid overflow
}

This works, but its time complexity is O(b) — very slow when b is large (for example, b = 10^9).


2. The Problem with pow() Function

You might think of using the built-in pow() function:

pow(a, b);

But this is not reliable for competitive programming. pow() works with floating point numbers, which cannot store large integers with 100% accuracy. It may give wrong results for big powers.


3. The Idea Behind Binary Exponentiation

We can make it faster using the Divide and Conquer idea.

Instead of computing a^b directly, notice these patterns:

  • If b is even: a^b = (a^(b/2)) * (a^(b/2))
  • If b is odd: a^b = a * (a^(b/2)) * (a^(b/2))

Each time we divide b by 2, so the time complexity becomes O(log b).


4. Step-by-Step Example

Let’s take 2^16:

2^16 = 2^8 * 2^8
2^8  = 2^4 * 2^4
2^4  = 2^2 * 2^2
2^2  = 2^1 * 2^1

We only need 4 steps instead of 16 multiplications. That’s why it’s called Binary Exponentiation — we keep halving the power (like binary bits).


5. Recursive Implementation

Here’s the clean recursive version of Binary Exponentiation:

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

const int M = 1e9 + 5;

int binExpRecursion(int a, int b) {
    if (b == 0) return 1;
    int res = binExpRecursion(a, b / 2);
    if (b & 1) {
        return (a * (1LL * res * res % M)) % M;
    } else {
        return (1LL * res * res) % M;
    }
}

int main() {
    int a = 2, b = 13;
    cout << binExpRecursion(a, b) << endl;
}

6. Working Explanation

When b = 13, recursion expands like this:

f(2,13) = 2 * f(2,6) * f(2,6)
f(2,6)  = f(2,3) * f(2,3)
f(2,3)  = 2 * f(2,1) * f(2,1)
f(2,1)  = 2 * f(2,0) * f(2,0)

At the base case, f(2,0) = 1.

So it combines results from the bottom up efficiently, doing only log(b) recursive calls.


7. Complexity

  • Time Complexity: O(log b)
  • Space Complexity: O(log b) (for recursion stack)

8. Modular Arithmetic Note

We take modulo M (like 1e9 + 7 or 1e9 + 5) to prevent overflow and keep numbers within bounds.

This makes it safe for problems where you need to compute results modulo a large prime.


Summary

Concept Formula Explanation
Even Power a^b = (a^(b/2)) * (a^(b/2)) Divide into two equal halves
Odd Power a^b = a * (a^(b/2)) * (a^(b/2)) Multiply once more by a
Base Case b == 0 → return 1 Anything raised to 0 is 1
Complexity O(log b) Much faster than O(b)

Binary exponentiation is one of the most important building blocks in number theory and modular arithmetic. Learn it once, and you’ll use it everywhere.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By testUser44, history, 13 months ago, In English

Bitwise operations are very powerful tools in competitive programming. They work directly on the binary form of numbers and are extremely fast. Here are some simple but useful tricks every beginner should know.


1. Even or Odd Check – (n & 1)

Every number in binary ends with either 0 or 1. If the last bit is 1, the number is odd. If the last bit is 0, the number is even.

int n = 7;
if (n & 1) cout << "Odd\n";
else cout << "Even\n";

Explanation: Binary of 7 is 111. The last bit is 1, so it is odd. Binary of 8 is 1000. The last bit is 0, so it is even.


2. Divide by 2 – (n >> 1)

The right shift operator >> divides a number by 2 for each shift.

int n = 10;
cout << (n >> 1) << endl; // Output: 5

Explanation: 10 (1010 in binary) becomes 101 after one right shift, which equals 5.


3. Multiply by 2 – (n << 1)

The left shift operator << multiplies a number by 2 for each shift.

int n = 5;
cout << (n << 1) << endl; // Output: 10

Explanation: 5 (0101 in binary) becomes 1010 after one left shift, which equals 10.


4. Uppercase to Lowercase and Vice Versa

Characters are also stored as numbers (ASCII codes). In ASCII:

  • Uppercase letters 'A'–'Z' have the 5th bit unset (0).
  • Lowercase letters 'a'–'z' have the 5th bit set (1).

This allows easy conversion using bitwise operations.

Convert Uppercase to Lowercase

Set the 5th bit.

char A = 'A';
char a = A | (1 << 5);
cout << a << endl; // prints 'a'

Convert Lowercase to Uppercase

Unset the 5th bit.

char d = 'd';
char D = d & ~(1 << 5);
cout << D << endl; // prints 'D'

You can also use shorter tricks:

cout << (char)('C' | ' ') << endl; // 'C' -> 'c'
cout << (char)('c' & '_') << endl; // 'c' -> 'C'

5. Clearing Bits (LSB and MSB)

Sometimes we need to clear some bits (set them to zero).

Clear the lowest k bits (LSB)

int n = 255; // 11111111 in binary
int k = 3;
int result = n & ~((1 << (k + 1)) - 1);
// Clears bits 0,1,2,3
cout << result << endl;

Keep only the lowest k bits (clear MSB)

int n = 255; // 11111111
int k = 3;
int result = n & ((1 << (k + 1)) - 1);
// Keeps bits 0,1,2,3 -> 00001111
cout << result << endl; // 15

Summary

  1. Even or Odd Check: (n & 1)
  2. Divide by 2: (n >> 1)
  3. Multiply by 2: (n << 1)
  4. Uppercase ↔ Lowercase: set or unset the 5th bit
  5. Clear bits: use bit masks with ~ and shifts

Bitwise operations may look tricky at first, but they are fast, compact, and very helpful in contests once you understand the binary logic behind them.

Full text and comments »

  • Vote: I like it
  • -18
  • Vote: I do not like it

By testUser44, history, 14 months ago, In English

Hello everyone,

I am a complete beginner who has just started Competitive Programming, and my short-term goal is to reach the Pupil rank within the next three months. Since I am still new, I would like to get some guidance and suggestions from the experienced members here about how to approach practice and learning in the most effective way.

My main confusion is about how to structure my practice. I am not sure how many problems I should solve daily and whether I should participate in every Codeforces contest or just some of them. Another doubt I have is about the problem-solving process itself: how much time should I spend thinking about a problem before checking the editorial, and how can I read the editorial in a way that truly helps me grow instead of just copying the solution?

Sometimes I also face difficulty when I try to understand others’ code or even the editorial itself. There are cases where I read it multiple times but still cannot fully understand what is going on. I want to know what I should do in such situations so that I do not get stuck or demotivated, and instead keep learning step by step.

In addition to that, I would like to know which topics a beginner should focus on first, and if there are any reliable resources or roadmaps that can guide me through the basics in a structured way.

I know that consistency, patience, and practice are the key factors in improvement, but I do not want to waste time following the wrong approach. Any kind of advice, tips, or roadmap from experienced programmers would be highly appreciated. Thank you very much for your time and guidance .

Full text and comments »

  • Vote: I like it
  • -19
  • Vote: I do not like it