Problem statement

Given a 1-indexed array of 0s and 1s of length $$$n$$$, sort it in $$$O(n)$$$ time with a model of computation that allows only read on the array and reversal operations for write.

A reversal operation is done by choosing a subarray with bounds $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$, and reversing it. A reversal operation takes $$$O(r-l)$$$ time.

Note — The goal is not to achieve $$$O(n)$$$ number of reversals, but total $$$O(n)$$$ time.

Note — We cannot optimize the reversal operation. The model of computation does not allow that. Any reversal on a subarray of size $$$S$$$ will take $$$O(S)$$$. You can think of it in a way that a stupid monkey is doing the reversals, and he will always take $$$O(S)$$$ time for a subarray of size $$$S$$$. You can only tell him $$$l$$$ and $$$r$$$, not how to do the reversal

Where am I on this?

A merge-sort based solution is straightforward, but $$$O(n*logn)$$$

I think it is impossible to solve it in O(n)

I tried to consider an array of repeating $$$0 1$$$, and never found a way to sort it in $$$O(n)$$$

0 0 0 ... 1 1 1 | 0 0 0 .... 1 1 1

Help needed

If there is a way, please explain.

If not, any other intuitions to prove that it's not possible?

Something really bad that could have happened with me was prevented, with a stroke of crazy fucking luck. I thank god for that, and I have decided to give out some help to other as a part of thanks.

I will personally help 5 people in comments asking their doubts in anything CP/Math related — any problem or anything in my capacity. (Based on my capacity. If a red asks me something crazy, I am sorry.)

I have been expert, but I lost touch with CP recently. I really love maths. I think I might be able to help people <= specialist.

Feel free to downvote, I dont care (Maybe you should, so that folks dont start a trend with these kind of blogs) . I just want to give out help and earn Karma and keep god's blessing on me. (Sorry I am lonely, This was one of the better idea I had to help others)

Edit — I am glad I could help. Based on my commitment, I have responded to 5+ peoples. I will still try to keep responding to questions, but might not be able to. Thanks guys for the opportunity.

Problem Name — Separate It

Statement

You are given an array $$$a$$$ containing $$$n$$$ elements and another array $$$b$$$ containing $$$m$$$ elements. ( Both are 0 indexed ) You want to separate $$$a$$$ into $$$m$$$ non-empty contiguous subarrays, such that each element belongs to exactly one subarray.

Also, the sum of elements of $$$r$$$th subarray ( $$$0 \le r \lt m$$$ ) should be divisible by $$$b_r$$$.

Find the total number of way to seperate $$$a$$$ into $$$m$$$ subarrays fulfilling the given conditions, modulo $$$10^9 + 7$$$

Input Format

$$$n$$$ $$$m$$$
$$$a_0 \; a_1 ... a_{n-1}$$$
$$$b_0 \; b_1 ... b_{m-1}$$$

First line contains two space separated integers $$$n$$$ and $$$m$$$.
Second line contains $$$n$$$ space separated integers denoting array $$$a$$$.
Third line contains $$$m$$$ space separated integers denoting array $$$b$$$.

Constraints

$$$1 \le n \le 10^3$$$
$$$1 \le m \le 10^3$$$
$$$1 \le a_i \le 10^9$$$, where $$$0 \le i \lt n-1$$$
$$$1 \le b_i \le 10^9$$$, where $$$0 \le i \lt m-1$$$

Examples

4 2
1 2 4 6
1 2

Possible separations
[1][2,4,6]
[1,2][4,6]
[1,2,4][6]

4 3
1 2 5 6
1 2 2

No way to separate array a

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

Possible ways
[7][7][2,1][5,6]
[7][7,2][1,5][6]
[7,7][2][1,5][6]

Source — Infosys Coding Round on 21st Jan.

I have tried a lot and I was only able to come up with a $$$O(n \cdot n \cdot m)$$$ approach using DP, but couldn't optimize further.

