Hello evevryone!
I would like to invite you to participate in HackerEarth HourStorm #6. It’s the sixth version of the short contest, that runs for 1 hour! The problem set consists of 3 traditional algorithmic tasks of various difficulties. The contest starts on the 15th December 10:00 PM — IST

For traditional algorithmic tasks, you will receive points for every test case your solution passes, so you can get some points with partial solutions as well. Check contest page for more details about in-contest schedule and rules.

I'm the setter of this round and I would like to thank webmaster for helping me preparing the tasks and testing the problems as well. We tried our best to make the problems interesting enough. Hope you'll enjoy the contest. As usual, there will be some prizes for the top three contestants.

$75 Amazon gift card
$50 Amazon gift card
$25 Amazon gift card

In addition, top 5 on the scoreboard with rating less than 1600 will win HackerEarth t-shirts. Good luck to everyone, and let's discuss the problems after the contest!

Wrote this article a long ago but during solving a problem recently thought of sharing this article publicly. Hope it will help some contestants to understand the idea clearly.

Digit dp is a very easy technique and also useful to solve many dynamic programming problems. Seeing the name “Digit DP” it’s easy to guess that we are going to do something using the digits. Yes we are actually going to play with digits. Let’s explain the concept using a classical problem.

Problem

How many numbers x are there in the range a to b, where the digit d occurs exactly k times in x? There may have several solutions including number theory or combinatorics, but let’s see how we can solve this problem using digit dp.

Solve for range (zero to a)

Using digit dp we always focus on building a number satisfying all the conditions. If we finally manage to build that number then we say, yes we have got one ;-) But how we’ll build that number? For the time being let’s say a is zero. So we need to find the total numbers which are not greater than b and also satisfy the given conditions.

Building a sequence of digits

Let’s consider the number as a sequence of digits. Let’s name the sequence sq. Initially sq is empty. We’ll try to add new digits from left to right to build the sequence. In each recursive call we’ll place a digit in our current position and will call recursively to add a digit in the next position. But can we place any of the digits from 0 to 9 in our current position? Of course not, because we need to make sure that the number is not getting larger than b.

Information we need to place a digit at the current position

Let’s say during the building of the sequence, currently we are at position pos. We have already placed some digits in position from 1 to pos-1. So now we are trying to place a digit at current position pos. If we knew the whole sequence we have build so far till position pos-1 then we could easily find out which digits we can place now. But how?

You can see that, in the sequence sq the left most digit is actually the most significant digit. And the significance get decreased from left to right. So if there exist any position t (1<=t<pos) where sq[t] < b[t] then we can place any digit in our current position. Because the sequence has already become smaller than b no matter which digit we place in the later positions. Note, b[t] means the digit at position t at number b.

But if there was no t that satisfy that condition then at position pos, we can’t place any digit greater than b[pos]. Because then the number will become larger than b.

Do we really need the whole sequence?

Now imagine, do we really need that whole sequence to find if a valid t exist? If we placed any digit in our previous position which was smaller than its corresponding digit in b then couldn’t we just pass the information somehow so that we can use it later? Yes, using an extra parameter f1(true/false) in our function we can handle that. Whenever we place a digit at position t which is smaller than b[t] we can make f1 = 1 for the next recursive call. So whenever we are at any position later, we don’t actually need the whole sequence. Using the value of f1 we can know if the sequence have already become smaller than b.

Extra condition

So far we focused on building the sequence sq, but we have forgotten that there is an extra condition which is, digit d will have to occur exactly k times in sequence sq. We need another parameter cnt. cnt is basically the number of times we have placed digit d so far in our sequence sq. Whenever we place digit d in our sequence sq we just increment cnt in our next recursive call.

In the base case when we have built the whole sequence we just need to check if cnt is equal to k. If it is then we return 1, otherwise we return 0.

Final DP States

If we have understood everything so far then it's easy to see that we need total three states for DP memoization. At which position we are, if the number has already become smaller than b and the frequency of digit d till now.

Solve for range (a to b)

Using the above approach we can find the total valid numbers in the range 0 to b. But in the original problem the range was actually a to b. How to handle that? Well, first we can find the result for range 0 to b and then just remove the result for range 0 to a-1. Then what we are left off is actually the result from range a to b.

How to solve for range a to b in a single recursion?

In the above approach we used an extra parameter f1 which helped us to make sure the sequence is not getting larger than b. Can’t we do the similar thing so that the sequence does not become smaller than a? Yes of course. For that, we need to maintain an extra parameter f2 which will say if there exist a position t such that sq[t] > a[t]. Depending on the value of f2 we can select the digits in our current position so that the sequence does not become smaller than a. Note: We also have to maintain the condition for f1 parallely so that the sequence remains valid.

Please check this to find the sample code of our initial approach.

Problem List

1. Investigation
2. LIDS
3. Magic Numbers
4. Palindromic Numbers
5. Chef and Digits
6. Maximum Product
7. Cantor
8. Digit Count
9. Logan and DIGIT IMMUNE numbers
10. Sanvi and Magical Numbers
11. Sum of Digits
12. Digit Sum
13. Ra-One Numbers
14. LUCIFER Number
15. 369 Numbers
16. Chef and special numbers
17. Perfect Number
18. The Great Ninja War

