Hello Codeforces

Recently someone asked for a tutorial about using polygon to prepare problems, I couldn't find such tutorial so I decided to write one. You can find the tutorial here.

This tutorial is beginner friendly, I tried to explain every step in details and through the tutorial I have created a complete simple problem. I hope you will find this tutorial interesting and helpful. If you want READ access for the problem created in this tutorial you can write a comment with your polygon handle on this blog or simply send me a message.

You can also check some of my previously written articles about Competitive Programming at:

• Maximum Independent Set in Bipartite Graphs.

• Stress Testing.

• Game Theory.

• Monotonic Queue.

• AtCoder unofficial Editorials, (abc178 and abc179)

Hello Codeforces

I decided to share this article about stress testing after watching the last screencast made by Errichto. To be more precise when he started making stress testing to find counter-test. You can check that here. Errichto has a full video called How to test your solution in Competitive Programming, on Linux? I highly recommend you to check it, basically this article is the same but I am extending it to stress test solutions with multiple answers using a written checker, and I thought maybe you like written articles more than watching videos (some people do).

You can find the article here. I hope you will like it, please share with me your thoughts and if you use other helpful tools then you can share them in the comments below.

You can also check some of my previously written articles about Competitive Programming at:

• Maximum Independent Set in Bipartite Graphs.

• Game Theory.

• Monotonic Queue.

Before Today's round I took part in 197 rated rounds, and I was hoping to mark my 200th round by becoming a master, however my hopes failed as I became master in Today's Round <3 <3 <3

I have been doing CP since February 2015, more than 5 years. Finally today I reached master, I wanted to share this blog with you because I see a lot of times some users say I am not advancing, my rate doesn't change, I am stuck in rate... Believe me in the end everything will change, just be patient and keep believing in your self ;)

You can take a look at all ups and downs in my graph, I didn't reach this level easily, It just takes time.

Happy coding all, I hope you will reach what you want soon.

Hello Codeforces

Recently I have written tutorial talking about the Maximum Independent Set Problem in Bipartite Graphs. I have tried all my best to cover this problem, and explained some related problems: Minimum Vertex Cover (MVC), Maximum Cardinality Bipartite Matching (MCBM) and Kőnig’s Theorem. You can find the Tutorial in my website.

I am new to blog writing, so any feedback (positive and negative one) will be highly appropriated.

Merry Christmas and happy new year for you all

2019 is almost over now, I am sure you all had ups and downs this year, I spent most of the year as a Candidate master and now here I am again, back to expert :D

