demoralizer and I were discussing our 2+ years old code and I thought it'd be a good motivation for newbies and pupil who write cancer currently.

Please contibute by sharing code(in spoiler tag) or links to your of your big brain moments from back when you were low rated.

My biggest big brain moment was when I assumed inbuilt std::sort must be slower, so copied merge sort from gfg. https://www.codechef.com/viewsolution/23270721

Hi , I was solving this problem https://www.codechef.com/problems/PRMQ and used Persistent Segment Tree for this.

However, one of my implementation using vector to store versions was giving error :

The implementation is:

Node *root = new Node(NULL, NULL);
st.build(root, 0, n - 1);
vector<Node *> version = {root};
// few lines in between
Node *newRoot = new Node(NULL, NULL);
st.update(newRoot, version.back(), 0, n - 1, y[i].ff, y[i].ss);
version.push_back(newRoot);

Another error free implementation was :

Node *version[20 * N];
Node *root = new Node(NULL, NULL);
st.build(root, 0, n - 1);
version[0] = root;
// few lines in between
id++;
version[id] = new Node(NULL, NULL);
st.update(version[id], version[id - 1], 0, n - 1, y[i].ff, y[i].ss);

Error :

Indirect leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x7f706c4aa947 in operator new(unsigned long) (/lib/x86_64-linux-gnu/libasan.so.5+0x10f947)
    #1 0x563fd4144eff in PST::build(Node*, long long, long long) /home/pritish/Competitive/B.cpp:43
    #2 0x563fd4140853 in Onigiri() /home/pritish/Competitive/B.cpp:106
    #3 0x563fd4142a6c in main /home/pritish/Competitive/B.cpp:150
    #4 0x7f706b6670b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)

SUMMARY: AddressSanitizer: 528 byte(s) leaked in 22 allocation(s).

Full Error Data : https://pastebin.com/S8QWp0bF
Full No-Error Code : https://www.codechef.com/viewsolution/47320824
Full Error Code : https://www.codechef.com/viewsolution/47320876

Build Flags : g++ -std=c++17 -Wshadow -Wextra -Wall -DZoro ${file} -ggdb3 -fsanitize=address,undefined -D_GLIBCXX_DEBUG -D_GLIBCXX_ASSERTIONS

Although it didn't affect the final verdict of the solution, I want to know if it's something serious I should be concerned about for future contests?

Reporting this issue here on Codeforces again because last time the issues were recognized and resolved effectively through this blog.

Last Code-Drift contest (linklist+stack+queue) which was organized had two major issues.

First is the hint system which when used will deduct some % from max achievable score for each problem. One can simply make an alt account and see the 1st hint. This could not be exploited that much because only 1 hint was available for participants who were active in the contest and it was very vague hint.

But the main issue was when I realized that everyone can actually see the setter solution for every problem by doing one trick.
After not being able to solve 3rd problem , I decided to press "End test" button out of frustration. Around 1 hour later I came back with some fresh ideas in mind and when I clicked the contest it opened in practice mode and there I was able to see complete solution before contest ended (notice time on my top-bar). This can be heavily exploited using alts.

Second issue was the time for revealing the 2 problems on 2nd day was 8pm. But when I logged in at around 7:15pm the problems were visible. I reported that problem through the portal (notice time).

The Code-drift before this one (2-pointer) had no such loopholes except delayed revealing of problems in 2nd day. But these new "hint" features can be exploited easily. This contest has cash prize and keeping hints may help cheaters. So I hope interviewbit authorities fix it.

I couldn't find any discussion forum of interviewbit where I could report this, so I am putting it here. If any admin/official of interviewbit is active here, then you can look at it.

The rank 1 has submission time of 5 sec,10 sec,8 sec and 6 sec.

This CodeDrift contest was a 2 day long contest and 2 problems were revealed on 1st day and 2 problems were revealed on 2nd day. But the strange this about this is , the time penalty for each problem is calculated from the point when you click on the problem link and actually view the problem. But this kind of system is very vulnerable to cheating, I mean nothing is stopping me from making a fake account and submitting all solutions at the last minute to get the top position on ranklist. I had managed to solve all problems and now I can simply retake the test with another id and submit the solutions to get a good rank.