Is there some other problems? Some suggestions are really welcomed :)

I was trying to learn burnside lemma and now i feel it's one of the very rare topic in competitive programming.

Here are some resources i found very useful:

1. math.stackexchange

2. petr's blog

3. imomath

4. Hackerrank Blog

5. AlgoWiki

Here are some problems related to burnside lemma:

1. Necklace

2. Necklace of Beads

3. The Beautiful Board

4. Lucy and the Flowers

5. Count the Necklaces

6. Cube Coloring

7. Magic Bracelet

8. Sorting Machine

9. Pizza Toppings

10. Drum Decorator

11. Alphabet Soup

Is there some other good resources or problems related to burnside lemma? Please suggest some more.

Will there be any international training camp for programming contestants in next winter or summer?

Update: There's a Programming Bootcamp in Barcelona in next February,2017. MikeMirzayanov had already posted about this.

Given a number N we have to find the summation of all possible LCM(i,j) where i <= j <= N.

Constraints: N<=10^6 and total test case <= 10^5

Problem Link : Light OJ 1375

How to find the intersected area between a circle and a triangle? I was trying to read this explanation in stackoverflow but got confused in the last part. Can anyone please explain the solution in a simpler way? I need to learn this technique for this problem.

Any idea or hint how to solve this problem?

Wouldn't it be more interesting if we could sort our ranklist by country name or institution name like Hackerrank or Codechef?Hope Codeforces will add this feature very soon :)

Need help with this two number theory problems.Give me some hints please.

Problem 1:

Given an integer N <= 10^25000 find the smallest m <= N such that m/phi(m) is maximum. Where phi is euler's totient function.

Input:

The first line in the input gives the number of test cases T (T<=200), and then T lines follow each containing an integer N.

Output: Output the smallest required value of m.

Sample Input:

1
10

Output:

6

Problem 2:

You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of n^k.

Input:

Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a line containing two integers: n (2 ≤ n < 2^31) and k (1 ≤ k ≤ 10^7).

Output:

For each case, print the case number and the three leading digits (most significant) and three trailing digits (least significant). You can assume that the input is given such that n^k contains at least six digits.

Sample Input:

5
123456 1
123456 2
2 31
2 32
29 8751919

Sample Output:

Case 1: 123 456
Case 2: 152 936
Case 3: 214 648
Case 4: 429 296
Case 5: 665 669

What are some important eBooks for learning number theories & advanced graph theories?Please suggest me some books for studying.

According to the contest schedule the next round is going to be held on 26th October.And the previous one was held on 15th October.I don't understand why there's too much gap between this two rounds.ICPC regional is very close.So i think that would be really helpful for all the contestants if we can participate in more and more contests.

I see there'll be an online mirror of ACM-ICPC, NEERC, Southern Subregional Contest tomorrow.Is that contest going to be rated?

I'm stuck with this problem and can't figure out how to proceed.Can anyone give me some hints how can i solve it using BPM?

Why doesn't codeforces have the feature of separated discussion page for all the contest problems.After the contest sometimes it becomes too hard to solve many problems.Though the editorials are provided but sometimes we also can't understand the editorial properly.Sometimes we have lots of confusions with the problem description and the logic and algorithm to solve that problem.So that would be really great if codeforces provide the feature for discussing the specific problems in separated discussion pages/forums where all the participants will be able discuss on that problem.Besides, that will be also helpful for other participants who will try to solve those problems in future.Because they can then see the previous discussions on any problem and clarify their confusions.Of course i like all the codeforces features very much but it's just my own opinion as i feel it most of the times :)

I was trying to solve this problem but getting WA.I used heavy light decomposition technique to solve it.But can't find out any case where my code fails.

Here is my code link.

I would relly appreciate if anyone help me finding my error.

Problem Description:

Finally the Great Magical Lamp was in Aladdins hand. Now he wanted to return home. But he didnt want to take any help from the Genie because he thought that it might be another adventure for him. All he remembered was the paths he had taken to reach there. But since he took the lamp, all the genies in the cave became angry and they were planning to attack. As Aladdin was not afraid, he wondered how many genies were there. He summoned the Genie from the lamp and asked this.

Now you are given a similar problem. For simplicity assume that, you are given a tree (a connected graph with no cycles) with n nodes, nodes represent places, edges represent roads. In each node, initially there are an arbitrary number of genies. But the numbers of genies change in time. So, you are given a tree, the number of genies in each node and several queries of two types. They are:

1)      0 i j, it means that you have to find the total number of genies in the nodes that occur in path from node i to j (0 ≤ i, j < n).
2)      1 i v, it means that number of genies in node i is changed to v (0 ≤ i < n, 0 ≤ v ≤ 1000).

Input
Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a blank line. Next line contains an integer n (2 ≤ n ≤ 30000). The next line contains n space separated integers between 0 and 1000, denoting the number of genies in the nodes respectively. Then there are n-1 lines each containing two integers: u v (0 ≤ u, v < n, u ≠ v) meaning that there is an edge from node u and v. Assume that the edges form a valid tree. Next line contains an integer q (1 ≤ q ≤ 105) followed by q lines each containing a query as described above.

