form a "decreasing histogram". We can still find the starting cell $(va,vb)$.
First, let's compute, ). Now the white cells form a "decreasing histogram". We can still find the
starting cell $(va,vb)$.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
→ Find user
→ Recent actions
You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:
305— search for 305, most probably it will find blogs about the Round 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
Codeforces Round #810 Editorial Sorry for the late editorial. May this editorial help you. If you have questions, feel free to ask.
[problem:1711A]
<spoiler summary="hint1.">
The minimal weight is at least $1$ since $1$ divides any integer (so $1$ divides $p_1$).
</spoiler>
<spoiler summary="solution">
Since $k+1$ does not divide $k$, a permutation with weight equal to $1$ is: $[n,1,2,\cdots,n-1]$.
</spoiler>
<spoiler summary="code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void work()
{
int n;
cin>>n;
cout<<n<<' ';
for (int i=1;i<n;i++)
cout<<i<<' ';
cout<<endl;
}
int main()
{
int casenum=1;
cin>>casenum;
for (int testcase=1;testcase<=casenum;testcase++)
work();
return 0;
}
~~~~~
</spoiler>
[problem:1711B]
<spoiler summary="hint1.">
See the party as a graph.
</spoiler>
<spoiler summary="hint2.">
Divide the vertices into two categories according to their degrees' parity.
</spoiler>
<spoiler summary="solution">
Let's consider ...
Tutorial of Codeforces Round 810 (Div. 1)
Tutorial of Codeforces Round 810 (Div. 2)
2.
Problem Topics Good Day to you!
I've been asked to make some topic-wise list of problems I've solved. Even though I couldn't involve all problems, I've tried to involve at least "few" problems at each topic I thought up (I'm sorry if I forgot about something "easy"). I've alredy made such list once anyway I've tried to include more problems now — so here it is:
<spoiler summary="aho">
http://www.spoj.com/problems/ADAJOBS/
URI 2226 (5) //[NICE][NUMBERS][DP]
http://www.spoj.com/problems/SUB_PROB/en/
http://codeforces.me/contest/696/problem/D 8
http://www.spoj.com/problems/AHOCUR/ 5 //Aho-Corassic + DP
https://www.codechef.com/problems/LYRC (5) //Sample aho-brute-force
http://codeforces.me/problemset/problem/346/B //Proposed by [user:bradyawn,2019-08-03]
</spoiler>
<spoiler summary="automat">
6861 [LA] //CYK
UVA 10679 //Suffix Automat
http://www.spoj.com/problems/STRMATCH/ //Suffix Automat — trie might do too
http://www.spoj.com/problems/NSUBST...
http://codeforces.me/contest/873/problem/F //6 VERY NICE: SA+Histogram, https://www.urionlinejudge.com.br/judge/en/problems/view/1683 (4) //RAW
histogram
3.
Changing your rank to lower one is mainstream above 1579 <spoiler summary="Disclaimer">
All data presented is actual as of 2024/12/28, that is, before Good Bye 2024.
Also, since Ratings page only shows active users, I decided not to count any others.
I apologize to anyone I have not included.
</spoiler>
Looking at the top-10 users and Recent Actions bar right now, two things become apparent:
1. Since LGMs cannot change their rank to a higher one, more people in, say, top-100 have changed their rank to a lower one than to a higher one.
2. Codeforces-wide, more people have changed their rank to a higher one than a lower one.
So there has to be an exact cut-off point, above which the same number of people have changed their rank to either side.
I decided to do some scraping to find out exactly where it is.
Lo and behold:
<img src="https://github.com/maslinnik/cf-magic/blob/master/images/by_position.png?raw=true" alt="Rank changes (leaderboard position)">
Of the top 15k users, about tenth changed their rank to a higher ...
fetched 40k users, so the histogram might look a little different in reality,
but the trends are clear, Keep in mind that I only fetched 40k users, so the histogram might look a
little different in
4.
Codeforces Raif Round 1 Editorial [problem:1428A]
------------------
Setter: [user:bensonlzl,2020-10-17]
Prepared by: [user:errorgorn,2020-10-17]
<spoiler summary="Hint 1">
Consider when $x_1=x_2$
</spoiler>
<spoiler summary="Hint 2">
Consider when $x_1 \ne x_2$
</spoiler>
<spoiler summary="Solution">
We consider 2 cases.
The first is that the starting and ending point lie on an axis-aligned line. In this case, we simply pull the box in 1 direction, and the time needed is the distance between the 2 points as we need 1 second to decrease the distance by 1.
The second is that they do not lie on any axis-aligned line. Wabbit can pull the box horizontally (left or right depends on the relative values of $x_1$ and $x_2$) for $|x_1-x_2|$ seconds, take 2 seconds to move either above or below the box, then take another $|y_1-y_2|$ seconds to move the box to $(x_2,y_2)$.
</spoiler>
<spoiler summary="Code (C++)">
```c++
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::...
For a fixed $r$, let us graph $f(l,r)$ in a histogram with $l$ as the, graph $f(l,r)$ in a histogram with $l$ as the $x$-axis. We notice that this
histogram is non, Above is the histogram for $11101011$ when $r=7$., And this is the histogram for $11101011$ when $r=8$., The area under this histogram is the sum of all $f(l,r)$ for a fixed $r$.
Consider what happens to, When adding a new segment of $k$ $1$s, we essentially fill up the bottom $k$
rows of thehistogram
Tutorial of Codeforces Raif Round 1 (Div. 1 + Div. 2)
5.
Codeforces Round 887 (Div 1, Div 2) Tutorial We hope you enjoyed these problems :) This contest has been in the works for almost a year.
<spoiler summary = "About the Authors">
This round was mostly made possible by problemsetters from the [CerealCodes](https://www.cerealcodes.org/) initiative!
CerealCodes is an organization based in the United States dedicated to running high quality competitive programming contests. You can check out our previous contest [here](https://codeforces.me/gym/103886).
</spoiler>
**UPD: D1D Editorial have been updated**
**UPD 2: D1D Editorial now has images by [user:EmeraldBlock,2023-08-01]. As an apology gift for being so slow, the image generator is programmatic and available [here](https://artofproblemsolving.com/texer/codeforces).**
#### [problem:1853A]
Problem Credits: [user:buffering,2023-06-02]
Analysis: [user:buffering,2023-06-02]
<spoiler summary="Hint 1">
To make $a$ not sorted, we just need to pick one index $i$ so $a_i > a_{i + 1}$. How do we do this?
</spoiler...
should be rearrangeable into horizontal segments covering this histogram., the minimum number of boulder throws, represent the health values with a
histogram, where the, To find the minimum number of boulder throws, represent the health values with a
histogram, where
Tutorial of Codeforces Round 887 (Div. 1)
Tutorial of Codeforces Round 887 (Div. 2)
6.
Presenting TLE: the best Codeforces bot for Discord I would like to present to you an open-source competitive programming (primarily codeforces) discord bot written in python by [user:meooow,2019-08-05], [user:algmyr,2019-08-05], [user:Narut,2019-08-05], [user:Rahul,2019-08-05], [user:pajenegod,2019-08-05], [user:aryaman,2019-08-05], [user:keima915,2019-08-05], [user:chilli,2019-08-05], [user:c1729,2019-08-05], [user:cfalas,2019-08-05] and [user:mblazev,2019-08-05]. Source code is avaliable on [github](https://github.com/cheran-senthil/TLE). If you would like to try the bot without having to set it up yourself, enter this server: [discord.gg/2CJ6qvY](https://discord.gg/2CJ6qvY). The bot is still work in progress, but it is already 4 months old so it can already do quite a few cool things. Here is a showcase of a subset of its features:
- It can plot rating distribution of either active or all codeforces users, in either normal or log scale, who have competed at least n times. For example, `;plot cfdistrib normal active 5` gives:
<...
- It can plot a histogram of problems solved by a user, color-coded by
submission type. For example, /607693345388494869/plot.png) - It can plot a histogram of problems solved by
a user, color
7.
Codeforces Round #274: editorial I am happy to present you author's ideas of solutions.
Editorial of the first five problem is authored by — [user:HolkinPV,2014-10-18] and [user:gridnevvvit,2014-10-18],
editorial for the last two problems is written by me.
### [problem:479A]
In this task you have to consider several cases and choose the best one:
~~~~
int ans = a + b + c;
ans = max(ans, (a + b) * c);
ans = max(ans, a * (b + c));
ans = max(ans, a * b * c);
cout << ans << endl;
~~~~
### [problem:479B]
The task is solved greedily. In each iteration, move the cube from the tallest tower to the shortest one. To do this, each time find the position of minimum and maximum in the array of heights (in linear time).
### [problem:479C], [problem:480A]
The solution is again greedy. Sort the exams by increasing $a_i$, breaking ties by increasing $b_i$. Let’s consider exams in this order and try to take the exams as early as possible.
Take the first exams in this order on the early day ($b_1...
columns, pointing from the row $r$ upwards and downwards. Lets call the first
histogram “upper”, the, first histogram “upper”, the second one — “lower”. Now consider all events
inside the sub, histograms: there is a square with side length $k$ if (minimum on the interval
in the upperhistogram
Tutorial of Codeforces Round 274 (Div. 2)
Tutorial of Codeforces Round 274 (Div. 1)
8.
A WhatsApp Bot for Codeforces Analytics, Visualizations, and More Hello Codeforces community,
------------------
I wanted to share a useful WhatsApp-based AI assistant that might help with our competitive programming workflows. The idea is to bring essential tools directly into your chat, saving the time you'd spend switching between different websites.
One of the most interesting features is its ability to generate a "true performance" graph for any user, which visualizes your performance rating in every contest.
How to Use
------------------
Click the link to open a chat: [Whatsapp Chat Link](https://puch.ai/mcp/ycGISc7uVo)
Send the pre-filled message that appears.
The bot will then be active and you can start sending commands.
Available Tools
------------------
Here is a list of its few functionalities. You can ask for them in natural language (e.g., "plot my rating graph" or "recommend a problem for me").
###Analytics & Information
`get_codeforces_user_stats`: Fetches detailed stats for one or more users.
`recommend_problems`:...
. `get_solved_rating_histogram`: Displays a text-based histogram of solved
problem ratings, `get_solved_rating_histogram`: Displays a text-based histogram of solved
problem ratings., `plot_solved_rating_distribution`: A visual histogram of the ratings of
problems solved.
9.
Personal thoughts on learning and improvement _Recently, some people have asked for advice, so I decided to write a blog._
In this blog, I will talk about my approach to problem-solving, what I think about solving problems, how do I learn techniques, data structures and/or algorithms and others.
### Solving is guessing
From my interpretation, solving any problem is just some sort of guessing: making an educated guess of the solution, validating, and repeating until solved. You can speed up the "guessing procedure" by simplifiying the problem to a certain degree by, for example, not considering obviously wrong solutions.
### Abstraction and Decomposition
Usually, as soon as I finish reading a problem, I try to simplify it as much as possible. For example, sorting arrays, removing elements, handling simple cases, doing greedy decisions whenever can be done, rearranging formulas to more familiar ones, or decomposing the problems into several independent problems. You might even have to solve a harder problem, just becaus...
10.
2025 ICPC Asia Manila Regional (Gym) Editorial [problem:106262A]
<spoiler summary="Hint">
There is only one way for the leftmost piece and the rightmost piece to refer to the same object.
</spoiler>
<spoiler summary="Solution">
If $n=0$, then Alice and Bob will not fight. Since they eat $2$ pieces at a time, that means $n=2, 4, 6, 8, 10, ...$ (i.e. the even numbers) will also have them not fight.
If $n=1$, then Alice and Bob will fight over that once piece. Since they eat $2$ pieces at a time, that means $n=3, 5, 7, 9, 11, ...$ (i.e. the odd numbers) will have them fight. Since an equal number of pieces are eaten from the left and the right, we know it is the center piece that remains (when $0$-indexed, this is at index $\lfloor n/2 \rfloor$).
So, the problem is just a parity check.
</spoiler>
[problem:106262B]
<spoiler summary="Hint">
For some letter, how many times does this letter occur in the substring of $t$ that begins at position $i$ and has some length $\mathrm{len}$?
You can answer this in $O(1...
do since $t$ is periodic and repeats itself every $k^2$ letters) so building a
histogram for all, repeats itself every $k^2$ letters) so building a histogram for all letters in
some segment can be, segment. The histogram for a segment can be lazily computed from its lazy flag
in $O(k)$, as
Tutorial of 2025 ICPC Asia Manila Regional
11.
Codeforces round #435 editorial [problem:862A]
One can see that in the final set all the elements less than $x$ should exist, $x$ shouldn't exist and any element greater than $x$ doesn't matter, so we will count the number of elements less than $x$ that don't exist in the initial set and add this to the answer, If $x$ exists we'll add 1 to the answer because $x$ should be removed .
Time complexity : $O(n+x)$ .
Solution link (me) : https://pastebin.com/ALfcu8Ab .
Solution link ([user:mahmoudbadawy,2017-09-17]) : https://pastebin.com/yXLkmA5F .
[problem:862B]
The tree itself is bipartite so we can run a dfs to partition the tree into the 2 sets (called bicoloring), We can't add an edge between any 2 nodes in the same set and we can add an edge between every 2 nodes in different sets, so let the number of nodes in the left set be $l$ and the number of nodes in the right set be $r$, The maximum number of edges that can exist is $l*r$, but $n-1$ edges already exist so the maximum number of edges to be ad...
it were big, It would be in our set, So we can use this observation by making
a newhistogram with, $(\min\limits_{i=l}^{r-1} lcp_{i})*(r-l+1)$, If we have a histogram where the
$i^{th}$ column has, histogram where the $i^{th}$ column has height $lcp_i$, The the size of the
largest rectangle that fits
Tutorial of Codeforces Round 435 (Div. 2)
12.
Contest imbalance metrics # The origins of the idea
So, I participated in [contest:2210] recently and solved ABC1, and when I moved on to C2 I thought to myself "wow, that's a big difficulty jump!"
# The process
After the contest was over, I also thought about whether there is a way to put a number to this, and after a bit of thinking, I came up with the following process:
- Take the solve counts of each problem (the green numbers at the bottom of the Standings page). Call it $\mathrm{solves}$. This is used as an estimation for how easy the question was.
- Say that there are $n$ problems. Define the array $\mathrm{ratios}\left[i\right] = \frac{1+\mathrm{solves}\left[i\right]}{1+\mathrm{solves}\left[i+1\right]}$. (The $1+$ part is to prevent division by zero.)
- The imbalance is calculated as $\mathrm{stdev}\left(\ln\left(\mathrm{ratios}\right)\right)$.
So I decided to test this method on some recent contests. After playing around, I decided that this function was good to use and then I wanted to make...
Here's a histogram showing the distribution:
 participated in the last 6 months and 2) participated in at least 6 contests. The second condition is to ensure that the user's rating is stabilized.
Here is the chart (n = 89352):
[clearer version](https://i.imgur.com/VZUMJO0.png)
And here are some previous years' histograms:
[2023](https://codeforces.me/blog/entry/116571) note: uses >= 5 contest participations instead of >= 6 participations.
[2021](https://codeforces.me/blog/entry/71260) note: the author of this post wrote the script that creates very nice histograms so credit to him.
Some interesting facts:
The median Codeforces rating is 1143. The mean rounded to the nearest integer is 1205. The standard deviation is 378 rounded down to the nearest ...
Hello everyone, I have updated the rating distribution histogram for this year
and I have, I have updated the rating distribution histogram for this year and I have
created rating
14.
Problem D of Beta Round 94 <div>Today's contest had some pretty interesting problems; I particularly liked <a href="http://codeforces.me/contest/128/problem/C">Problem C</a> and <a href="http://codeforces.me/contest/128/problem/D">Problem D</a>. I'm going to describe my solution to D which I think is quite nice (and results in simple code). I don't doubt that there are even easier solutions to the problem, so please enlighten me if you have one :).</div><br /><div><h3>Impossibility</h3><div>Let us denote the sequence by $a_1, \ldots, a_n$ and assume it has been sorted already. We can note immediately that there are some easy cases we can rule out. If $n$ is odd, by a parity argument it is impossible. Moreover, let $m = a_n - a_1$, i.e. the range of the values. If $m = 0$ it is impossible since $n \ge 3$, and if $m > n/2$ it is impossible since we cannot get from $a_1$ to $a_n$ and back going around the circle. Now that these cases are out of the way we move on to the actual algorithm.</div><div><br /></div>...
easier to work with, i.e. a histogram. As such, we define $c_i$ to be the
number of values $a_j$ with, of checking whether or not the histogram can produce a valid sequence. To do
so, first place a $0
Tutorial of Codeforces Beta Round 94 (Div. 2 Only)
15.
SPOJ NSUBSTR Editorial In the [NSUBSTR](https://www.spoj.com/problems/NSUBSTR/) problem on SPOJ, we are given a string $s$ of length $n$, and for every $k = 1$ to $n$, we are asked to find the maximum number of times any substring of length $k$ appears in $s$ (including overlapping occurrences).
---
### 1. Rephrasing the Problem
We need to compute, for each possible substring length $k$, the highest frequency among all substrings of length $k$. For example, if $s = "ababab"$:
* $k=1$: substrings are {"a", "b"}, frequencies {3,3} → answer 3.
* $k=2$: substrings are {"ab", "ba"}, frequencies {3,2} → answer 3.
* etc.
A brute-force sliding-window plus hashing approach would be $O(n^2)$ or worse, which is too slow for $n$ up to $10^5$.
---
### 2. Key Insight: Suffix Array + LCP
We transform the problem into counting identical substrings by sorting all suffixes and using their common prefixes.
1. **Suffix Array**: an array $sa$ of length $n$ that lists the starting positions of all suf...
Frequencies Let’s imagine the $lcp$ array as heights of bars in a histogram of
size $n-1$. For each index, By reducing the substring-frequency problem to histogram spans over the LCP
array, we elegantly, Let’s imagine the $lcp$ array as heights of bars in a histogram of size $n-1$.
For each index $i$:
16.
I built a better CPH — and a better Codeforces while I was at it (FREE) **TL;DR -** CPH and Competitive Companion already parse samples and submit for you. CPOS does that too — but that's the boring part. The point is everything *around* it: a **browser companion** that turns the Codeforces page itself into an IDE (write and run your solution right there, plus rating-change predictions, deep profile analytics, head-to-head compare, a focus mode, and a cleaner UI), a **VS Code extension** that — unlike CPH — also renders the problem statement next to your code, and a **terminal app** that actually tells you what to solve next and how to reach your next rating. Free, open-source, MIT, and 100% local — no accounts, no servers, no tracking.
- **Source (MIT):** [github.com/Soham109/cpos](https://github.com/Soham109/cpos)
- **Browser companion (the good part):** [Chrome / Edge / Brave](https://chromewebstore.google.com/detail/gjnbapmjonegeeamdeahcoojgokeogmm) (Firefox source install in the repo)
- **VS Code extension:** [Marketplace]...
17.
Complexity of Maximum aera of histogram Can anyone tell me that what is the complexity of this code.
Problem Name: Maximum aera of histogram
Question Link: https://leetcode.com/problems/largest-rectangle-in-histogram/
~~~~~
def MAH(self,arr: List):
n=len(arr)
stackl=[]
left=[]
stackr=[]
right=[]
width=[]
for i in range(0,n):
while stackl and stackl[-1][0]>=arr[i]:
stackl.pop()
if len(stackl)==0:
left.append(-1)
else:
left.append(stackl[-1][1])
stackl.append([arr[i],i])
for i in range(n-1,-1,-1):
while stackr and stackr[-1][0]>=arr[i]:
stackr.pop()
if len(stackr)==0:
right.appen...
Complexity of Maximum aera of histogram, histogram Question Link: https://leetcode.com/problems/largest-rectangle-in-
histogram/
18.
segment tree problem. Can anyone please give me hints,how to solve this problem.
1083 — Histogram
PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 64 MB
A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3 measured in units where the width of the rectangles is 1.
Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.
Input
Input starts with an integer T (≤ 20), denoting the number of test cases.
Each case contains a line with a...
area of the largest rectangle in a histogram that is aligned at the common
base line, too. The, 1083 — Histogram PDF (English) Statistics Forum Time Limit: 2 second(s) Memory
Limit, A histogram is a polygon composed of a sequence of rectangles aligned at a
common base line. The, Can anyone please give me hints,how to solve this problem. 1083 — Histogram PDF
19.
Were the pretest good enough? Drug-free treatment for depression ) Every time when a dispute arises if the pretest were just bad or the worst in the history, I wondered what is a typical part of submissions failed on full tests.
I ran [my script ](https://github.com/NataIss/codeforces) to calculate this value for Codeforces rounds. The value is based on 895 Div.1 and Div.2 rounds which were held since 2012. The histogram for 4846 tasks is shown below
[cut]
_._
Let's draw a boxplot for this data
But it is really more interesting to look at distribution of failed submissions by task rating
The same data in the number format
If you still feel angry, guilty or depressed about a failed submission, I could recommend a cool book for CP guys ...
and Div.2 rounds which were held since 2012. The histogram for 4846 tasks is
shown below
20.
Some standard problems of stack and queue, with the solution link of my github repository. #### Stack & Queue
1. [G_Next Greater Element ](https://practice.geeksforgeeks.org/problems/next-larger-element-1587115620/1) [_Solution_](https://github.com/Jawed-byte/Striver-s-SDE-sheet/blob/main/G_Next%20Greater%20Element.cpp)
2. [I_Nearest Smaller Element](https://www.interviewbit.com/problems/nearest-smaller-element/) [_Solution_](https://github.com/Jawed-byte/Striver-s-SDE-sheet/blob/main/I_Nearest%20Smaller%20Element.cpp)
3. [Nearest Smaller to right](https://practice.geeksforgeeks.org/problems/fab3dbbdce746976ba35c7b9b24afde40eae5a04/1/) [_Solution_](https://github.com/Jawed-byte/Striver-s-SDE-sheet/blob/main/G_Help%20classmates.cpp)
4. **[G_Stock span problem](https://practice.geeksforgeeks.org/problems/stock-span-problem-1587115621/1/)** [_Solution_](https://github.com/Jawed-byte/Striver-s-SDE-sheet/blob/main/G_Stock%20span%20problem.cpp)
5. **[I_Largest Rectangle in Histogram](https://www.interviewbit.com/problems/largest-rectangle-in-histogram/)** [_Solution_](https...
-sheet/blob/main/G_Stock%20span%20problem.cpp) 5. **[I_Largest Rectangle in
Histogram](https, Histogram](https://www.interviewbit.com/problems/largest-rectangle-in-histogram
/)** [_Solution_
21.
Users Solutions greyed out. Unable to view Editorial or Solution. Please help :( Submissions to some old problems (without clear editorials or solutions) are greyed out. How can I know the solution to such problems in Codeforces?
The problem I am trying to learn: https://codeforces.me/gym/102760/problem/F
Words on Editorial:
"There is another, more difficult solution. If you know how to find the largest rectangle in the histogram inO(N) using a stack, then you may realize that you can actually apply the exact same strategy to find the largest square. The proof is left to the reader for exercise."
And my solution
~~~~~
n = int(input())
arr = list(map(int, input().split()))
def solve(heights):
maxside = 0
pstack, hstack = [], []
currarea, maxside = 0, 0
heights.append(0)
for i in range(len(heights)):
prevwidth = int(1e9)
while hstack != [] and hstack[-1] > heights[i]: # -_
prevwidth = pstack[-1]
width = i - pstack.pop()
height = hstack.pop()
if width =...
largest rectangle in the histogram inO(N) using a stack, then you may realize
that you can actually apply, . If you know how to find the largest rectangle in the histogram inO(N) using a
stack, then you may
22.
Feature request: Player rating histogram <p>In the player profile it would be very good to have the rating histogram just like the one on the Topcoder.<br><br>Because of the way the rating system works on Topcoder, you can see a small bump just before the division change. Is there a bump on Codeforces as well? :)<br><br>I also have a feeling that the programmers on Codeforces are stronger on average. Such a histogram would be a good indication of that.<br></p>
Feature request: Player rating histogram,
In the player profile it would be very good to have the rating histogram just
like the one on
, I also have a feeling that the programmers on Codeforces are stronger on
average. Such ahistogram
23.
Some nice questions for beginners learning new stuffs (will be adding more in time) _Although I'm too a beginner but I try to learn new things everyday, so here are the questions on DS which beginners like me find hard but are too easy if learned the DS nicely._
## Arrays
| Index | Problem | Prerequisite |
| --- | --- | --- |
| 1 | [Maximum circular subarray sum](https://practice.geeksforgeeks.org/problems/max-circular-subarray-sum/0) | Kadane's Algorithm |
| 2 | [Find subarray with given sum](https://practice.geeksforgeeks.org/problems/subarray-with-given-sum/0) | Hashing |
| 3 | [Equilibrium index of an array](https://practice.geeksforgeeks.org/problems/equilibrium-point/0) | None |
| 4 | [Maximum Sum Increasing Subsequence](https://practice.geeksforgeeks.org/problems/maximum-sum-increasing-subsequence/0) | Simple DP |
| 5 | [K-Concatenation](https://www.codechef.com/problems/KCON) | Kadane's Algorithm |
| 6 | [Convert array into Zig-Zag fashion](https://practice.geeksforgeeks.org/problems/convert-array-into-zig-zag-fashion/0) | None |
| 7 | [Find...
| [Largest Rectangle in Histogram
](https://leetcode.com/problems/largest-rectangle-in-histogram/) | None, Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/) |
None| | 2 | [Stock Span
24.
AtCoder Analytics — a Chrome extension for AtCoder profiles Hi everyone,
I just published AtCoder Analytics, a Chrome extension that adds extra stats to AtCoder user profile pages.
I started this because I noticed another AtCoder-related extension I used stopped working (likely due to site/API changes), so I decided to build a lightweight alternative and publish it.
Features
- Solved-by-difficulty histogram (estimated difficulty)
- Solved breakdown by contest series (ABC/ARC/AGC/AHC/etc.)
- Unsolved list (with links)
Chrome Web Store link: https://chromewebstore.google.com/detail/bmfjngielhkffoekjpdgpedpmelhabhm?utm_source=item-share-cb
Feedback and bug reports are welcome.
and publish it. Features - Solved-by-difficulty histogram (estimated
difficulty) - Solved, - Solved-by-difficulty histogram (estimated difficulty) - Solved breakdown by
contest series (ABC
25.
Codeforces API I would like to know if there is any way we can get the rating/difficulty of the problems using Codeforces API? Obviously we can use user status to get to the problems a particular user solved. But I would like that to the difficulty of each problem so that I can actually produce a histogram.
I think the API has not been updated since the new edition of rating/difficulty in problemset. It would be awesome if you can point me to the right direction!
would like that to the difficulty of each problem so that I can actually
produce ahistogram.
26.
Histogram Is there any good explanation for the idea behind finding max area sub-rectangle in a histogram problem? And some tasks involving the same idea. It seems to be used in much harder problems as a sub-problem and i am having hard time about it.
Histogram, Is there any good explanation for the idea behind finding max area
sub-rectangle in ahistogram
27.
(SEGMENT TREE) SPOJ PROBLEM: Largest Rectangle in a Histogram Problem: [Largest Rectangle in a Histogram](http://www.spoj.com/problems/HISTOGRA/)
Verdict: WA
can not get the problem
please help someone
code: [CODE](http://pastebin.com/XBi6jHs0)
(SEGMENT TREE) SPOJ PROBLEM: Largest Rectangle in a Histogram, Problem: [Largest Rectangle in a Histogram
](http://www.spoj.com/problems/HISTOGRA/)
28.
How to prove that answer cannot be less than minimum of two colors in div2 — D 609 https://codeforces.me/contest/1269/problem/D
In editorial it is given that answer is min(black colors , white colors) .But why it cannot be less than that ? Also what is the problem with algorithm when histogram is not given in sorted order (i.e decreasing height) ?
Also one request to editorial writers . You guys are doing great job,thanks, but if you write more simple explanation it will help beginners and people in general a lot ! (I am not saying that editorial of this contest is not good).
algorithm when histogram is not given in sorted order (i.e decreasing height)
? Also one request to, than that ? Also what is the problem with algorithm when histogram is not
given in sorted order
29.
Histogram for number of paths on an acyclic undirected graph. Hello everyone. I need your help. I have been trying to solve [a problem from code chef](https://www.codechef.com/problems/CUTTREE), and I wonder whether, it is possible to count number of paths with length i for all i in [1..n] on an acyclic undirected graph in _O(n*log(n))_ time complexity or not. Here, by length of a path I mean the number of nodes the path contains.
Histogram for number of paths on an acyclic undirected graph.
30.
WA in SPOJ Histogram problem Solving [HISTOGRA](http://www.spoj.com/problems/HISTOGRA/) problem on Spoj. Getting WA with [this](https://gist.github.com/aalexand/8451159) O(ln(N)*N) union-find-based solution. Can't find the bug myself, maybe somebody's fresh eyes can help. Much appreciated.
WA in SPOJ Histogram problem
31.
largest rectangle area in histogram hello sir/mam,
yesterday i started solving the following problem using stack..
https://www.hackerrank.com/challenges/largest-rectangle
this is my solution
http://ideone.com/SomZF4
i think my code is entirely correct,,,but dont know where it is going wrong.....answer has to be 9 for the sample input....but i am getting it as 5..
could any on pls say error in my code..
largest rectangle area in histogram
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/10/2026 06:43:40 (g2).
Desktop version, switch to mobile version.
Supported by
