CodeChef invites you to participate in the May Cook-off 2015 at http://www.codechef.com/COOK58. The CodeChef May Cook-Off 2015 is an especial contest dedicated to our beloved community member Harsha Suryanarayana, whose sudden demise last year left us all in shock. Harsha, was an inspiration to many and he remains so. On his birthday, 23rd May let’s come together and do what Harsha liked the most and that is to have a fun filled competitive contest. So, do join us for the May Cook-Off 2015 to pay homage to one of finest and respected community member. You will always be with us humblefool.

Time: 24nd May 2015 (2130 hrs) to 25rd May 2015 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: http://www.codechef.com/COOK58

Registration: Just need to have a CodeChef user id to participate.

New users please register here

- Problem Setters : RedAnt (Anil Kishore) and PraveenDhinwa (Praveen Dhinwa)
- Editorialist: Balajiganapathi (Balajiganapathi)
- Problem Tester: utkarshl (Utkarsh Lath)
- Russian Translator : CherryTree (Sergey Kulik)
- Mandarin Translator: gediiiiiii (Gedi Zheng)
- Contest Admin: PraveenDhinwa (Praveen Dhinwa)

It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.

CodeChef invites all the programming enthusiasts to take part in the CodeChef SnackDown Round 1A. The contest is a part of CodeChef SnackDown, a multi-round onsite programming contest and we want you all to be a part of it. It is a team contest open to students and professionals alike. The contest will have 3 problems and will be of 2 hours duration. You surely will enjoy cracking them.

All you need to take part in this contest is a CodeChef username. If you do not have one, please register here to participate.

Also, it is a team contest, so you need to register your teams first to take part in the contest. To register your team, register/login through CodeChef and go to: http://snackdown.codechef.com/register/

Date of Contest: 23rd May 2015 Time: 14:30:00 hrs to 16:30:00 hrs IST Check out the local time in your City/Time Zone here.

Contest Details

• Contest link: http://www.codechef.com/SNCK2015
• Problem Setters: CherryTree (Sergey Kulik) and PraveenDhinwa (Praveen Dhinwa)
• Problem Testers: kevinsogo (Kevin Charles Atienza) and Piyush Kumar
• Editorialist: kevinsogo (Kevin Charles Atienza)
• Translators: CherryTree (Sergey Kulik) (Russian), MinakoKojima (Minako Kojima) (Mandarin), ptnk8554517 (Tran Phan Anh Khoa) and duykhanhuet (Khanh Duy Nguyen) (Vietnamese).
• Contest Admin: PraveenDhinwa (Praveen Dhinwa)

Prizes
For the current round, Along with top ranked participants, top 10 fastest successful submissions will get cool CodeChef SnackDown Merchandise. Please see details of the prizes of the entire competition here. You can also see schedule and other details on the Snackdown page

Top 500 teams in the round will advance to next Elimination Round. Others will have two more chances to qualify by participating in Round 1B and Round 1C.

Please also note that we will also provide Vietnamese translations in all Snackdown rounds. A big thanks to I_love_Hoang_Yen (Thanh Trung Nguyen) for making the proposal of including Vietnamese translations and providing big help in finding out translators.

We hope to see you all participating in the contest. Good Luck! Hope to see you participating.

451A - Game With Sticks

From a grid of size n * m, if we remove an intersection point, then the grid after removing the sticks passing through it, will of size n - 1, m - 1.

Notice when the grid consists of a single horizontal stick and m vertical sticks, If we pick any intersection point, then the updated grid will be only made of vertical sticks. You can see that there is no intersection point in the grid now.

So
ans(n, m) = ans(n - 1, m - 1) ^ 1.
ans(1,  * ) = 1
ans( * , 1) = 1

So we can notice that answer will depend on the parity of minimum(m, n).
You can prove it using the previous equations. You can also check this by seeing the pattern.

So finally if min(n, m) is odd, then Akshat will win. Otherwise Malvika will win.

You can also observe that "players will play optimally" is useless in this case.

Complexity : O(1)

Solution codes

• my solution

451B - Sort the Array

Note that if from a given sorted array, if reverse a segment, then the remaining array will be arranged in following way. First increasing sequence, then decreasing, then again increasing.

You can find the first position where the sequences start decreasing from the beginning. Call it L.
You can find the first position where the sequences start increasing from the end. Call it R.

Now we just need to reverse the segment between a[L] to a[R].

Here is outline of my solution which is easy to implement. First I map larger numbers to numbers strictly in the range 1, n.
As all the numbers are distinct, no two numbers in the mapping will be equal too.

Let us define L to be smallest index such that A[i]! = i.
Let us also define R to be largest index such that A[i]! = i.

Note that if there is no such L and R, it means that array is sorted already. So answer will be "yes", we can simply reverse any of the 1 length consecutive segment.

Otherwise we will simply reverse the array from [L, R]. After the reversal, we will check whether the array is sorted or not.

Complexity: O(nlogn)

Solution codes

• my solution

451C - Predict Outcome of the Game