Last night taran_1407 ,gupta_samarth and neeraj_joshi were in top 3 I guess. And today, another person (clearly a cheater) is on rank 1 and two more people have also entered the top 5 list.

This doesn't make any sense at all. Why calculate penalty time from the point when you click the problem link?

Note: This is not the first contest where I have seen this system. Few months back they had conducted an inter-IIIT contest, where this system was also followed. It was 8 hours long contest maybe , but you had 2 hours submission time from the point you enter the contest. My rank had dropped from top-5 (when I finished my test) to top-30 (by the time the test period completed). What if 10 more people had cheated in this way by creating fake IDs?

EDIT: Post contest ranklist be like :

Now I hope they don't use this stupid system for contests.

EDIT: They changed and fixed the ranklist :)

These problems were found in gym. I don't have access to other's solutions and there is no editorial for these problems. So can anyone please help ?

K. Parabolic sorting : https://mirror.codeforces.com/gym/102780/problem/K
F. A word game : https://mirror.codeforces.com/gym/102780/problem/F

For the Grid Paths problem, if I use #define int long long and submit the solution, it gets accepted verdict, but using int gives time limit exceeded. How is this possible?

Link to accepted with long long : https://cses.fi/paste/6c2a837ed715717813be49/
Link to TLE with int : https://cses.fi/paste/1298e773dc80a66513be46/

Original problem link: https://www.codechef.com/CRK32020/problems/KEVIN

Kevin has an array a consisting of $$$N$$$ elements. He defines an operation $$$f$$$ as maximum of absolute difference between the adjacent elements of the array. If $$$0 \leq N \leq 1$$$ then $$$f$$$ is 0. He wants to minimize the value of $$$f$$$ for the array $$$A$$$. For this, he is allowed to replace at most $$$K$$$ elements of the array with any integer. Help Kevin to find the minimum value of $$$f$$$ for the array.

$$$1 \leq K \leq N \leq 2000$$$
$$$ -1e9 ≤ A[i] ≤ 1e9 $$$

