anudeep2011's blog

By anudeep2011, 10 years ago, In English

CodeChef invites you to participate in the January Cook-off 2015 at codechef.com/COOK54.



Time: 18th January 2015 (2130 hrs) to 19th January 2015 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: codechef.com/COOK54/

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

New users please register here

- Problem Setter : Anupdeep Nekannti
- Problem Tester and Mandarin Translator: Minako Kojima
- Russian Translator : Sergey Kulik
- Editorialist: Lalit Kundu

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. Have you tried the new Code, Compile & Run feature on CodeChef? Try it here

  • Vote: I like it
  • +51
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it +41 Vote: I do not like it

502 Bad Gateway

  • »
    »
    10 years ago, # ^ |
    Rev. 4   Vote: I like it +26 Vote: I do not like it

    Same here

    UPD: 503 Internal Server Error now.

    UPD1: Managed to get to the contest page. Now trying to open the problems

    Links (If you have any luck just post the problem) :

    http://www.codechef.com/COOK54/problems/ANUBTG http://www.codechef.com/COOK54/problems/ANUTHM http://www.codechef.com/COOK54/problems/ANUAAA http://www.codechef.com/COOK54/problems/ANURRZ http://www.codechef.com/COOK54/problems/ANUAHR

    Managed to open the first problem:

    Problem 1:

    It is winter super sale and all the shops have various offers. Suraj selected N items to buy and he is standing in the billing queue. It was then he noticed the offer "Buy two, get two". That means for every two items you buy, they give you two items for free. However, items can be of varying price, they always charge for 2 most costly items and give other 2 as free. For example, if the items cost 1, 1, 2, 2, then you have to pay 4 and take all 4 items.
    
    Suraj is busy reordering his items to reduce the total price he has to pay. He can separate the items and get them on different bills if needed. Can you tell me what is the least price Suraj has to pay to buy all the N items?
    
    
    Input
    The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. First line of each test case has single integer N. Second line of each test case has N space separated integers, which are the costs of items Suraj want to buy.
    
    
    Output
    For each test case, output a single line containing the required answer.
    
    
    Constraints
    
    1 ≤ T ≤ 1000
    
    1 ≤ N ≤ 1000
    
    1 ≤ Cost of items ≤ 1000
    
    Example
    
    Input:
    3
    4
    1 1 2 2
    2
    10 200
    7
    1 1 10 2 2 2 1
    
    Output:
    4
    210
    14
    Explanation
    Example case 1
    Suraj pays for 2 costly items and gets other 2 for free.
    Example case 2
    Suraj has to pay for both the items, he wont get anything for free.
    Example case 3
    Suraj separates the items into 2 bills. In one bill he pays 12. And in another bill he pays 2.
    
  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    as usual

    gif

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    503 Server cannot process your request. Please try again. You may be exceeding the number of request's limit or our server is too busy.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same :/

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will this contest be rated ? cook-off page has not yet loaded :'(

»
10 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I love such kind of contests :) Just waiting for site to be up :)

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

ANUTHM ****

As a holiday gift, Tojo received a probability problem. The problem read as follows Consider an N by M grid. Rows are numbered 1 to N, from top to bottom. Columns are numbered 1 to M, from left to right. You are initially at cell (1, 1) and want to go to cell (N, M). From any cell you can move to the cell below it or to the cell right to it. You should never go out of the grid. At any point you should consider all the possibilities of movement with equal probability Let P[i][j] be the probability of visiting cell (i, j). You need to calculate the sum of P[i][j] for 1 ≤ i ≤ N, 1 ≤ i ≤ M. As we all know, Tojo really hates probability related problems. He wants you to solve this task Input The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.Only line of each test case has two integer N and M. Output For each test case, output a single line containing the required answer. Answers within an absolute or relative error of 10-6 will be accepted. Constraints 1 ≤ T ≤ 1000 1 ≤ N ≤ 1000 1 ≤ M ≤ 1000 Example Input: 2 2 2 1 6

Output: 3.000000 6.000000 Explanation Example case 1 Probability matrix P for N=2, M=2 is 1.0 0.5 0.5 1.0 You are at (1, 1) initially. So the probablity of visiting (1, 1) is 1. At (1, 1) you have 2 options, move below to (2, 1) or to right cell (1, 2). Probablity of going to (1, 2) is 0.5. Probability of going to (2, 1) is 0.5. You always end up at (2, 2), so P[2][2] is 1. Required sum = 1.0 + 0.5 + 0.5 + 1.0 = 3.0 Example case 2 Probability matrix P for N=1, M=6 is 1.0 1.0 1.0 1.0 1.0 1.0 Because at any position there is only one possible next position.

»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I think my participation in this contest is over before it started. GL & HF

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sad to hear that, I wish codechef handled the load. :(

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      30 minutes have passed. It's too much. :((

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        It is working now, just in case :)

        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          It's not working. At least for me.

      • »
        »
        »
        »
        10 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Managed to get all problems loaded. Keep trying.


        Nevermind, this is hopeless

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

