Hello Codeforces community,

Get ready for an exciting Sunday action your way.

This Sunday, 17th September, from 9:30pm to 12:00am (IST) Codechef is organising Mega Cook off for ICPC aspirants from around the world.

The panel for the contest consists of :

• Problem Setter and Editorialist : likecs(Bhuvnesh Jain)
• Problem Tester : kingofnumbers(Hasan Jaddouh)
• Admin : kingofnumbers(Hasan Jaddouh)
• Russian Translator : CherryTree(Sergey Kulik)
• Mandarin Translator : huzecong(Hu Zecong)
• Vietnamese Translator : Team VNOI
• Language Verifier: (Priyank jaini)

I would also like to thank Codechef team and Praveen Dhinwa (PraveenDhinwa) for help in preparing the contest.

Hope you will enjoy solving the problems. The editorials with the model solutions will be available right aafter the contest. Please give your feedback on the problem set in the comments below after the contest.

Please find the rest of the details about the contest below.

Time: 17th September 2017 (2130 hrs) to 18th September 2017 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/COOK86

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: Top 10 school students each from Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected]).

In addition to the above prizes, top 50 Indian students will get their ACM-ICPC expenses reimbursed. For more details refer here.

The main characters of the contest are Chef Dobby and Bhuvan.

Good Luck! Hope to see you participating!!

UPD 1: The contest starts in 25 minutes. Best of luck.

UPD2: The contest has started.

UPD3: The contest has ended. Congratulations to all the winners and also everyone who solved the complete problemset.

The global top 5 (also overall top 5) are :

1. tourist (Special Congratulations for completely solving the contest in just 34 minutes).

2. uwi

3. RAVEman

4. zeliboba

5. I_love_Tanya_Romanova

The top 5 Indians are :

1. jtnydv25

2. saharshluthra

3. gvaibhav21

4. architkarandikar

5. abisheka

How can we optimise dynamic programming of the form:

Base case : dp[i] = a[i] * i

dp[i] = max(dp[i], dp[j] + (a[i] - a[j]) * (i - j)), for 1 ≤ j < i

It is given that n ≤ 10⁵ and |a_i| ≤ 10¹². Naively, it can be computed in O(n²). But I can't further improve my solution.

I tried the following :

(a[i] - a[j]) * (i - j) = a[i] * i + a[j] * j - a[i] * j - a[j] * i

Thus, we can store another array, dp2[i] = dp[i] + a[i] * i. Then the recurrence becomes :

Base case : dp[i] = 0

dp[i] = max(dp[i], dp2[j] - a[i] * j - a[j] * i)

Finally : dp[i] = dp[i] + a[i] * i and dp2[i] = dp[i] + a[i] * i

But, it is still O(n²).

Any hints would be appreciated.

Love solving Mathematical problems. Then get ready for some action ahead.

Computer Science Association, BITS PILANI, Pilani Campus presents you their flagship contest, "Mathemagic 2017". It is being organised as a part of our technical fest, Apogee.

Contest Link : https://www.hackerrank.com/mathemagic-bits

Start Time : 17:00 IST, 23rd March' 2017

Prizes to be Won:

First Place: INR 3000, Second Place: INR 2000, Third Place: INR 1000.

The contest consists of 10 problems of varying difficulty similar to ones available at Project Euler and Ad Infinitum contests. The problems have been set such that even beginners can attempt a few problems and even the best coders find tough job ahead at the hard ones. Although Mathematical insights and tricks would help you find the logic in the problem, programming will be your way out for the full solution. There will be 4 "TEXT" based problems where the input is provided in the question, similar to the format in Project Euler. Rest 6 problems will be programming based. The editorials of all the problems with the Setter's code will be uploaded immediately after the contest so that you may benefit from it.

The problems have been set by me. I would like to thank -Morass- for testing the problems and providing valuable feedback as well. I would also like to thank ujzwt4it and CSA juniors for their feedback as well.

To register for the contest, you just need a Hackerrank handle and then just click on the link mentioned above for registering for the contest.

I hope you enjoy the contest and Happy Coding :)

UPDATE 1: Scoring & Type Distribution will be as follows:

• 1: Easy 20 points (Text)

• 2: Easy 30 points (Text)

• 3: Medium 60 points (Programming)

• 4: Medium 60 points (Text)

• 5: Medium 80 points (Programming)

• 6: Hard 100 points (Text)

• 7: Hard 120 points (Programming)

• 8: Advanced 150 points (Programming)

• 9: Advanced 180 points (Programming)

• 10: Advanced 200 points (Programming)

UPDATE2 : Contest is over and editorials are out. Winners will be announced soon after plagiarism check is over.

UPDATE3: The winners of the contest are :

1. uwi

2. jtnydv25

3. bayleef

A was thinking about a DAG problem. It goes as follows:

You are given a directed acyclic graph with N nodes and M edges. Every vertex has a number associated with it, let us call it A[i]. The power of every vertex is defined as the sum of values written on every vertex reachable from it. We are given Q queries. In each query we need to find the power of a given vertex.

For example, Let N = 5, M = 5 and the value of A = {2, 3, 1, 4, 2}. (Assume 1-based indexing). Let the edges be {(2, 1), (3, 1), (4, 2), (4, 3), (3, 5)}, where (x, y) means there is directed edge from x to y.

So, querying for vertex 4, gives a answer of (2 + 3 + 1 + 4 + 2) = 12, as every vertex is reachable from it, while for vertex 3, it gives answer as (2 + 3 + 2) = 7 as only {1, 3, 5} are reachable from it.