The solutions (https://www.codechef.com/viewsolution/39101909) to the problem are using DP but I'm not able to understand the state transitions. Can anyone help please?

You are given a binary string (consisting of 0,1) and you can rotate the string in any order. Basically if the string is s1s2s3...s(n-1)s(n) , you can make it s2s3s4,,,s(n-1)s(n)s1 .

Print out the rotation which has the maximum value in binary representation.

For example:
s=0110
ans= 1100

|s| <= 10^5

Can anyone suggest any approach ? I'm unable to think of any fast approach.

The doubt arises from the fact that no person in top 10 rated list currently has won(rank 1) all contests he/she participated in. And the current max rating is of tourist (3739) and not even tourist has won all contests.

So , I was wondering what if someone existed who had participated in every possible rated-contest on CF and got rank 1 in all of them. What would his/her rating be?

I know that's a totally hypothetical situation but it's kind of interesting and so I am curious. Will there ever be a point where even rank 1 will give +0 delta? And what would that rating be?

Is there any way we can calculate this? Is there any web-app or script that can tell us this?

I manually calculated it for all Global Rounds using virtual contest rating calculator and the rating changes turned out to be:

(default)1400->2045->2451->2761->2959->3137->3257->3373->3461->3539->3579->3635

Link to the problem : https://www.codechef.com/FCF32020/problems/PATHWAY
Link to the code : https://www.codechef.com/viewsolution/38865614

In this code , how can python compute factorials of (N+M) ( N+M is in the order of 10^5 ) so fast? Can anyone explain this ? How did the python interpreter optimize it ?

Guys please share your approaches for the problems you solved. How many did you guys solve?

Problem 1

There are N cities numbered from 1 to N connected by M bidirectional roads. A concert is going to be held in each city and i_th city concert costs A[i] amount. Travelling through the roads also costs some amount given.

For each city i from 1 to N : find the minimum amount a person from city i has to spend to visit a concert in any of the city and come back to own city.
It may not be guarenteed that each city is reachable from other city.

N,M<=10^5

=====================================
Problem 2

Given rooted tree of N vertices from 1 to N. Every vertex must not have same color as it's p-th ancestor. Every vertex must have either red or green color. Calculate the number of ways to color the tree.

N,p<=10^5

=====================================

Problem 3

You are going to make a necklace of N beads using K different colored beads.
There are unlimited beads of each color.
You need to find the expected value of number of distinct colors used, if every necklace is equiprobable to be made.
Two necklaces are considered same if after some rotation they are identical.
You need to find this value for each N from 1 to M, modulo 1e9+7.

K,M<=10^5

=====================================
Problem 4

Find lexicographically smallest permutation of 1 to N where there are exactly B good indices.
A good index i is one where the element at this index is greater than all it's previous elements(at indices<i).

N,B<=10^5

=====================================
Problem 5

Given an array of length N. You can change any number to anything else. Calculate the minimum number of changes needed to make the array such that every subarray of size K will have Bitwise Xor = 0.

N,K<=10000
A[i]<=2^10-1

=====================================
Problem 6

Indumati has been given an array of A ones and B zeroes.
One operation is:
-> Select any C elements from the array and delete them from the array and append their average (in irreducable fraction from) to the array.
It's guarenteed that A+B-C is multiple of C-1.
Indumati repeats this operation until only 1 number is remaining.

Your task is to calculate the number of distinct values the fraction can take, modulo 1e9+7.

A,B<=2000
2<=C<=2000

=====================================

CodeAgon is on 27th September 2020 at 20:00IST.
And I'm sure almost all Indian coders will participate in CodeAgon rather than CF Div1,Div2.

Please change the date for round #673. Otherwise many people will have to skip this round.

Please look into this, MikeMirzayanov .

The reason for asking this is :
In our college ,our ICPC coach doesn't do any "coaching" work. :P

So I was wondering if the Indian teams , which are currently performing well, have good coaches for coaching them in college?
And I could have asked this in DMs but I thought it would be better to ask everyone at once. :P

I'm especially curious about those colleges who's teams have been visiting WF consistently (like IIIT Delhi, CMI , etc).

Can you please spill the beans? ;)

Hey, I have noticed that for the past few days I don't receive notification for new comments for blogs that I've written.
The notifications come to my email but not to the bell icon on codeforces.

You can see that I got mail nilesh8757 and SuperJ6 have commented on my blog but I don't see it in 'recent notifications' .
Is there any setting for this? Did I disable it by mistake? Is everyone facing this issue?

MikeMirzayanov , can you please look into this if it's a bug?

It was asked to my friend in google coding challenge and I'm unable to think of any approach.
Can anyone help?

Given a weighted undirected graph G that contains N nodes and M edges.
Each edge has a weight w associated with it.

Answer Q queries:
- x y W : Find if there exists a path between node x and node y such that the maximum weight on that path doesn't exceed W. If it exists print 1 or else print 0.

1<=T<=5
1<=N,M,Q,W,w<=10^5
1<=x,y<=N

I know it's slightly off-topic but I couldn't find any answers on other sites.
I was actually doing a project in which I think using a trie will be really helpful for processing the queries.

But if I keep remaking the trie everytime from scratch when I load the app then it's gonna be slow. So is there anyway I can store the contents of a trie ( wrapped in a class) into a file and load it directly everytime I need it?

I have done something like this using classes before , but we know trie needs dynamic memory allocation. So will it work if I wrap it in a class and put it in a file?
Also can anyone who has development experience tell how do people generally handle these query-based data-structures in apps? Do they rebuild it on the database everytime?

So, basically this problem can be considered as a simpler version of https://mirror.codeforces.com/blog/entry/74836 . I was wondering what can be the approach if we fix the size of the subset.

Given an array of size N , find the maximum bitwise or of elements in a subset of size K.