Let x₁ be number of wins of first team in the first k games.
Let x₂ be number of wins of second team in the first k games.
Let x₃ be number of wins of third team in the first k games.

Note that x₁ + x₂ + x₃ = k ---(1)
|x₁ - x₂| = d₁. — (a)
|x₂ - x₃| = d₂. — (b)

Note that |x| can be x and -x depending on the sign of x.

Case 1: Assume that x₁ > x₂ and x₂ > x₃.
x₁ - x₂ = d₁ ---(2)
x₂ - x₃ = d₂ ---(3)

Adding 1 and 2, we get
2x₁ + x₃ = d₁ + k --(4)
Adding 2 and 3, we get
x₁ - x₃ = d₁ + d₂ ---(5).

Now solve (4) and (5), we will get values of x₁ and x₃. By those values, compute value of x₂. Now we should check the constraints that x₁ ≥ x₂ and x₂ ≥ 3.

Now comes the most important part. Number of wins at the end of each team should be n / 3. So if n is not divisible by 3, then our answer will be definitely "no".

Note that if all of the x₁, x₂, x₃ are  ≤ n / 3, then we can have the remaining matches in such a way that final numbers of wins of each team should be equal.

Now you have to take 4 such cases. Implementing such cases in 4 if-else statements could incur errors in implementation. You can check my code to understand a simple way to implement it.

I will explain idea of my code briefly, basically equation (a) and (b) can be opened with either positive or negative sign due to modulus.
So if our sign is negative we will change d₁ to be  - d₁. So if we solve a single equation and replace d₁ by  - d₁, we can get solution for the second case.

All the cases can be dealt in such way. Please see my code for more details.

Complexity: O(1) per test case.

Solution codes

• my solution

451D - Count Good Substrings

Merging Step: We have to convert string like "aaaabbbaabaaa" into "ababa".

Important Observation
A substring made of the string will be a "good" palindrome if their starting and ending characters are same. If the starting and ending characters are same, then the middle characters after merging will be alternating between 'a' and 'b'. eg. "abaa" is not a palindrome, but it is a good palindrome. After merging step it becomes "aba". Note that in the string left after merging, the consecutive characters will alternate between 'a' and 'b'.

So if we are currently at the i^th character, then we can have to simply check how many positions we have encountered upto now having the same character as that of i^th. For counting even and odd separately, we can make count of a's and b's at even and odd positions.

So if we are at i^th position, for counting even good palindromes, you just need to add count of number of characters a's at odd position. For counting odd good palindromes, you just need to add count of number of characters a's at even position.

Complexity: O(n) where n is length of string s.

Solution codes

• my solution

Note that you can also consult following comment for alternate editorial.

451E - Devu and Flowers

The number of ways to choose N items out of R groups where each item in a group is identical is equal to the number of integral solutions to x₁ + x₂ + x₃...x_R = N, where 0 ≤ x_i ≤ L_i, where L_i is the number of items in i^th group. Number of integral solutions are coefficient of x^N in [Product of (1 + x + x * x + ...x^L_i) over all $i$].

You need to find coefficient of x^s in (1 + x + x² + x³ +  + ..x^f₁) *  *  * (1 + x + x² + x³ +  + ..x^f_n).

Using sum of Geometric progression we can say that (1 + x + x² + x³ +  + ..x^f₁) = (1 - x^{(f₁ + 1)}) / (1 - x).

Substituting in the expression, we get (1 - x^{(f₁ + 1))} / (1 - x) *  *  * (1 - x^{(f_n + 1))} / (1 - x).

= (1 - x^{(f₁ + 1))} * .. * (1 - x^{(f_n + 1))} * (1 - x)^( - n).

Now we can find x^s in (1 - x)^- n easily. It is .

You can have a look at following link. to understand it better.

So now as s is large, we can not afford to iterate over s.

But n is small, we notice that (1 - x^{(f₁ + 1))} * .. * (1 - x^{(f_n + 1))} can have at most 2ⁿ terms.

So we will simply find all those terms, they can be very easily computed by maintaining a vector<pair<int, int> > containing pairs of coefficients and their corresponding powers. You can write a recursive function for doing this.

How to find % p. As n + s - 1 is large and s is very small. You can use lucas's theorem. If you understand lucas's theorem, you can note that we simply have to compute .

Complexity: O(n * 2ⁿ).

Another solution based on inclusion exclusion principle.

Please see the following comments to get the complete idea.
Comment 1
Comment 2
Comment 3

Solution codes

• my solution (Java)
• another (C++)
• Inclusion Exclusion based solution

439A - Devu, the Singer and Churu, the Joker

For checking whether there is a way to conduct all the songs of the singer, you can conduct the event in the following way.

• First singer will sing a song.
• Then during 10 minutes rest of the singer, the joker will crack 2 jokes(each of 5 minutes)
• Then singer will again sing a song, then joker, etc.
• After the singer has completes all his songs, the joker will keep on cracking jokes of 5 minutes each.

