Infoleague Spring Round 2022 Announcement Hello Codeforces! We would like to invite you to the first (and possibly only) round of Infoleague Spring 2022, the contest starting on Wednesday, March 30th from [12:30 GMT+3](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Infoleague+Spring+2022+Official+Round&iso=20220330T123030&p1=2209&ah=4). The problems in this round have been prepared to train high school students for the upcoming Romanian National Olympiad in Informatics (ONI). **The registration period for this contest starts from [6:30 GMT+3](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Infoleague+Spring+2022+Official+Round+Registration&iso=20220330T0630&p1=2209&ah=6) on Wednesday, March 30th**. This contest has two divisions, Div 1 and Div 2. The Div 2 contest intends to mimic an ONI problemset for 9th and 10th graders, while Div 1 is mainly focused towards challenging 11th and 12th graders. Contest links: [Div1](https://codeforces.me/gym/103634), [Div2](https://codeforces.me/gym/1036...

Full text and comments »

Infoleague Autumn 2021 Round 2 Announcement Hello Codeforces! We would like to invite you to the second round of Infoleague Autumn 2021, on Saturday, November 20th at **15:30 GMT**. This contest will have two divisions, Div 1 and Div 2. In both Div 1 and Div 2 you will have to solve 3 problems, which should hopefully be sorted in increasing order of difficulty. Div 2 is recommended for specialists and below, while Div 1 is recommended mainly for experts and low CMs. Contest links: [Div 1](https://codeforces.me/contestRegistration/103423), [Div 2](https://codeforces.me/contestRegistration/103422) - Contest duration (Div 1): **4:00h** - Contest duration (Div 2): **3:00h** - Scoring distribution (Both divisions): **100-100-100** The scoring system is IOI-esque, with partial scoring. All problem statements will be available in both English and Romanian. Problemsetters: [user:Gheal,2021-11-08], [user:tibinyte,2021-11-08], [user:cadmiumky,2021-11-08] Testers: [user:andrei_boaca,2021-11-08], [user:IacobTudor,2...

Full text and comments »

Infoleague Winter 2022 Round 1 Announcement Hello Codeforces! We would like to invite you to the first official round of Infoleague Winter 2022, starting Saturday, January 8th at 14:00 GMT. This contest will have 2 divisions, each containing 3 problems, which are not necessarily sorted in increasing order of difficulty. Div 2 is recommended for low-Experts and below (i.e. <1700), while Div 1 is recommended mainly for high experts, CMs and Masters. Contest links [Div1]( https://codeforces.me/gym/103505), [Div2]( https://codeforces.me/gym/103503) Contest duration: - Div 1: 5 hours - Div 2: 3 hours Scoring distribution (for both divisions): **100-100-100** The scoring system is IOI-esque, with full feedback. All problem statements will be available in English. Problemsetters: [user:Gheal,2022-01-08], [user:tibinyte,2022-01-08], [user:cadmiumky,2021-10-31] Testers: [user:andrei_boaca,2022-01-08], [user:IacobTudor,2022-01-08], [user:RaresFelix,2022-01-08] **Upd 1:** The Div. 2 round is over! Co...

Full text and comments »

Infoleague Winter 2021 Training Round Announcement _Disclaimer: This contest is not rated_ Hello Codeforces! We would like to invite you to the training round of Infoleague Winter 2021, starting from Saturday, December 4th at **14:00 GMT**. This contest will have 8 problems, which are **not** sorted in increasing order of difficulty. They should provide an interesting challenge to everyone up to around 2300 rating. - Contest link: https://codeforces.me/contestRegistration/103449 - Contest duration: **7 days** - Scoring distribution: **100-100-100-100-100-100-100-100** The scoring system is IOI-esque, with partial feedback. All problem statements will be available in English. Problemsetters: [user:Gheal,2021-12-01], [user:tibinyte,2021-12-01], [user:cadmiumky,2021-12-01] Testers: [user:andrei_boaca,2021-12-01], [user:IacobTudor,2021-12-01], [user:RaresFelix,2021-12-01] Upd 1: Six days down, one to go! The editorial will be posted tommorrow, shortly after the end of the round. Upd 2: The contest is over, co...

Full text and comments »

Problemsetting Goal Since goals are very important in any individual's life, I decided to **set** a goal for myself. The target is to **set** 100 problems until I quit cp. Current progress: **40** | # | Date | <center>Problem</center> | <center>Contest</center> | <center>Difficulty</center> | Comments | Feedback | |----|---------------|----------------------------------------------------------------------------------------------|-----------------------------------------------------------------|-----------------------------------------------...

Full text and comments »

Infoleague Spring 2022 Round Editorial <spoiler summary="Vote your favourite problem"> <spoiler summary="Div 2"> Div 2A &mdash; The Hatchet Div 2B &mdash; Floor Or Xor Div 2C &mdash; Yet Another Constructive Problem Didn't participate, idc </spoiler> <spoiler summary="Div 1"> Div 1A &mdash; Bamboo Coloring Div 1B &mdash; Xor Or Floor Div 1C &mdash; Jump Didn't participate, idc </spoiler> </spoiler> [103633A &mdash; The Hatchet](https://codeforces.me/gym/103633/problem/A) ------------------ Author: [user:tibinyte,2022-03-30] <spoiler summary="Rate Problem"> 1700 or less 1800 1900 2000 2100 or more Didn't solve it, idk </spoiler> <spoiler summary="Solution"> ### Subtask 1 : $N \le 10^2$ This subta...

Full text and comments »

Infoleague Winter 2021 Training Round Editorial [103449A &mdash; Mountains](https://codeforces.me/gym/103449/problem/A) ------------------ Author: [user:Gheal,2021-12-01] <spoiler summary="Solution"> At the beginning of year $y$, the height of peak $i$ can be any integer $H \in [h_i + y \cdot l_i, h_i + y \cdot r_i]$. Therefore, the problem boils down to finding the maximum number of overlapping segments, where segment $i$ is $[h_i + y \cdot l_i, h_i + y \cdot r_i]$. This can be done in many ways, either via greedy, or by using difference arrays. Time complexity: $O(N log N)$ </spoiler> <spoiler summary="Code"> ``` #include <bits/stdc++.h> using namespace std; using ll = long long; const ll NMAX = 2e5+9; int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll n, y, v, l, r, peaks=0, maxpeaks=0, cnt=0; map<ll,ll> dif_array; cin>>n>>y; for(ll i=0;i<n;i++){ cin>>v>>l>>r; dif_array[v+l*y]++; dif_array[v+r*y+1]--; } for(auto it = dif_arr...

Full text and comments »

Infoleague Autumn 2021 Round 2 Division 1 Editorial [problem:103423A] ------------------ Idea and Solution: [user:Gheal,2021-11-20] <spoiler summary="Solution"> <spoiler summary="Subtask 1"> The basic naive approach would be to iterate through every subarray and naively check for each one if it is bordered. Time complexity: $O(N^3)$ </spoiler> <spoiler summary="Subtask 2"> All bordered subarrays are either constant, or begin with a $1$ and end with a $2$. The answer can be found in $O(N)$ with prefix sums. Time complexity: $O(N)$ </spoiler> <spoiler summary="Subtask 3"> Similarly to the first subtask, we'll iterate through every subarray. A subarray $[a_l,a_{l+1}, \ldots a_r]$ is bordered if $a_l \le min_{i=l}^r(a_i)$ and $ max_{i=l}^r(a_i) \le a_r$. Calculating $min_{i=l}^r$ and $max_{i=l}^r$ for every pair of indices $(l,r)$ can be solved via RMQ or via dp in $O(N^2)$. Time complexity: $O(N^2)$ </spoiler> <spoiler summary="Subtask 4"> $O(N \cdot \sqrt N)$ or inefficient $O(N log N)$ s...

Full text and comments »

Infoleague Autumn 2021 Round 2 Division 2 Editorial [problem:103422A] ------------------ Problem author : [user:Gheal,2021-11-20] <spoiler summary="Solution"> Let some sequence $b=[$ $a[i_1],a[i_2], \ldots a[i_k]$ $]$. If $b$ is constant, then $a[i_1]+1=a[i_2]+2= \ldots = a[i_k]+k$. Therefore, $b=[$ $a[i_1],a[i_1]-1, \ldots, a[i_1]-(k-1)$ $]$. Let *dp[i]* be the maximum length of a constant subarray ending in $a[i]$. We'll also need *maxdp[x]*=max( *dp[i]* for which $a[i]=x$). Let $i$ be the current position. *a[i]* can be appended to any subarray ending in **a[i]+1**. Therefore, *dp[i]=dpmax[a[i]+1]+1(. *dpmax[a[i]]* will also be updated accordingly: *dpmax[a[i]]=max(dpmax[a[i]],dp[i])*. The maximum length of any constant subarray is equal to $k=max_{i=1}^n(dp[i])$. Reconstructing a maximal constant subarray will also require *prev[i]* &mdash; the last appearance of *a[i]+1* to the ``left`` of $i$. From some position $p$ where *dp[p]* is maximal, $p$ will be replaced repeatedly by *prev[p]* $k-1$ times. This traversal ...

Full text and comments »

Infoleague Winter 2022 Round 1 Div. 2 Editorial I would like to apologize for the checker issue with problem C. I selected `std::ncmp` out of habit and forgot to change it afterwards. I would also like to apologize for taking so long to fix the issue. The model solution for div1A was also wrong, and I decided to fix that first. Nonetheless, we still hope that you enjoyed our problems in both Div. 1 and Div. 2. [103503A &mdash; Make Sum Great Again](https://codeforces.me/gym/103503/problem/A) ------------------ Author: [user:Gheal,2022-01-08] <spoiler summary="Hint 1">It is always optimal to add the smallest integer which is not already in the array.</spoiler> <spoiler summary="Hint 2">The number of operations will never exceed $\sqrt{2 \cdot s}.$</spoiler> <spoiler summary="Hint 3">Based on the first hint, the final array will be equal to $\{v_1,v_1,\ldots, v_n\} \cup [1,x]$, for some $x$.</spoiler> <spoiler summary="Hint 4">Hint 4: How can we find the value of $x$ faster than $O(\sqrt{s})$?</spoiler> <spo...

Full text and comments »