Through the year I have seen many posts of users setting up challenges, cheering up when they achieve it :D and getting sad and desperate when they fail :( For me I set one challenge and luckily I was able to succeed in it. My challenge was to reach +2000 rating before the start of May. I have done it in 29 April, in Codeforces Round 556 (Div. 2) it was the last rated round before my deadline :D

If you have set yourself any challenge in 2019 share it with us in the comments below, perhaps your story will inspire someone else, even if you failed in it.

Now reaching +2000 rating was a nice thing, but this time I will set myself a higher challenge, If I can't reach international master (+2300) before next year ACM regional contest ( usually held in November ) then I won't attend the regional contest, although this will be my last regional contest, and my last chance of reaching WF.

If you want to set your self any challenge for the next year, share it with us in the comments below. It would be nice by the end of 2020 to read all these stories.

Hello Codeforces

Every time I try to open a problem in the gym I get this following error message:

Is it a common problem? or this is just happening with me :\

All day I have been getting messages from 6998bharath to share with him my code for VRt Contest 2019 (marathon) problem, he even offered me money to sell him the code!!!

How can I report such thing, and how to stop him from sending me any other messages?

World finals was yesterday, and I am sure you all got excited to take part in 2020 WF, so What are you waiting for? Start training hard :D

I would like to invite you all to take part in NCD 2019 qualification contest, NCD ( National Center of Distinguished students) is a high school in Syria, the best students in Syria study in NCD and they receive special programs. Every year top teams from NCD compete with university students in ACM contests and achieve great results.

The onsite contest will be held tomorrow you can check your timezone Apr/06/2019 18:30 (Moscow time), however the contest might be delayed for some time due to some delays from onsite event, you will be given 10-13 problems to be solved in 5 hours, the contest will be held on Codeforces gym, registration will be open 6 hours before the start of the contest.

The contest was prepared and tested by me Hasan, EleCursity, NeuTronic, massoud8032000, Hash, Geo_Ghaffar and others.

We hope you find the problems interesting, see you on the standings page :D

Due to some unexpected events, the round was delayed 9 hours after the system testing of global round.

UPD the contest is over thank you for your participation, please share with us your feedback, and if you have any questions leave them in the comments below, and we will do our best to answer them.

Finally, congratiolations for TooNewbie who solved all the problems :D

When I try to open A2oj I am getting this message:

Your connection is not secure

The owner of a2oj.com has configured their website improperly. To protect your information from being stolen, Firefox has not connected to this website.

Is there is anyone else facing this problem??? or it's just me :\

I am trying to add a solution for a problem on polygon, however i keep getting:

Can't compile: solution.cpp

solution.cpp(1) : fatal error C1083: Cannot open include file: 'bits/stdc++.h': No such file or directory

same thing happened when i tried to add the validator, but after trying to add the validator for nearly 10 times it was successfully added...

Am I the only one having this problem??? or is there something wrong???

Thanks in advance...

Today I found the following bug in Codeforces, I was "by mistake" trying to register at Codeforces Round #383 (Div. 1) when I got the following message:

Now, how can I take part in Codeforces rounds when my rating becomes 10, 000 ??? I think that this bug should be fixed ASAP !!!

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

Hello Codeforces, my name is C137 and as I said before, I will continue writing regularly in this blog:

It has been a long time since i wrote something new, because I was busy with some stuff, however I will try to post at least one topic every 10-15 days, and i am gonna select a problem that i really found it useful and interesting, and then i will talk about the way i solved this problem, with long editorial and analysis, by this way of sharing my thoughts i hope that grey, green and cyan contestants will benefit from it and learn something new, also i am hoping that top rated contestants will also add their notes to my solution, and suggest some more optimized code.

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

Today, I choose to you this graph problem, I hope you will like it:

P.S: if you are familiar with the basics of graph theory and the BFS algorithm, then i strongly recommend you to try with this problem at least for one hour before reading this blog:

Before I start, I would like to thank NourAlhadi and Samo.A.R for solving this problem after reading this blog, and adding his notes and suggestions to make it even more clear.

problem name: long journey

Link: here

type: Graphs

Difficulty level: Average

Short Description:

Given an un-directed un-weighted connected graph, two friends A and B stand in a starting node st, A wants to go to node en_a using the shortest possible path, similar B wants to go to node en_b using the shortest possible path, but they both want to share the maximum number of edges, your task is to calculate the maximum number of edges they will share.

Example:

see the graph in the picture, let st be node 1, en_a be node 4 and en_b be node 6.

the optimal path for A will be 1 - 2 - 3 - 4

the optimal path for B will be 1 - 2 - 3 - 5 - 6

sharing two edges, from 1 to 2, and from 2 to 3.

Problem Analysis:

As a start we will make the following assuming, solve the problem based on it, then prove it's true:

the optimal path for A will be something like:

st - x₁ - x₂ - ...... - x_len - a₁ - a₂ - ..... - en_a

and the optimal path for B will be something like:

st - x₁ - x₂ - ...... - x_len - b₁ - b₂ - ..... - en_b

where nodes a₁, a₂, ...., en_a, b₁, b₂, ...., en_b are all distinct

that means, they will both start at node st, travel together till node x_len then separate, and never meet again.

but why this is true??? let's look at the two examples below:

in figure 1, the two friends should travel from node a to node e, there are two possible paths:

• a - b - e
• a - c - d - e

the optimal, is for them both to follow the first path, because it's the shortest, remember they both should take the shortest possible path.

in figure 2, the two friends should travel from node a to node f, there are two possible paths:

• a - b - c - f
• a - d - e - f

the two paths are in the same length, but it's better for them to choose the same path, to travel as much together as possible.

so it's clear, that if they are at any node, let's say x, and they will meet again at any other node, let's say y, then for sure all the nodes from the shortest path between x and y are part of the answer !!!

Now, we can say the answer is at a node x_len such that x_len is a part of a shortest path between st and en_a, and a part of a shortest path between st and en_b, and it's distance of st is maximum possible.

So, all we should do is make three BFS the first from node st store the distances in array dis1, second from node en_a store the distances in array dis2, third from node en_b store the distances in array dis3, then for each node x, we say:

if(dis1[x]+dis2[x]==dis1[en_a] && dis1[x]+dis3[x]==dis1[en_b] )ans=max(ans,dis[x]);

remember, if you want to check if a node x, is a part from the shortest path between nodes st and en, then run two BFS, and check whether dis1[x]+dis2[x]==dis1[en]

the time complexity for this code is a simple BFS and it's O(n + m), and the space complexity is O(n).

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

This is all I can say for this problem, I hope you liked my analysis and you benefit from it, I am not gonna post my code, because I think you can code it now after reading the analysis, If there is still something unclear, then fell free to ask me in the comments below, or send me a message...

I will try to post the next blog about the next problem in the following 10-14 days... Happy coding, and have a nice day :D

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

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

Hello Codeforces, my name is C137 and as I said before, I will continue writing regularly in this blog:

The idea is, every 7-10 days i am gonna select a problem that i really found it useful and interesting, and then i will talk about the way i solved this problem, with long editorial and analysis, by this way of sharing my thoughts i hope that grey, green and cyan contestants will benefit from it and learn something new, also i am hoping that top rated contestants will also add their notes to my solution, and suggest some more optimized code.

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

Today, I choose to you this dp problem, I really liked this problem because in the round I solved it in the last 23 minutes, and this helped me becoming blue for the first time, I hope you will like it:

P.S: if you are familiar with the basics of dynamic programing, then i strongly recommend you to try with this problem at least for one hour before reading this blog, otherwise as a start you should check this as it contains a description to the Longest common sub-sequence (LCS) problem .

Before I start, I would like to thank NourAlhadi for solving this problem after reading this blog, and adding his notes and suggestions to make it even more clear.

problem name: Alyona and Strings

Link: this

type: dp

Difficulty level: Medium

Short Description:

You are given two strings, and number K, you should find the length of the longest sub-string consisting of at most K groups of continuous characters.

Example:

Let the two strings be:

aabbcc

aadccc

and k = 2

the answer would be 4, and the sub-string is: aacc

Problem Analysis:

When you read such problem, the first thing that clicks to your mind is dp, there is a famous dp problem so familiar to this one, it's the Longest Common sub-sequence(LCS) so i knew i should start from LCS code, and I wrote the following code on a piece of paper:

int lcs(int i, int j){
	if(i==s1.length() || j==s2.length())return 0;
	int &ret=dp[i][j];
	if(ret!=-1)return ret;
	if(s1[i]==s2[j])return ret= 1+lcs(i+1,j+1);
	return ret=max(lcs(i+1,j) , lcs(i,j+1) );
}

Now, any dp problem could be solved easily if you can determinate three main things:

First, how to represent your state, like the LCS my state should be represented using my position in the first string, and my position in the second one, in addition this problem requires another parameter, its the number of remaining groups, so the state is:

[pos_first_string][pos_second_string][rem_groups]

Second, the end case of the cal function, also like the LCS my cal function should return 0 when i reach the end of one of the two strings, in addition, when i have no remaining groups, i should return 0, because i can't take any more characters, so:

if(i==s1.length() || j==s2.length() || rem_groups==0)return 0;

Now after i represented my state, decided when the cal function should stop, there is only one more thing to consider, how to move from state_a to state_b ??? I mean how to move from a state to another.

Now there are two cases to consider, if there is a common continues characters to take, or if there isn't. If there isn't any common continues characters, which means:

if(s1[i]!=s2[j]) return ret=max(cal(i+1 , j, rem_groups), cal(i, j+1 , rem_groups) );

either i move in the first string, or in the second one, and the number of remaining groups doesn't change.

Now, if there is a common group of length len then I should take it, and increase the answer by len, so i wrote:

if(s1[i]!=s2[j]) return ret=max(cal(i+1 , j,  rem_groups),cal(i, j+1 , rem_groups) );
else ret=len+cal(i+len, j+len, rem_groups-1);
return ret;

when i first saw this problem, there was only 23 minutes remaining in the round, so i was in a big hurry, and have no time to debug my code, I submitted it like this and got wrong answer on the pretests.

with short time remaining, i checked my code on some samples, and it gave me a wrong answer on the following sample:

1
axsss
acsss

my code was printing 1, but the answer is 3, taking sub-string "sss"

what was happening, is sometimes i shouldn't take the group, because perhaps there is longer group after it, so I wrote:

ret=max(cal(i+1 , j,rem_groups),cal(i      , j+1 , rem_groups) );
if(s1[i]!=s2[j])return ret;
else ret=max(ret,len+cal(i+len,j+len,rem_groups-1) );
return ret;

with five minuted remaining, i submitted my code, to get TLE on pretests, i was surprised, as my complexity is:

lenoffirststring * lenofsecondstring * k = 1000 * 100 * 10 = 1⁷

something small, and easily passes the pretests, however after a quick look at the code, i found that i forget in the cal function to write:

if(ret!=-1)return ret;

with three minutes remaining, i fixed the code, and got pretests passed, and finally got it accepted, after very interesting and nervous 19 minutes.

there are some things that i would like to talk about, while solving a dp problem, always check if you passed this state before, so you won't cal the same states multiple times, never forget to initialize your dp array with  - 1, and don't forget the return at the cal function, these are three common bugs at dp codes, that makes you sometimes hate your day.

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

This is all I can say for this problem, I hope you liked my analysis and you benefit from it, I am not gonna post my code, because I think you can code it now after reading the analysis, If there is still something unclear, then fell free to ask me in the comments below, or send me a message...

I will try to post the next blog about the next problem in the following week... Happy coding, and have a nice day :D

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

Hello Codeforces, my name is C137 and starting from today I'm gonna try to write regularly in this blog:

The idea is, every 7-10 days i am gonna select a problem that i really found it useful and interesting, and then i will talk about the way i solved this problem, with long editorial and analysis, by this way of sharing my thoughts i hope that grey, green and cyan contestants will benefit from it and learn something new, also i am hoping that top rated contestants will also add their notes to my solution, and suggest some more optimized code.

As a start i choose the following interesting problem, I hope you will like it :D

P.S: if you are familiar with the Segment tree data structure, then i strongly recommend you to try with this problem at least for two hours before reading this blog, otherwise as a start you should check this and this, also for more advanced Techniques you can check this amazing article .

Before I start, I would like to thank NourAlhadi for solving this problem after reading this blog, and adding his notes and suggestions to make it even more clear.

problem name: Billboard

Source: 2008-2009 ACM-ICPC, NEERC, Northern Subregional Contest

Link: this

type: Data Structures

Difficulty level: Medium

Short Description:

You are given a Billboard with width w, and height h, also you are given n ads, each ad has height 1 and width w_i and for each ad you must decide in which row you will put it, you start putting ads from top and going down if there is enough width in this row, if you can put the ad, then print the number of the row, otherwise print  - 1

Example:

w = 6, h = 3, n = 5

ads widths: 3 3 5 2 5

answer: 1 1 2 3 -1

after putting the first ad, the remaining width will be: 3 6 6

after putting the second ad, the remaining width will be: 0 6 6

after putting the third ad, the remaining width will be: 0 1 6

after putting the fourth ad, the remaining width will be: 0 1 4

there is no row with width 5, so you cant put the last ad.

Problem Analysis:

The first thing that came to my mind when I read this problem was to use set<pair<int, int> > the first parameter of the pair is the row index, and the second is the remaining width in that row, I spent nearly 30 minutes trying to get something useful out of this idea using lower_bound but I only ended with a piece of useless code, so I erased the whole code, cleared this idea from my head, and started thinking in something else.

lets say that the current ad width is x I am interested in the first row with remaining width greater than or equal to x, then I should update the value in that row and decrease it by x, the word "Update" took me to think about Segment tree, what if i used a segment tree, and in each node of the tree I can store the max value in it's range?? now initially i will build the tree, and for each node i will put the value w which is the width of the Billboard, now I can know for each range in the array whether I can put the ad in it or not only with log h time=30, that's great, I started to make some progress, now how can I know the index of the first row greater than or equal to x ??? or there is no answer???

Let's first talk about the no answer case:

if quer (1,1,h) < x then there is no answer, because in the whole tree there is no node with remaining width greater than x.

If there is an answer, but it's not in the range (1, ind) then for sure it will be in the range (ind+1, h) this is so familiar to binary search, actually it's a binary search, so now I can get the first row (the answer) in only log h * log h time =30*30=900 for each ad.

now my pseudo code was something like this:

for each ad 
read x
if(quer(1,1,h)<x)print -1
st=1, en=h
do binary search
if(quer(1,1,mid)>=x)en=mid
else st=mid+1
print st
update(1,1,h) // decrease the value at st by x

OK, now most of the work is done, Or that's what I thought, two big problems were about to make me change the whole idea, and give up solving this problem...

First problem, the time complexity n* log h* log h=200000*30*30=180000000 too big!! and needs optimizations

Second problem, Memory, h is too big, it can go up to 10^9 so I can't use a segment tree array of size 3*h

After five minutes, I noticed that i am not interested in the whole billboard, I just need to use the first n rows of it, because in the worst case, I will but one ad in each row, using only n rows.

About the time,I needed to get rid of one of the log n the query or the binary search, After drawing some trees, I noticed something so important, I can use the structure of the tree to do the Binary Search !!!

Each node of the tree has at most two children, the left child, and the right child, the left child might take me closer to to the answer, and to the lower row, and the right child also might take me closer to the answer, but to a higher row, so when I can go to the left child, I must go straight to it, otherwise go to the right child, finally return the index of the leaf I will reach, and now my pseudo code was something like this:

for each ad 
read x
if(tree[1]<x)print -1
ind =quer(1,1,n,x)
print ind
update(1,1,n) // decrease the value at ind by x

and the quer function will be:

int quer(int pos, int l, int r, int x){
	if(l==r)return l;
	int mid=(l+r)/2;
	if(tree[2*pos]>=x)return quer(2*pos, l ,mid,x);
	else return quer(2*pos+1, mid+1, r, x);
}

Now all the ideas were clear to me, my time complexity is n*log n, the memory is 3*n, and everything was ready on paper, it took me 10 minutes to write the code, and you can't imagine how sad and depressed i was when i got TLE, I checked my code again, and found a stupid bug in the update function, fixed it and got the beloved green light, after a very interesting and amusing two hours of thinking :D

This is all I can say for this problem, I hope you liked my analysis and you benefit from it, I am not gonna post my code, because I think you can code it now after reading the analysis, If there is still something unclear, then fell free to ask me in the comments below, or send me a message...

If you liked the idea, then I will try to post the next blog about the next problem in the following week...

Happy coding, and have a nice day :D

Before this post, my Contribution is +47 but in the Contribution list it's just +40

And I noticed the same thing with some of my friends, like Daniar his Contribution is +24 but in the list it's just +15 is there something wrong here???

We all suffered from the tragedy happened yesterday, from rated to unrated :( , And as far as i remember the last rated round was before 18 days at 30/3/2016.

We all love to see rated rounds, and let's be honest Codeforces the most attractive thing in Codeforces is rated rounds !!! and as I can see we have to wait for another 8 days to see a rated round, that's if " VK Cup 2016 — Round 2 " will be rated :\

Also i see that after three days there will be Educational Codeforces Round 12, how about making it rated??? i mean the problems must be ready by now, maybe it just need a little change to make it suitable to a rated round...

What do you think, Edvard and MikeMirzayanov, is there a chance to see this happen ???

Thanks in Advance...

Once a friend described recursion for me using the following problem:

Le's say that you are the first man standing in a queue, and you have a pen, you want to give it to the last person on the queue, simply say to the man sitting behind you: "If you are the last man in the queue then do nothing, else do like me" and give him the pen.

if you want some practical practice to understand recursion more, then i advise you to check the link.

Hello everyone

I am facing the following geometry problem, and since am not so good at it, i would ask your help:

We have a straight line that goes throw 3 points, A(X1,Y1) B(X2,Y2) and M(X0,Y0).

We know X1,Y1,X2,Y2 and we know d, the distance between A and M, and we have to define the two possible positions of the pair X0,Y0...

Any Help would be highly appreciated, and thanks in advance...

String str;

cin>>str;

for(int i=0;i<str.length();i++){

....

}

if str.length()=n, then the total complexity of the algorithm is n*n?? or just n?

Hello everyone i was solving an easy problem using GNU C++ 4.9.2, but i kept getting runtime error!! the problem was so easy, and the code is simple, which made with mad!! however in the end /after about 3 hours of thinking/ i found that the problem was with the return statement, i was writing return 1; instead of return 0;

but i couldn't understand why this is a runtime error??? can anyone explain to me please...

With many thanks...

Hello Codeforces family!!! i have been just a member of the codeforces family for just 117 days, not so long, not so little too. Today i want to share with you my little achievement, from less than 5 minutes i got my 200 Green light, averaging almost two problems per day, you can say good, knowing that the last two month i was so busy in collogue exams and tests, but it's not enough for me. I will keep on the hard work, especially after i finish my exams, and try to reach 1000 Green light so i could be 200% ready for the ACM-ICPC 2016-2017 !!! and to all contestants, Wish you all the best... Ali_Ibrahim