Hence minimum duration of the even needed such that sing could sing all his songs will be t₁ + 10 + t₂ + 10 + ... +t_n = sum + (n - 1) * 10 where sum denote the total time of the songs of the singer.

So for checking feasibility of the solution, just check whether sum + (n - 1) * 10 ≤ duration or not?.

If it is feasible, then time remaining for joker will be the entire duration except the time when the singer is singing the song. Hence time available for the joker will be duration - sum. In that time joker will sing songs.

Solution codes

• my solution

439B - Devu, the Dumb Guy

You can formulate the problem in following way. Given two arrays a and b. Find minimum cost of matching the elements of array a to b. For our problem the array a will be same as b. The array b will have content x, x — 1, , 1, 1. For a general version of this problem, we can use min cost max flow(min cost matching), but for this problem following simple greedy solution will work.

• Sort the array a in increasing and b in decreasing order (or vice versa).
• Now match i^th element of the array a with i^th element of array b.

Proof:

It can be easily proved by exchange argument.

Solution Codes

• my solution

439C - Devu and Partitioning of the Array

Let us first try to find the condition required to make sure the existence of the partitions.

Notice the following points.

• If the parity of sum does not match with parity of number of odd partitions (k - p) , then we can't create the required partitions. eg. a = [1;2], k = 2, p = 0, Then you can not create two partitions of odd size, because then sum of the elements of the partitions of the array will be even whereas the sum of elements of the array is odd.

• If number of odd elements in a are less than k - p (number of required partitions with odd sum), then we can not do a valid partitioning.

• If number of even elements are less than p, then we can not create even partitions simply by using even numbers, we have to use odd numbers too. Notice the simple fact that sum of two odd numbers is even. Hence we will try to include 2 odd elements in our partitions too. So if we can create oddsRemaining / 2 partitions in which every partition contains 2 odd elements, then we can do a valid partitioning otherwise we can't. Here oddsRemaining denotes the number of odd elements which are not used in any of the partitions made up to now.

Let oddElements denotes the number of odd elements in array a. Similarly evenElements denotes the number of even elements.

So the answer exists if

• Number of possible odd partitions are  ≥  k - p i.e. oddElements ≥ k - p.
• Number of possible even partitions are  ≥  p i.e. evenElements + (oddRemaining) / 2 ≥ p. where oddRemaining is oddElements - (k - p).

For generating the actual partitions, you can follow the same strategy used in detecting the existence of the partitions. We will first generate any valid p partitions (forget about the condition of using the entire array), then we can simply include the remaining elements of the array in the last partition and we are done.

Solution Codes

• [user:Gerald]'s solution

• my code

439D - Devu and his Brother

You can solve the problem in two ways.

• By using ternary search

Let us define a function f. Function f(k) = cost needed to make array a elements  ≥  k + cost needed to make array b elements  ≤  k

Instead of proving it formally, try checking the property on many random test cases. You will realize that f is convex.

Claim: f is convex:

Proof:

It is fairly easy to prove. See the derivative of f.

= — (# of elements of b > k) + (# of elements of a < k)

The first term (without sign) can only decrease as k increases whereas second term can only increase as k increases.

So,

• By using the fact that optimal values are attainable at the array values:

All the extremum points will lie in the elements from the any of the arrays because f is convex and at the event points (or the points of array a and b).

For learning more about ternary search, you can see following topcoder discussion

Another smart solution

Please see following comment of goovie and proof is given in the reply by himank

Solutions Code

• ternary search solution
• my solution using 2nd fact
• [user:Gerald] solution
• [user:triveni] solution using smart solution

439E - Devu and Birthday Celebration

There are two possible solutions.

dp solution

Let P(n, f) be total number of ways of partitioning n into f segments such that each a_i is positive. With some manipulations of the generating function, you can find that this is equal to .

So

Let F(n, f, g) denotes partitions of n into f parts such that gcd of all the a_i's is g.

Note that F(n, f, 1) = P(n, f) — sum of F(n, f, g) over all possible gcd g's. So g will be a divisor of n.

In other words,

As .

You can implement this solution by a simple dp.

You can pre-calculate factorials which will help you to calculate .

Complexity of this solution will be nlogn over all the test cases.

Please note that this solution might get time limit exceeded in Java. Please read the comment.

Mathematical solution

Note that F(n, f, 1) = P(n, f) — sum of F(n, f, g) over all possible gcd g's (g > 1 such that g is a divisor of n.

In other words,

As F(n, f, g) = .

Now you have to use Möbius inversion formula.

Theorem:

If f and g are two arithmetic functions satisfying

then

So In our case: g(n) is P(n, f) and f(n) is F(n, f, 1).

For proving complexity: Use the fact that total number of divisors of a number from 1 to n is

Please also see xorfire comment for understanding the relation between mobius function and the solution using inclusion exclusion principle.

Solution Codes

• my solution using mobius function
• [user:Gerald]'s code based on first solution
• [user:Balajiganapathi,2014-06-05]'s inclusion exclusion principle

Hi everyone,

Codeforces round #251 for division 2 participants will start at June 4, Wednesday, 19:30 MSK (usual time). Traditionally we invite Div.1 participants to take part out of the competition.

The round was prepared by me (PraveenDhinwa). This is my first codeforces round. I have tried my best to make the problem statements as clear as possible. I hope that everyone will enjoy the round.

Special thanks to Gerald(Gerald), for his extensive help in problem ideas verification, problem testing, without his help the contest would not have seen the day. English translation is done by me with a lot of help from Gerald Agapov(Gerald). Problems are translated in Russian by Maria Belova(Delinur).

Many thanks to Pratik Moona(pratikmoona), Varun Nitish(JuanMata) for providing their help in testing of round. Their help is greatly appreciated :)