What can be the best(time complexity wise) possible approach for this problem apart from this ? Can anyone please help?

UPD: I had initially written Xor everywhere instead of Or. Sorry.

One of my friends noticed a strange behaviour of .size() method.

Link to WA submission : https://mirror.codeforces.com/contest/1307/submission/88824759
Link to AC submission : https://mirror.codeforces.com/contest/1307/submission/88824749

The bug is in the line
LL x=a[i].size()*(a[i].size()-1)/2;

In C++17 , I guess there is overflow in that expression.
But in C++17(64) , it works fine.

So does that mean the .size() operator can hold larger numbers in 64bit version?
And also what other methods show this kind of varying behaviour when the compiler changes from 32bit to 64bit??
Can anyone explain this please??

Hi,
I had made this problem( https://www.codechef.com/FTCF2020/problems/TRADE2 ) and the approach that I used to solve was make a segment tree over a multiset table of size 10^5. In that approach , table[i] would denote prices of phones with speed i. Segment tree would work on the .begin() values of the multiset tables.

I wanted to know if there's any alternate approach to this problem. Thanks in advance!

Hi,
Somethings related to Competitive Programming (well, in a broader sense , Data Structures and Algorithms) have been on mind lately.

I know some people who haven't done Competitive Programming and also have very less knowledge of DSA but they never needed those. Example- Some of the seniors from my college are well-placed in good companies but they never properly explored DSA.

I know that being proficient in CP is not the only way to get good placements and I also realize that being proficient in CP also does NOT guarantee good placements.

Lately, my primary motivation to keep doing CP has shifted from "getting good placements" to "it's fun and exciting".
But along with that shift of mindset, I also find it harder to suggest others to start CP (knowing that most of them are just looking for an easier way to get well paying jobs).

So, I wanted to ask you guys.
If you'd ever suggest someone to start Competitive Programming, what would be your reasons to do so? I mean how would you convince someone to start CP ?

PS: I'm sorry if this has been asked before or if you find this useless.

Hi,
I wanted to know how to make segment tree with
Lazy propagation for Range Assignment Updates (make elements in range L to R equals to update_Val) and Range Sum Queries.
I am not able to code it properly and also I couldn't find any proper tutorial for this specific set of operations.

Can anyone share the code for doing that?

Hey everyone,
After watching tmwilliamlin's livestream I was a bit interested in the CSES problemset.
I wanted to ask "Who is it for?" and is it worth it to solve the entire problemset?

I was completing A2OJ ladders (currently in 1700-1800 ladder) till now.
Should I pause that and complete the CSES problemset?

Hello everyone, This extension will modify the submit through file block in the problem page so that we can paste our code there and submit.

Of course , if you liked submitting through file then it's useless for you. It is made for those who have a habit of pasting code in the separate submit page.

Links to the extension :

• Firefox : https://addons.mozilla.org/en-US/firefox/addon/submitify/
• Chrome & Opera : https://github.com/pritish-n/Submitify

It also redirects into a new tab and you don't have to open a new page every time you submit.
Thanks for reading and hope you like it.

UPD : I added the feature that now selects the code written in the text-area on clicking the submit button, So now it's easier to delete the previously written code.

UPD : I found link to another such tool : https://mirror.codeforces.com/blog/entry/66646

This extension is a much simplified version of the tool mentioned in the above blog.

Me and my floormate(now roommate XD) had made this video in our first year of college.
We didn't know about Codeforces back then, and participated in Codechef only.

Hope you find it entertaining and relatable. :D

https://www.youtube.com/watch?v=J3z_u_kn8dM

Problem Link:https://mirror.codeforces.com/problemset/problem/442/B

I have been trying to solve it using DP, but there always seems to be precision issues even when using long double.

My submissions : https://mirror.codeforces.com/contest/442/submission/81584010

In my approach
dp[i].first = the max probabilty obtainable by choosing 1 or more friends from index i to n-1.
dp[i].second = the product of complements of probablity of all chosen friends.
dp[i].second is helping me do the transition.

Can anyone solve it using such DP without failing due to precision issues?