The brute force solution is to perform dfs/bfs in every query. If possible, can you please provide an efficient algorithm for this. (I was thinking about some kind of precomputation using topological sort, but ended but added some values more than once.)

Thank you.

Hello All,

I have some questions as doubts:

1) How can we solve problem E (The secret code) in http://codeforces.me/gym/100371 Any hints?

2) I am given an sorted array of 1000 elements, where each element can be in the range [0, 20000]. We need to consider all subsequences on the array. For every subsequence, it's power is defined as the sum of all the elements in it. We are given 1000 queries of the form "x" where i need to print the xth smallest value of the power of any subsequence of the array. Here "x" is in the range of [1, min(2^n, 10000)].

For example: Let the array be [1, 2, 100]. Then the power of subsequences sorted order are [0, 1, 2, 3, 100, 101, 102, 103]. If the query is x = 3, I need to print 2.

3) How can we solve this problem https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2334

My approach to this problem- First of all if the graph contains a directed cycle, then the answer is 0, as a trivial case. Otherwise, consider all the cases where we can partition the groups into 2 equal halves. For this I use of mask (till 2^(2m)) and if it contains number of set bits as "m" I continue the loop. Then I consider the partition if it is valid or not i.e. if in partition 1 or 2, whether there exits a person "i" who has a dependency on person "j" but is not present in the same set. In such a case, I just add nothing. In rest of the cases, I try to find the number of topological sorts on graph in set 1 and 2 and multiply their results and finally add it to the final result. (For number of topological sorts, I used this method http://cs.stackexchange.com/questions/12713/find-the-number-of-topological-sorts-in-a-tree )

Here is a link to my code according to the above implementation https://textb.org/r/doubt-likecs/

4) How can we efficiently find the points of intersection of a line and polygon, where the polygon is not necessarily convex polygon (but the polygon is simple)?

Please help in the above problems. If possible please post the code as well.

Thanks in advance.

I was learning the topic FFT from e-maxx.ru (translated version). The english translation for this part "The discrete Fourier transform in a modular arithmetic" is not very clear on google chrome. Also, I am not able to understand clearly the math behind it. Please someone explain it.

Also, I have one doubt regarding the generators in number theoretic transforms. I was going through this solution of this problem. I understood the editorial and how to solve it using fft. But in the NTT solution (given in link) the author discusses about generators for certain prime numbers in comments. Can you please elaborate what are generators and how to calculate them?

Thanks in advance.

**EDIT: ** Understood the concept.

Hello everyone, I have a doubt regarding precision error problems. For example I wrote a code like here.

Initially the numbers I am multiplying are 2, 10, 10, 10 i.e product should be 2000 but what I get is 1999.

I usually see people use some small value like EPS (10^(-6) or 10^(-10)) in their code. Even while comparing double they do it like abs(a-b)<=EPS, then equal else not. They do not do directly like a!=b.

Please someone explain the above observations and how to effectively take care of it in competitions. Many a times, after passing pretest we fail system tests due to precision errors. What value of EPS (epsilon) do you set or decide from the problem constraints. Please discuss your approach.

The first coding contest made by me. Codestorm Prelims

Do come and participate. It is on Sunday from 3:00 to 6:00 pm on Codechef. The problem-set will consist of 7-8 problems. It is a team contest with maximum of 2 members. ACM-style ranking followed. Submissions in all languages supported by Codechef is possible. Winners will get a chance to advance to the Onsite round next week.

Registration Link

The problems are of varying difficulty and from vast number of topics. The problems have been set such that even beginners can attempt a few problems and even the best coders find tough job ahead at the hard ones. I hope you enjoy the contest. The Editorials for the contest will also be put up after the Onsite round is over.

Image

Happy Coding :)

I have doubt why my solution failed for QB for round #336 Div2 during system testing.

Here is my approach for the question.(Assuming 0-based indexing of strings everywhere.)

Let us assume len(a) = 3, len(b) = 10 and a = 101 and b = 1001001001. So the required sub-strings are 100, 001, 010, 100, 001, 010, 100, 001 which are to be checked with 101. Here hamming distance is simply the no of distinct characters between string a and given sub-string of b. So the hamming distances are respectively 1, 1, 3, 1, 1, 3, 1, 1 i.e. total answer is 12 for this case.

Initially I found the number of ones and zeros in string a till a given position. (this is stored in sec[i][0] and sec[i][1] in my code).

Next we see that the 0th position of b is compared with only 0th position of a in all cases. The 1st position is only compared with the 0th (in sub-string 2) and 1st (in sub-string 1) positions of string a. the 8th position in b is compared with 1st (in sub-string 8) and 2nd (in sub-string 7) positions of string a and finally 9th position in b is only compared with 2nd position in string a. Rest all the characters between 2nd and 7th positions (inclusive) are compared with all the character positions of string a once in the cases possible.

In general the first 0 to len(a)-1 characters are only compared with 0 to given index vales of string a and the reverse happens for the ending characters. they are compared with last characters of a. The remaining middle characters i.e. fro len(a)th position to (len(b)-len(a))th position are compared with all the characters of string a.

Here is my code for the above implementation. http://codeforces.me/contest/608/submission/14948872.

I am only able to understand why this logic fails.

PS: All the solutions seen till now by me have done the opposite i.e. stored the count of zeros and ones for string b and traversed on string a. But i want to understand what difference does it make if I do the reverse.