Many thanks to Devendra Agrawal(devu)Utkarsh Lath(utkarshl) to helping me in verifying the ideas of problem statements.

Many thanks to Mike Mirzayanov(MikeMirzayanov) for creating this wonderful platform :)

The contest problems are dedicated to my dear friend Devu (devu), He once proposed problem titled "Churu, the thief". Churu is my nick-name. So it is now time to take some revenge in a funny way :P

Score distribution for the contest is standard: 500-1000-1500-2000-2500.

I have a good news for you too. Tutorial of the contest will be available as soon as the contest ends :).

I wish all the participants good luck, high rating and lot of hacks :) Don't miss the round.

UPD Thank you everyone for participating. I hope that you have enjoyed the round, Thank you all !!

Editorial

#include <bits/stdc++.h>

using namespace std;

int main() {
      double d = 50;
      printf ("%lf\n", d);

      return 0;
}

If I compile it using g++ A.cpp -std=c++0x, output is 0.000000.

If I compile it using g++ A.cpp -std=gnu++0x, output is 50.000000 as desired.

Gives correct answer for using cout in both the cases.

What could be the possible issues? My g++ version is (tdm-1) 4.7.1

EDIT: Based on suggestion of andreyv, I checked using %f, it works correctly. But I dont know the reason for this :(

You are given a string s of size n, consisting of characters A and B only. You have to find minimum sum of size of the two disjoint segments such that number of A's in them are >= z.

Input: string s, n, z are given in the input. Output: minimum sum of size of two disjoint segments with given property

Currently I have a solution of complexity , Can anybody give a better solution than this?

Or can somebody prove that it is somehow related to 3 SUM problem?

You are given n non-negative integers a₁, a₂, , a_n. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference between those integers ie, if the removed integers are b and c, you put |b — c| into the set again. You keep applying the operation until you are left with only a single number, So After n — 1 steps the game will terminate, you need to find out what is maximum value of the single number left in the end after n — 1 such operations.

I am interested in seeing any polynomial time algorithm for the problem, Currently I dont have any idea about how to solve this problem less than .

If you feel that there does not any polynomial time algorithm, could you please establish in which complexity class it lies, Is it NP complete ?

Hi all,

I was using http://polygon.codeforces.com/ for creating some problems. I could not find any option for downloading the html code of the problem statement. Can anybody share some insights into this?

Hey guys,

I want your review about quality of the problems of our local contest held on http://www2.cse.iitk.ac.in/judge/. The problems have been added to spoj. Their ids are ranging from http://www.spoj.com/problems/IITWPC4A/ to http://www.spoj.com/problems/IITWPC4L. Total number of problems are 12.

Actually I wanted to invite users from codeforces in the contest, but I was doubtful about the quality of contest being helpful for them or not. Please guide me in this.

Thank you for reading !!

I had once set problems for Internal contest of our college IIT Kanpur. See link http://www2.cse.iitk.ac.in/judge/public/. I had also added the problems on spoj http://www.spoj.com/problems/IITKWPCA/ to http://www.spoj.com/problems/IITKWPO/. Please Try them :)

I liked the problem C http://www.spoj.com/problems/IITKWPCC/ most. None of the teams was able to solve this during the contest. After adding on spoj, I was expecting that lot of people will try to solve this problem. But not a lot of people have done so. So It kind of looks bad when your most loved problem does not get many users to attempt. So I request you to attempt the problem :). I am sure that you will love it :)

• Using constructors in C++

struct point {
    int x, y;
    point() {} // default constructor
    point (int _x, int _y) {
        x = _x;
        y = _y;
    }
};

Another way

struct point {
    int x, y;
    point() {} // default constructor
    point (int x, int y): x(x), y(y) {}
};

• Using Comparison function in C++. For information of operator overloading visit link

struct point {
    int x, y;
    point() {}
    point (int x, int y) : x(x), y(y) {}
    
    // overloading of < operator
    bool operator<(const point &rhs) const{
        // your main logic for the comparator goes here
        return make_pair(x,y) < make_pair(rhs.x, rhs.y);
    }
};

Now A Sample Implementation

Thanks to Break-Neck for pointing out the problem with earlier a <= b in the code of cmp function, see the comment of Break-Neck comment for more details and also see the well commented cmp function.
You can also view link to know more about strict weak ordering in stl.

// please write your includes do not forget to include vector or direcly use include bits/stdc++.h

bool cmp(int a,int b) {
    return a < b;
    // please view the first comment so as to understand the concept of strict weak ordering to be used in comparison if you want to use std:sort etc functions. Strict weak ordering means that specify the case when a is strictly less than b to true, all other cases to false.
  
}

int main() {
    int n;
    cin >> n;

    vector a;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }

    sort (a.begin(), a.end(), cmp);

    for (int i = 0; i < a.size(); i++)
        cout << a[i] << " ";


    return 0;
}

