nitin12384's blog

By nitin12384, history, 2 months ago, In English

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

Full text and comments »

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

By nitin12384, 2 months ago, In English

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.

Full text and comments »

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

By nitin12384, history, 4 months ago, In English

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)$$$?

Some algorithms that don't work in this case.

Full text and comments »

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

By nitin12384, history, 4 months ago, In English

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?

Full text and comments »

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

By nitin12384, history, 4 months ago, In English

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

Full text and comments »

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

By nitin12384, history, 4 months ago, In English

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.

Full text and comments »

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

By nitin12384, history, 5 months ago, In English

This problem https://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?

Full text and comments »

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

By nitin12384, history, 6 months ago, In English

https://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://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://codeforces.com/contest/49/submission/223125

Full text and comments »

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

By nitin12384, history, 6 months ago, In English

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
where k is like 200-300 or something. But I am not sure.)

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://codeforces.com/blog/entry/62865 )

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

Full text and comments »

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

By nitin12384, history, 17 months ago, In English

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

Full text and comments »

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