If anyone has any idea how to solve it, or knows any similiar problem, please help.

Today I solved this 1600-rated problem.
I tried this problem (for about 2h+) around one month ago and I wasn't able to solve it then. So I left it for later, without seeing the editorial.

Today I tried it again in two sittings and devoted 1h + 2h time to it. I was stuck multiple times, but I just wanted to solve it on my own, really didn't want to give up.
I finally managed to solve it on my own without seeing the editorial.
Though it was very satisfying to solve it, I am still confused about whether I wasted too much time(overall 5h+) on this problem.
This happens to me a lot. I spend 1.5h+ on average on a problem and it's very common for me to spend around 5-6h+ on some problems.

Every time I get stuck on a solvable problem and I have the option to jump to the editorial, I am afraid.
I fear that I will miss the important skill development that I can get if I manage to solve this problem on my own.
I feel that coming up with the solution on your own is far greater that knowing the solution.

I do enjoy solving problems a lot, and I really love the feeling when I solve harder problems on my own. But sometimes, the amount of time I spend makes me wonder if I am doing the right thing.

Questions

(1) Should I have given up earlier and saved my time? I would have been able to solve more problems.

(2) Sometimes I end up spending hours and still don't get to the solution. Is that time considered almost wasted?

(3) Consider, Person 1 — Spent 10 hours and solved 2 problems of X difficulty on his own, Person 2 — Spent 10 hours and solved 6 problems of X difficulty (5 on his own, and 1 by seeing the editorial). Consider both person have the same skill level at this point. Which person is doing better?

(4) Will I grow too slowly if I keep devoting too much time to the problems?

(5) My goal is to touch 1900+ Rating by end of April 2023 (I have a peak rating 1841). If I keep following this strategy will I be able to achieve my goal?