PS. Please do comment if the article was useful or needs some changes or more explanation.

As you see last Div1 contest was on 15 Oct. Next one is not yet scheduled, it has been around 15 days, isn't this delay unusual?. What are the reasons behind this delay??

The blog is not yet complete. I just mistakenly clicked post button. So it is still in writing, I have to add formatting to it. Sorry for inconvience

Structure of the article. First I will explain what does sieve mean. Then I will give you some examples with corresponding java codes and finally some exercises :)

According to http://www.thefreedictionary.com/sieve , "sieve" means A utensil of wire mesh or closely perforated metal, used for straining, sifting, ricing, or puréeing. Similar to this definition sieve is a method of doing stuff, where you keep rejecting the things that are useless and reducing the space that you are currently looking at.

So much of thing in air, Let us now take an example.

1. Finding primes upto N. You have to print all primes upto N.

Method1 : For all the numbers i from 1 to N, check if i is prime or not. If it is a prime, then print it.

_Subproblem_ :

        Checking whether a number K is prime.

  _Solution_ :

         1. For all numbers i from 2 to K-1, check if K is divisible by i (as every number is divisible by 1 and itself). If yes, then not a prime else the number is a prime.

            Complexity of this solution : O(K)

         2. Note that we do not need to check upto K-1, instead we  can very well check upto sqrt(K).

          Proof: Let us say a number K = a * b. Note that atleast one of a and b <= sqrt(K) otherwise product of them would exceed K. So check just upto sqrt(K).

         3. Either use some probabilistic method for finding whether a number is prime or not.
 More on this later. For now see link

                             http://en.wikipedia.org/wiki/Primality_test
                         http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting

Method 2 :

Now here comes the idea of sieve. So initially assume that all numbers are prime. Then you try to sieve/refine your search range by not looking at the entire numbers but at the reduced space. eg. When you find all the numbers which are divisible by 2, You do not look into those again, as they are already not prime. So those numbers are sieved out. Now try for 3,4, upto n.

  In other terms, You first try all the numbers which are divisible are 2 (except 2 itself),

Note that all those wont be primes. So you can remove those out of your consideration now. Now try the same for 3,4,...... N. Finally you will end up with only prime numbers.

For understanding the actual thing going on, see the code.

 So the code basically sets all the numbers upto N to be prime. Then for every number that is still prime, we set all of its multiples upto N to be non-prime.

import java.io.*; import java.util.*; import java.math.*;

public class Main { static boolean[] isPrime;

public static void sieveOptimized(int N) {
    isPrime = new boolean[N + 1];

    for (int i = 2; i <= N; i++)
        isPrime[i] = true;
    for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
            // For further optimization, You can do instead of j += i, j += (2 * i).
            // Proof is left to reader :)
            for (int j = i * i; j <= N; j += i) 
                isPrime[j] = false;
        }
    }
}


public static void sieve(int N) {
    isPrime = new boolean[N + 1];

    for (int i = 2; i <= N; i++)
        isPrime[i] = true;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            for (int j = i + i; j <= N; j += i) 
                isPrime[j] = false;
        }
    }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int limit = sc.nextInt();

    // call the sieve method
    sieveOptimized(limit);

    for (int i = 1; i <= limit; i++) {
        if (isPrime[i]) 
            System.out.printf("%d ",i);
    }
}

}

Now comes the complexity part: Complexity of this code is O(n * logn).

 _Proof_ : (This proof comes a lot of times in various algorithms, So pay attention).

 For all numbers i going from 2 to n, you need to check all the multiples of i. Note that number of multiples of i upto n are n / i. Hence Expression for the complexity will be written as n / 2 + n / 3 + .. + 1. Take n common out of expression. Now it becomes n * (1 / 2 + ..... + 1/n). 

 Now as the expression is definitely greater than n. So adding an n to the expression won't have any effect on the complexity, So add n to the expression and now it becomes n * (1 + 1 / 2 + ... + 1/ n).  The expression (1 + 1 / 2 + 1 / 3 + ... 1 / n) is harmonic sum and it's bounded by ln(n). Hence overall complexity is O(n * logn)