ANUAHR

Read problems statements in Mandarin Chinese and Russian as well. Problem description

Abhijeet loves to play with rectangles. Today he has N rectangles of various sizes with him. He started to arrange them on the coordinate plane such that the area of intersection is maximized. However, he never rotated the rectangles he had, he only moved them here and there.

Abhijeet soon realized that the game was boring and decided to introduce a modification. He decided to remove atmost M of those rectangles and arrange others on coordinate plane such that the area of intersection is maximized.

Given the dimensions of N rectangles and M, can you answer maximum possible area of intersection with above rules?

Note: If all the rectangles are removed, the area of intersection is considered as 0. Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.First line of each test case has two integer N and M. N lines follow, each has two integers representing the length and breadth of the rectangle. Output

For each test case, output a single line containing the required answer. Constraints

1 ≤ T ≤ 105
1 ≤ N ≤ 105
0 ≤ M ≤ N
1 ≤ Rectangle Dimensions ≤ 109
1 ≤ Sum of N over all test cases ≤ 106

Example

Input: 3 1 1 10 10 2 0 5 10 5 5 2 1 1 1 2 2

Output: 100 25 4

Explanation

Example case 1

Abhijeet has only one rectangle. He can remove it, but then the area will be 0. Optimal way is not to remove it. Area = 10 * 10 = 100

Example case 2

Abhijeet cannot remove any rectangles in this case. He can however, place them such that the smaller 5 by 5 rectangle is completely inside the larger 5 by 10 rectangle. Then the area of intersection is 5 * 5 = 25

Example case 3

Abhijeet can remove atmost 1 rectangles in this case. He can remove the smaller rectangle of size 1 by 1. He is then left with 2 by 2 rectangle of area 4.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anup at Amrithapuri Anup recently visited Amrithapuri for ACM ICPC regional contest. A student walked up to Anup, gave him a paper which had a long programming question on it and asked him to solve it by 18th of January, 2015. As Anup was busy with school kids, he posted the question as cook off question, asking wider community to solve that question. Following is the question: function f(A[0..N-1], L, R, P): if L > R: return f(A, R, L, P) ANSWER = 0 C[] = A[L..R] for each subset S of C: G = GCD(S) for each prime factor PF of G: if PF == P: ANSWER = MAX(ANSWER, SIZE(S)) return ANSWER Clarifications: Line 5 loops over all 2^(R-L+1) subsets. GCD(S) returns the Greatest common divisor of all the elements in S. SIZE(S) returns the number of elements in S. Given: N, M, A[0..N-1], B[0..M-1] Required: Image: https://codechef_shared.s3.amazonaws.com/download/COOK54/ANUAAA_1.gif) Where L = (B[i] + B[j]) % N R = (B[i] - B[j] + N) % N As the answer can be large. Output it modulo 1000000007. Input First line has two integer N and M. Second line has N space separated integers representing the array A. Third line has M space separated integers representing the array B. Output Output single integer which is the required answer modulo 1000000007 Constraints 1 ≤ N ≤ 100000 1 ≤ M ≤ 500 1 ≤ A[i] ≤ 100000 0 ≤ B[i] < N Example Input: 5 2 1 2 3 4 5 1 2 Output: 34 Explanation Here are the answers of few calls to function f() f(A, 2, 0, 2) = 1 f(A, 2, 0, 5) = 0 f(A, 3, 4, 2) = 1
»
10 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem ANURRZ

Rudreshwar likes random numbers and random arrays. Today Rudreshwar started playing with a couple of Arrays A and B, each of size N. Initially A is filled with zeros. Rudreshwar filled B with random numbers. Rudreshwar visits each index i (1 <= i <= N) in random order. When at i, he selects another random index j such that j is greater or equal to i. He then increments A[i], A[i+1], A[i+2] ... A[j] by 1. Finally if for any index i, A[i] is greater than B[i], he then throws away that array A For a given B, calculate the number of different arrays A, that Rudreshwar can end up with. Two arrays are called different if there exists an index where the arrays have different values

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. First line of each test case contains an integer N. Second line contains N space separated integers representing the array B

Output

For each test case, output a single line containing the required answer modulo 1000000007.

Constraints

1 ≤ T ≤ 100 1 ≤ N ≤ 1000 1 ≤ B[i] ≤ N Example

Input: 2 2 2 2 3 1 1 1

Output: 2 1

Explanation

Test case 1 {1, 1} and {1, 2} are valid. Test case 2 {1, 1, 1} is the only possible final array A.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

45 minutes 502/503 BG error. It's fail :(

But problems is fine, I like ANUAHR.

P.S. ( FOR RUSSIANS ) under Amazon VPN also 503, It isn't sanctions problems.

»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

its up and working fine now.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Cannot submit problems: error 503.