witua's blog

By witua, 10 years ago, translation, In English

CodeChef invites you to participate in the August Cook-off 2014 at http://www.codechef.com/COOK49.

Time: 24th August 2014 (2130 hrs) to 25th August 2014 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

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

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

New users please register here

- Problem Setter : Vitaliy Herasymiv
- Problem Tester and Russian Translator : Sergey Kulik
- Editorialist: Constantin Sokol
- Mandarin Translator: Gedi Zheng & Minako Kojima

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.

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

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

Does anyone have problems with codechef.com?

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

Can someone provide statements at least?

Between, i hate cookoffs due to system issues.

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

Here's one problem that I can see :

Alice and Bob are playing the game. Initially, there is a single rooted tree. Players take turns alternately, Alice starts.

In a single turn, Alice should choose any non-empty subset of roots of tree (or trees) and remove them. On the other hand, Bob should choose any non-empty subset of leafs and remove them from the tree (or trees). It's not allowed to skip the turn. The game ends when a player can't take a turn.

The Alice's goal is to minimize the number of turns made by the both players, while Bob wants this number to be the maximal. Considering they both play optimally, what is the number of turns eventually made? Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N denoting the number of nodes of the tree.

The next N-1 lines contain pairs of nodes' numbers Ui and Vi (one pair per line), denoting the edges of the tree.

The nodes are numbered from 1 to N, inclusive, and the node with the index 1 is the root of the tree. Output

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

1 ≤ T ≤ 40
1 ≤ N ≤ 10000
1 ≤ Ui, Vi ≤ N

Example

Input: 3 2 1 2 7 1 3 1 4 4 2 4 5 4 6 6 7 1

Output: 2 5 1

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

Same here don't know what's wrong with codechef.com.

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

Permutation Shuffle

You are given a permutation of natural integers from 1 to N, inclusive. Initially, the permutation is 1, 2, 3, ..., N. You are also given M pairs of integers, where the i-th is (Li Ri). In a single turn you can choose any of these pairs (let's say with the index j) and arbitrarily shuffle the elements of our permutation on the positions from Lj to Rj, inclusive (the positions are 1-based). You are not limited in the number of turns and you can pick any pair more than once. The goal is to obtain the permutation P, that is given to you. If it's possible, output "Possible", otherwise output "Impossible" (without quotes). Input The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two space separated integers N and M denoting the size of the permutation P and the number of pairs described above. The next line contains N integers — the permutation P. Each of the following M lines contain pair of integers Li and Ri. Output For each test case, output a single line containing the answer to the corresponding test case. Constraints 1 ≤ T ≤ 35 1 ≤ N, M ≤ 100000 1 ≤ Li ≤ Ri ≤ N

Example Input: 2 7 4 3 1 2 4 5 7 6 1 2 4 4 6 7 2 3 4 2 2 1 3 4 2 4 2 3

Output: Possible Impossible

Shooting

You are given a rectangular grid with N rows and M columns. Each its cell is either empty, contains an enemy, or contains a laser. The lasers are capable of shooting. Each one can shoot in one of three directions: either left, right or up.When a laser shoots at some direction, it kills all the enemies on its way. Find out whether it's possible to kill all the enemies on the grid. If it's possible, output "Possible", otherwise output "Impossible". Input The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains the pair of integers N and M denoting the size of the grid. The next N lines contain M characters each. The characters can be one of the following ones: '.' denoting an empty cell. 'E' denoting an enemy. 'L' denoting a laser. Output For each test case, output a single line containing the answer to the corresponing test case. Constraints 1 ≤ T ≤ 10 1 ≤ N, M ≤ 50 The number of lasers will be between 1 and 16, inclusive.

Example Input: 3 2 2 E. L. 2 4 E.EL LL.. 3 3 EE. L.L L..

Output: Possible Possible Impossible

Pant The Tree

You are given a rooted tree with N nodes. You would like to paint each node of the tree in one of three possible colors: red, green, and blue. The following conditions must be fulfilled: For each node painted red, there must be no more than R red nodes in its subtree (including this node). For each node painted green, there must be no more than G green nodes in its subtree (including this node). For each node painted blue, there must be no more than B blue nodes in it's subtree (including this node). Find the number of ways to paint the tree and output it modulo 1000000007. Input The first line contains four integers N, R, G and B. The following N-1 lines contain pairs of the nodes' numbers Ui and Vi (one pair per line), describing the edges of the tree. The nodes are numbered from 1 to N, inclusive, and the node with the index 1 is the root of the tree. Output Output the answer to the problem on the first line. Constraints 1 ≤ N ≤ 300 0 ≤ R, G, B ≤ 300

Example Input #1: 3 1 1 1 1 2 3 1

Output #1: 12 Input #2: 8 2 1 3 1 2 1 4 5 4 7 4 3 2 4 6 8 6

Output #2: 613

Count Digits

You are given an integer N. For each pair of integers (L, R), where 1 ≤ L ≤ R ≤ N you can find the number of distinct digits that appear in the decimal representation of at least one of the numbers L L+1 ... R. Find the sum of all that numbers. Since the answer can be large, output it modulo 1000000007. Input The only line of the input contains a single integer N without leading zeros. Output Output the answer to the problem on the first line. Constraints 1 ≤ N ≤ 10100

Example Input: 7

Output: 84

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

    Time limits: 2sec, 1sec, 1sec, 3sec

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

      Are they real statements? Does it not provide an advantage for codeforces users?

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

        Better than just providing an advantage to people who were lucky enough to open a problem. And a huge ethical plus for the poster.

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

    At counting digits limit is 10^100 or 10,100?

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

This is ridiculous, why I have to wait half an hour for a reply on my question (which is crucial for solving the problem)...

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

    but i don't see any question posted by u?
    EDIT: oops, i got trolled! :D

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

      Exactly! It hasn't even been approved by the moderator.

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

      The funniest thing is that I have to debug two programs because both give WA. :D

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

        @gen what is your id on codechef?

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

          jevi

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

            I am surprised that your comment was not published, I had myself asked problem setter to reply to this comment. Probably it was not answered due to mis-communication on our part. Really sorry for it :(

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

Ow. The second hardest problem is of the type I hate: taking care of special cases arising from zeroes and the number of digits having to satisfy some constraint. That in itself would be manageable, but if I make a mistake somewhere, it takes a long time to find it because there are so many independent parts of the code where it could be.

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

    Pretty much...

    Time to code: ~40 min Time to debug: ~1h 30min

    (These are unfortunately real statistics :( ).

    Edit: tourist's code looks pretty special case free due to his excellent state choice. I'm not that good, though.

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

502 Bad Gateway!!

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

Hi. I asked a question on codechef.com, but there are still no answers.

http://discuss.codechef.com/questions/50210/problems-with-java

I've tried to send several solutions on Java, but there always was NZEC verdict. I wasn't able to make any Java solution get AC. But the C++ and C# ones are okay. So.. I hope that somebody could explain me, what I do wrong using Java on codechef. Thanks.