_ Proof of harmonic sum:_ __ A simple Proof: Let us integrate 1 / x from 1 to n. (Note that we are doing integration, which means sum of area under the curve 1/x, which is greater than (1 + 1 / 2 + ... + 1 / n). Value of the integral can be found easily. In fact integration of 1/x dx is ln(x).

1. Finding Sum of divisors of numbers upto N.

   Now you have to find sum of divisors of all numbers upto N. Here we are not just considering proper divisors(numbers other 1 and itself), we are considering all the divisors. Here you can do something like this.

   Here let us say divisorSum[i] denotes sum of divisors of i. Intially value of divisorSum[i] is equal to zero. Then for all the numbers i from 1 to n, We check all the multiples of i (let us say j) and add i to divisorSum[j].

   In other words, Start from 1 and for all the numbers which are multiples of 1, increment their sumDiviors by 1.

   Now do the same for 2,3, ... N. Note that for a number i, you are doing this adding operation upto N/i times. So the complexity calculation is same as before.

Look the beautifully commented code.

import java.io.*; import java.util.*; import java.math.*;

public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt();

while (T-- > 0) {
        int n = sc.nextInt();
        int divisorSum[] = new int [n + 1];

        // For every number i, You know that 2*i,3*i,4*i   upto k*i such that k*i<=n, will have i 
        // as one of it's divisors, so add that to divisorSum[j]

        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j += i) {
                divisorSum[j] += i;
            }
        }

        // Complexity of this code is O(n * logn)
        // Proof: Expression for the complexity can be written as n / 1 + n / 2 + ... + n / n
        // take n common
        // n * (1 + 1 / 2 + ..... + 1/n)
        // (1 + 1 / 2 + 1 / 3 + ... 1 / n) is harmonic sum and it's bounded by logn.
        // A simple Proof: Let us integrate 1 / x from 1 to n. 
        // (Note that we are doing integration, which means sum of area under the curve 1/x
        // which is greater than (1 + 1 / 2 + ... + 1 / n)
        // value of integration can be found easily
        // as integration of 1/x dx is ln(x)

        for (int i = 1; i <= n; i++) 
            System.out.printf("%d ", divisorSum[i]);

        System.out.printf("\n");
    }
}

}

1. ** Finding No of divisors of numbers upto N.**

   This is also same as the previous example. Here instead of the storing sum in the array, store the number of divisors and for every multiple of i (say j), In the previous example, you were adding value i to divisorSum[j] , Here just increment the count of noOfDivisior[j] by one.
   
   Code is very easy and hence omitted. Complexity is also same.

2. Sieve for finding euler phi function.

   I will denote the euler phi function for a number n by phi(n). phi(n) is defined as follows. It is count of how many number from 1 to n are coprime(having gcd value 1) to n. For example phi(6) is 2 as 1,5 are coprime to 6.

   Few properties of phi function :

   a). phi(p) = p - 1. Where p is prime. All the numbers from 1 to p - 1 are coprime to p.
   
   b). phi(a * b) = phi(a) * phi(b) where a and b are coprime.
   
   c). phi(p^k) = p^k - p^(k - 1). Note that here ^ denotes power. Here all the numbers from 1 to p^k are coprime to p^k except all the multiples of p, which are exactly p^(k -1).

   Method for finding:

   1. Simple : For all numbers from 1 to n, check if it is coprime to n or not, If yes add that to your answer.
   1. Let us say your number is n, which can be denoted as p1^k1 * p2^k2 ..... *p_m*k_m. Note that here p1, p2.... pm are prime. Basically n is written in it's prime representation.

   Then phi(n) would be [ p1^k1 - (p1^(k1-1) ) ] * ....... [p_m^k_m - (p_m^(k_m-1) )] . The expression for n can also be written as p1^k1 * p2^k2 * .... * p_m^k_m * (1 - 1/p1) * (1 - 1/p2) .... * (1 - 1/pm).

which is equal to n * (1 — 1/p1) * (1 — 1/p2) .... * (1 — 1/p_m).

See the code for details.

import java.io.*; import java.util.*; import java.math.*;

public class Main {

public static boolean isPrime (int n) {
    if (n < 2)
        return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}

public static int eulerPhiDirect (int n) {
    int result = n;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i))
            result -= result / i;
    }

    return result;
}

public static int eulerPhi (int n) {
    int result = n;
    // think that it like this, initially all numbers have gcd with n to be equal to 1.
    // Hence value of result is n
    // according to formulla  n * (1 - 1/p1) * (1 - 1/p2) .... * (1 - 1/pm). We will be calculating value 
    // of the product upto i. that is n * (1 - 1/p1) * ... (1 - 1/p_i)
    // So let us take example of p1. value of result after one iteration will be n - n / p1, which is precisly
    // n * (1 - 1/p1). 
    // Similarily by induction hypthesis we can say finally the result will be as required.

    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            result -= result / i;

            // By using while loop here, we are ensuing that all the numbers i will be prime.
            // because for every i, all it's multiples are gets removed.
            while (n % i == 0) {
                n /= i;
            }
        }
    }

    if (n > 1) {
        result -= result / n;
    }

    return result;
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();

    while (T-- > 0) {
        int n = sc.nextInt();

        // call the eulerPhiDirect or eulerPhi method. 
        // culerPhi is more faster as it does not take sqrt(n) for checking for prime

        int ans = eulerPhiDirect (n);
        System.out.println(ans);
    }
}

}