Output
For each case, print the case number in a single line. Then for each query 0 i j, print the total number of genies in the nodes that occur in path i to j.


Sample Input:
1
 
4
10 20 30 40
0 1
1 2
1 3
3
0 2 3
1 1 100
0 2 3

Sample Output:
Case 1:
90
170

Cany anyone give me some hints how can i solve the problem using segment tree?

Problem Link: Consecutive Sum

Problem Description:

Little Jimmy is learning how to add integers. As in decimal the digits are 0 to 9, it makes a bit hard for him to understand the summation of all pair of digits. Since addition of numbers requires the knowledge of adding digits. So, his mother gave him a software that can convert a decimal integer to its binary and a binary to its corresponding decimal. So, Jimmy's idea is to convert the numbers into binaries, and then he adds them and turns the result back to decimal using the software. It's easy to add in binary, since you only need to know how to add (0, 0), (0, 1), (1, 0), (1, 1). Jimmy doesn't have the idea of carry operation, so he thinks that

1 + 1 = 0
1 + 0 = 1
0 + 1 = 1
0 + 0 = 0

Using these operations, he adds the numbers in binary. So, according to his calculations, 3 (011) + 7 (111) = 4 (100)

Now you are given an array of n integers, indexed from 0 to n-1, you have to find two indices i j in the array (0 ≤ i ≤ j < n) such that the summation (according to Jimmy) of all integers between indices i and j in the array, is maximum. And you also have to find two indices, p q in the array (0 ≤ p ≤ q < n) such that the summation (according to Jimmy) of all integers between indices p and q in the array, is minimum. You only have to report the maximum and minimum integers.

Input Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 50000) The next line contains n space separated non-negative integers, denoting the integers of the given array. Each integer fits into a 32 bit signed integer.

Output For each case, print the case number, the maximum and minimum summation that can be made using Jimmy's addition.

Sample Input:

2
5
6 8 2 4 2
5
3 8 2 6 5

Output for Sample Input:

Case 1: 14 2
Case 2: 15 1

If a person loves programming too much and can never concentrate on academic studies which one he should prefer mostly?Programming or cGPA?I'm asking this because i worked too hard and spent too much time in coding in the last few months but didn't get the desired result!I started programming too late.It's almost 2 years.And i started participating in contests 8/9 months ago.So it's taking too much time for me to fill the gaps.I just have 2 years left of my graduation.And my cGPA is going down semester by semester.So i just have two choices left.Either i have to continue spending most of my times in coding to become more skilled or i have to give much time for academic courses to make my cGPA higher.But i really prefer programming over everything.Though my performences are not that much good till now but i want to give my 100% for it to become a very skilled coder before next year.I'm just frustrated and confused!I would really appreciate some suggestions!

Given N segments (1-d) and Q numbers, for each of the numbers we have to find the number of segments which contain that number. A number "num" will lie in a segment (A,B) if A ≤ num ≤ B. For example, let the segments are (6 12), (8 8), (10 12), (8 11) and (0 12). Now for any query if the given number is 11(eleven), then the answer is 4.Because the number is contained by 4 segments. Here 1 <= (N,Q) <= 50000 Problem Link Some hints on how the problem can be solved using segment tree would be really helpful.

Given two decimal numbers U and V if we write down all the numbers from U to V how many zeroes(0) we will write?Where U<=V<=10^9 For example if U = 100 and V = 105 then we have to write 100,101,102,103,104,105 There are total 7 zeroes therefore the result is 7. I was trying to find a pattern but i could not come up with any perfect solution :(

Given two integers N and M, count the number of integers x between 2 and N! , having the property that all prime factors of x are greater than M. Where 1≤M≤N<10000001 and (N-M)≤100000. Can anyone help me with the logic?

I'm struggling to solve problem C in Codeforces div 2 round.I can solve B very quickly but barely solved problem C.Can anyone give me some suggestions how can i prepere myself to gain the capability to solve problem C?

Problem Link : http://www.spoj.com/problems/MULTQ3/

I tried to solve the problem using two different logic.

1. For the first one for both update & query when i'm getting the propagate value of parent node is not zero,i'm calculating the result for it and then adding those propagate value to its left & right child.Then i'm making its own propagate value to zero as i have already use it for that node.So for the query operation i'm just returning the valid result when i find a valid range.I got AC for these one.
2. For the second one for update operation when i find a valid range then i update its propagate value and also update the result while returning.So for the query operation until i find a valid range i sum up all the propagate value and pass it as a carry value while calling.Then when i find a valid range then calculate the result using that carry value and return it.But i'm getting WA for these solution though the logic seems ok to me. Can anyone help me where i'm doing wrong?

• My AC Code : http://ideone.com/IApyMo
• My WA Code : http://ideone.com/7MaAlr

Hello, can anyone help me with this problem?I'm getting time limit with this solution but i can't find any error in my code.I used bit mask dp for these solution. Here is my code : http://ideone.com/xVl0JI Problem Link : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1885

(THE PROBLEM IS SOLVED FINALLY :) )