(6) What is the maximum time you have spent on a solvable problem? (Let's say a solvable problem is defined as a problem of rating within 200 rating range of your rating at the time of attempting the problem)?

(7) Any high rated user(CM+) who follows similiar strategy?

In todays contest tourist solved ABC in 5 minutes. He solved C in 3 minutes.
How is that even possible?
C is not a so simple problem, it has a big complicated statement, and it takes some time to observe the task and simplify the computation to be able to do it in O(n) / O(nlogn).
Even top LGM's and reds took 8-10 minutes.
This is completely unbelievable, how can a human possibly possess so much speed?
I cannot imagine someone looking at C, reading and understanding the statement, and thinking of an approach, and then implementing it, all under fucking 3 minutes. HOW IS THIS POSSIBLE !!!!!!!!

Say you have a variable length array declared in a function, and you try to initialize it using memset in a lambda function, like this.

int n; cin>>n;
int cnt[n];
auto reset = [&](){
    memset(cnt, 0, sizeof(cnt));
};

It will not work correctly because sizeof(cnt) will return sizeof(int*) instead of n*sizeof(int).
That is because variable length array seems to decay to pointer when using labmda functions.

But surprisingly, this happens only in C++17, not in C++20.
In C++ 20, sizeof(cnt) will return n*sizeof(int).

Here is code demonstating this. You can try to run it in custom invocation.

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

int main()
{
    int arr1[100];
    cout << "sizeof arr1(outside lambda) = " << sizeof(arr1) << endl;
    auto lambda1 = [&](){
        cout << "sizeof arr1(in lambda) = " << sizeof(arr1) << endl;
    };
    lambda1();
    int n = 100;
    int arr2[n];
    cout << "sizeof arr2(outside lambda) = " << sizeof(arr2) << endl;
    auto lambda2 = [&](){
        cout << "sizeof arr2(in lambda) = " << sizeof(arr2) << endl;
    };
    lambda2();
}

Just be cautious while using arrays in lambda functions. I got wrong answer in a problem due to this, and it took me a lot of time to figure out that this was causing the issue.

Anyone is welcome to post comment of any related facts/insight, or maybe some explanations about why this happens, and why this doesn't happens in C++20.

https://mirror.codeforces.com/problemset/problem/1215/B

https://mirror.codeforces.com/contest/1215/submission/60611022

Here's a problem and Um_nik's solution to it.
I was thinking about a lot of things, tried DP etc. and was unable to solve it.
Then I saw this crazily concise solution of Um_nik.
Can someone explain, what's his approach?
Like, I understood what he's doing, but didn't understand why it's working, or I should rather say, how he came to this solution.
Like the idea, or some convincing observation behind this idea.

I didn't find any announcement blog for ABC 278.
So I posted this .

Um_nik is uploading his screencast of most rounds of Codeforces and Atcoder.

Since Um_nik said he is open to suggestion, I would request Um_nik to add some commentary . Basically, you speak up about your approach, do loud thinking. Please convey what do you think and how you build up to the solution?

This would cause so many benefits :
1. Your screencast becomes very interesting.
2. More people would watch your screencast.
3. People would be able to learn much more from you that way.
+ many more ...

Personally, after giving a round and up-solving I would really like to watch the approach of Um_nik, what his solution was, how he came up with that, and how he implementation.
But the current videos are just equivalent to just looking up your submission and give no further learning and insights.

The task is to find the position of any one peak element in a 2D integer matrix of size $$$m * n$$$, if a peak element exists. Adjacent elements are allowed to be equal.

An element is called peak if it is strictly greater than all of its adjacent elements. For element at position $$$(i,j)$$$, these elements are considered adjacent if they exist in the matrix :
$$$(i+1, j)$$$, $$$(i-1, j)$$$, $$$(i, j+1)$$$, $$$(i, j-1)$$$

Examples of peak:

$$$2\;4\;5\;5\;4\;2$$$
$$$2\;4\;5\;5\;4\;2$$$
$$$2\;4\;5\;5\;4\;6$$$
$$$2\;4\;5\;5\;4\;2$$$
$$$2\;4\;5\;5\;4\;2$$$
For this matrix, only one element is peak, element at position $$$(3,6)$$$

$$$2\;4\;5\;5\;4\;2$$$
$$$5\;4\;5\;5\;4\;2$$$
$$$2\;4\;5\;5\;4\;2$$$
$$$2\;4\;5\;5\;4\;2$$$
$$$2\;4\;5\;7\;4\;2$$$
For this matrix, there are two peak elements, one at $$$(2,1)$$$, and one at $$$(5,4)$$$. You can find any one of them.

$$$2\;4\;5\;5\;4\;2$$$
$$$2\;4\;5\;5\;4\;2$$$
$$$2\;4\;5\;5\;4\;2$$$
$$$2\;4\;5\;5\;4\;2$$$
$$$2\;4\;5\;5\;4\;2$$$
For this matrix, There is no peak.

A simple algorithm would be to linearly scan all elements, with the runtime of $$$O(m*n)$$$.
Is there any algorithm better than $$$O(m*n)$$$?

In his atcoder profile,he has mentioned that his birth year is 2010.
His Codeforces profile.

This is totally unbelievable for me, that how can someone achieve so much maturity in maths, problem-solving, analysis, deduction at so less age.

Is this some mistake that he has mentioned 2010 as his birth year?
If its not a mistake, then wont he be the youngest LGM on codeforces?

I want to see my detailed profile analysis for atcoder. Mostly I need to know how many problems I solved of which point value. I want to see if I solve enough hard problems, or else I mostly solve only easy problems.

Example counterparts for codeforces analyzer are mentioned below :

Is it possible?

The only thing I have found is that I can check the number of problems solved in atcoder using stopstalk. But it can only display the count of problems solved and names of the problems solved, but no other information.

Is there any analyzer for atcoder that can provide more detailed info?

I believe that it could be beneficial for a lot of people to be able to analyze their atcoder profile.

Some examples of such analyzer tools for codeforces :

A. CF Analytics

B. Codeforces Visualizer

This problem appeared in ABC 271 today in just an easier version of this codeforce problem with $$$k = 0$$$ and $$$a_i \le 2^{30}$$$

Maybe it's a coincidence that the authors came up with the almost exact same problem.

Even if authors didn't copied the problem, its still an unfair since there is a direct advantage for people who have solved the problem on codeforces.

This problem https://mirror.codeforces.com/problemset/problem/20/A is a very very simple string processing problem.
All you have to do is to convert contiguous groups of '////' to one '/' and take care of one edge case when there is a '/' in the end of string.

This problem is supposed to have difficulty rating of 800-900. At most 1000, No way that this problem could be called a 1700 difficulty rating problem.

Here is the statement

The new operating system BerOS has a nice feature. It is possible to use any number of characters '/' as a delimiter in path instead of one traditional '/'. For example, strings //usr///local//nginx/sbin// and /usr/local/nginx///sbin are equivalent. The character '/' (or some sequence of such characters) at the end of the path is required only in case of the path to the root directory, which can be represented as single character '/'.
A path called normalized if it contains the smallest possible number of characters '/'.
Your task is to transform a given path to the normalized form.
Input
The first line of the input contains only lowercase Latin letters and character '/' — the path to some directory. All paths start with at least one character '/'. The length of the given line is no more than 100 characters, it is not empty.
Output
The path in normalized form.

Examples :

Input
//usr///local//nginx/sbin
Output
/usr/local/nginx/sbin

I understand that the old contest has a lesser number of participants and hence, the count of people who solved the problem is less. But why isn't this normalized accordingly?

https://mirror.codeforces.com/problemset/problem/49/D

I managed to solve this problem with a very very complicated approach involving separating groups of consecutive characters which are same. Then separating the even-sized groups and then applying some DP on them.

My submission :

https://mirror.codeforces.com/contest/49/submission/167985059

I want to ask if anyone can tell me a simpler approach. I tried to find an editorial but there were none. I also couldn't make sense of some accepted submissions that I tried to look at.

Or if someone could make some sense of this solution. https://mirror.codeforces.com/contest/49/submission/223125

Now, since Codechef has announced Integral Problem Difficulty ratings, I have some questions:

How is Problem Difficulty Rating calculated on Codechef?
(For instance, in Codeforces, it is calculated based on how many users were able to solve it in the contest.)

How does CodeChef Problem Difficulty Rating compare with Codeforces? What is approx mapping?
(Ex: What would be the difficulty rating of a problem on Codeforces, whose difficulty rating on CodeChef is 2441 ?)
(I guess that mapping may be like

Codeforces_Rating(x) == Codechef_Rating(x) — k

What is the basic implication of Codechef rating?
(For instance, in Codeforces, Approximately this means that if the rating of the problem is equal to yours, then on a typical round you would solve the problem with a probability of 0.5.
Source : https://mirror.codeforces.com/blog/entry/62865 )

For Codeforces problem difficulty ratings, there are many blogs like https://mirror.codeforces.com/blog/entry/46304,
but there are none for CodeChef. That is why I resorted to asking about it here.

The problem is "What is the number of recursive palindromic binary strings of length n ? " A string "s" of length n is recursively palindromic is "s" is a palindrome and the first half of "s", is also recursively palindrome. Example of recursively palindromic strings : 0001000 1011101 111

For example for n = 5, there are four such strings {00000, 00100, 11011, 11111}, so answer is 4.

What I came up with is : T1 = T2 = 2 (n is odd) Tn = 2*T((n-1)/2) (n is even) Tn = T(n/2)

Interestingly . It turns out that Tn = 2^(no. of set bits in binary representation of n) . Can someone explain an intuition behind this simple answer, and how can one come up with this solution ?

Reference : https://discuss.codechef.com/t/official-basic-math-combinatorics-problems/65236/16