Now Let us calculate value of sieve of all numbers from 1 to N.

Let us say eulerPhi[i] be the value of phi(i). Assign initially all the values of eulerPhi[i] to be i. Then for every prime p, for all multiples of p, we will multiply value of eulerPhi[i] by (1 - 1/p) as per the formula. multiplying eulerPhi[i] by (1 - 1/p) is exactly equal to eulerPhi[i] -= (eulerPhi[i] / p).

import java.io.*; import java.util.*; import java.math.*;

public class Main {

public static boolean isPrime (int n) {
    if (n < 2)
        return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}

private static int[] eulerPhi;

public static void eulerSieve (int N) {
    eulerPhi = new int[N + 1];

    // set initial value of phi(i) = i
    for (int i = 1; i <= N; i++)
        eulerPhi[i] = i;

    // for every prime i, do as described in blog.
    // Note that we are using isPrime(i) function that takes sqrt(n) time. You are advised to write 
    // a seperate sieve of finding primes as described by me.
    // which will reduce the compleixty of this to n * log(n)
    // Proof of this is similar to previous ones. Left to reader.

    for (int i = 1; i <= N; i++) {
        if (isPrime(i))
            for (int j = i; j <= N; j += i)
                eulerPhi[j] -= eulerPhi[j] / i;
    }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();

    eulerSieve(N);

    for (int i = 1; i <= N; i++)
        System.out.printf("%d ",eulerPhi[i]);
}

}

1. Sieve for finding inverse modulo m.

   Inverse of a number a with respect to m is defined as b * a = 1 mod m. Then b is called inverse of a modulo m.

   So first of all do you realize that it is not necessary to exist the inverse? Example for a = 4, b = 6.

   Let us play around the expressions. a * b = 1 mod m can be written as a * b = 1 + m * k. which can be written as a * b — m * k = 1. If the left side has a common factor of both a and m, means gcd(a,m) != 1, then note that right side won't be divisible by that number, Hence no solution of the equation when a and m has gcd non zero. Hence inverse will exist when a and m have non zero gcd.

   Now solving a * b + m * (-k) = 1. write the same as a * b + m * k1 = 1.

   So let us try to find solution of a * b + k * m = 1. This k is not equal to previous k, infact it is -k. It is equal to k1.

   So let us try to solve generic problem a * x + b * y = 1. where a and b can also be negative and gcd(a, b) = 1.

   Let us try a simpler version of the same problem which is solving b * x1 + (a % b) * y = 1;

   Now try to relate these equations. a % b = a — [ a / b] * b. where [] denotes floor function. This is same as removing all multiples of b from a, which is exactly equal to a % b.

   Now the equation turns into b * x1 + (a — [a/b] * b) * y1 = 1

   which is a * y1 + b * (x1 — [a/b] * y1) = 1.

   So this is recursive version of a * x + b * y = 1, where x is replaced with y1 and y is replaced with x1 — [a/b] * y1.

   Things getting really complex. (Note that this method is exactly similar to finding gcd of two numbers). Seeing the code will help you to understand more.)

   Complexity of this code is same as gcd as it has exactly the same recurrence relation as of that. Time complexity of gcd(m, n) is log (max(m , n)). Hence we can consider time complexity of this method around O(logn).

import java.io.*; import java.util.*; import java.math.*;

class pair { public int x, y;

pair (int x,int y) {
    this.x = x;
    this.y = y;
}   

boolean isEquals (pair p) {
    if (this.x == p.x && this.y == p.y) 
        return true;
    else 
        return false;
}

}

public class Main { public static int gcd (int a, int b) { if (b == 0) return a;
return gcd (b, a % b); }

public static pair solve (int a,int b) {
    if (b == 0) {
        // a * x + b * y = 1
        // here b = 0
        // hence a * x = 1
        // if a is not 1, then error else x = 1 and y = 0
        // Note that error wont be here, we will always find a which is not 1
        // as error case is already handle in solveThis function
        return new pair (1, 0);
    } else {
        // do the recursive call
        pair p = solve (b, a % b);
        int x1 = p.x;
        int y1 = p.y;

        int x = y1;
        int y = x1 - (a / b) * y1;

        return new pair (x, y);
    }
}

public static pair solveThis (int a, int b) {
    if (gcd (a, b) != 1)
        // (-1, -1) corresponds to error, that means no inverse exists in this case
        return new pair (-1, -1);
    else 
        return solve (a, b);
}

public static int modpow (long a, long b, long c) {
    long res = 1;
    while (b >= 0) {
        if (b % 2 == 1) {
            res = (res * a) % c;
        }
        a = (a * a) % c;
        b >>= 1;
    }

    return (int) res;
}

public static int findInverseModuloPrime (int a, int p) {
    return modpow (a, p - 2, p);
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int a = sc.nextInt();
    int m = sc.nextInt();

    pair p = solveThis (a, m);

    if (p.isEquals(new pair(-1, -1)))
        System.out.printf("Error, inverse does not exist");
    else 
        System.out.printf("%d %d\n", p.x, p.y);
}

}

Now I will tell you another easier method . Generalized version of Fermat's theorem says that a ^ phi(m) = 1 mod m where gcd(a, m) = 1. Fir finding inverse a ^ (phi(m) — 1) = 1 / a (mod m) = (inverse(a)) mod m.

Hence for finding inverse(a) mod m, You can just find a ^ (phi(m) — 1) by modular exponention method. In case of m being prime, As phi(m) = m — 1. So just find a ^ (m — 2) % m. This is what precisely computed by modpow function in the above function.

Complexity :

Now Sieve for finding inverse modulo m:

You have to find inverse(i) mod m for i ranging from 1 to n. as complexity of modpow is log (n). and we are doing this for n numbers. Hence total complexity will be O(n * logn). Here I am going to describe a better method using sieve

Just use the identitiy inverse(i) = (-(m/i) * inverse(m % i) ) % m + m;

Proof: It is good one. I do not want reveal it now. Try yourself. If you come up with it, post it in the comments, I would check whether it is correct or not?

import java.io.*; import java.util.*; import java.math.*;

public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); // denotes the range upto which you want to find the value of modInverse[i]
    int m = sc.nextInt();

    int modInverse[] = new int[n + 1];

    modInverse[1] = 1; // this is you know 1 * 1 mod m = 1

    for (int i = 2; i <= n; i++) {
        modInverse[i] = (-(m/i) * modInverse[m % i]) % m + m;
    }

    for (int i = 2; i <= n; i++) 
        System.out.printf("%d ", modInverse[i]);
}

}

Finally, Here are some few exercises for you to try

1. http://www.spoj.com/problems/GCDEX/

 I will keep adding the list if I found some problems.

Some time before I had contribution points 70, Now profile is showing only 19.
Am I the only one with whom this has happened ??

I was reading http://www.stanford.edu/class/cs97si/suffix-array.pdf. In problem 6, I am unable to figure out n^2 DP solution. I tried to think about it, but I was not able to reduce it less than simple O(n^3), where state is (i,j,k) -> ans : i is position in S1, j in S2, k in S3.

I feel like that I can optimize it shuffling the state parameters, something like (i,j) -> (k, ans). But I am not able to correctly write the recurrence.

Please help me in finding the O(n*n) solution, If you could tell about the recurrence of above DP states, then I would be very thankful for that.

Can you also suggest similar task, where I could test my implementation ??

Hi, I am unable to find some idea to solve problem http://www.spoj.com/problems/CNTTREE/. I think that this is a dp problem. But no idea how can I find it's states of dp. Could anybody help me with just the state part??

http://mirror.codeforces.com/contest/267/problem/B

Please help me in solving this problem. For me this looks like finding a hamlitonian path in a graph which is NP complete. Any hints for solving the problem ??

Hi all, I am trying to change my Handle. It asks for a password. I do not which password is it asking for ??. I had registered on codeforces through gmail. So I didn't set up special password for codeforces. I tried to enter gmail password. But it does not work. Please help !! Thanks in advance !!

I am trying to solve problem : http://mirror.codeforces.com/contest/54/problem/C I am getting wrong answer on test case no 51. Despite trying for a long time, I am unable to get where I am getting wrong.

My code outputs on this test : -1.#IND00000000000000 , which is quite strange. Link to my solution : http://mirror.codeforces.com/contest/54/submission/2789163

Thanks in advance .

EDIT: problem is solved. Problem was in size in declared array . Wasted a lot of time in debugging the solution rather than looking at it. :(

I recently tried to participate in virtual contest 155 div 2 and 154 div 2. I am getting errors on first problem of both the contest. See my latest unofficial solutions : http://mirror.codeforces.com/submissions/praveendhinwa

In First problem of 154 Div2 A (Boys and Girls) , I am getting memory limit exceeded. In First problem of 155 Div2 A (Cards with Numbers) , I am getting runtime error and wrong answers.

Both these errors are happening in even test case no 1.

Please help!!!

Hi All, Given n circles. (n <= 1000) The problem is to find maximum no of circles can a straight line can intersect.

My idea : For every circle , Take it's tangent , Then rotate it and check the maximum number of intersections it can have with other circles.

Can anybody suggest me some other approach ??

can anybody please How dp is used in question no 112 div 2 E http://mirror.codeforces.com/contest/165/problem/E I tried to understand the approach mentioned in the round blog , I could not understand that . there is no editorial of this round upto .

Thanks in advance !!

Hi guys ,,, Could anybody help me How to solve http://www.spoj.pl/problems/MPOLY/ . I tried to relate it with convex Hull ,, But It did not work . There is a codeforces blog on dp problems ,which suggests it to be a geometry dp problem ,, Any hints please!!!!!! Any kind of help will be appreciated . Thank you.

I want to use template used by some coder . So if I write his name in the top and say this is taken by this coder . Is this against the copyright law .

Please suggest me.