So, if you can't understand what author of the problem meant, you're not alone :o)

He meant the following: chukcha goes from A to B and he covers each K kilometers in H hours. But the speed whithin this interval is not constant: he can cover K minus eps kilometers within first second of H hours and remaining eps kilometers in the remaining time (and visa versa).

It leads to the problem itself: what speed distribution along the interval leads to the minimum time to reach destination and what distribution leads to maximum time.

как понимать _минимальное_ и _максимальное_ время ???

Edited by author 01.11.2009 13:12

why taking the biggiest fraction of remain assure that the church gets the minimized?

If you decide not to repeat my mistake, then the 49th check is that the king must bypass the black pawn in order to catch up with the white one, I will not talk further, but just give you an example:
8
a3 d7 e6
Answer:BLACK WINS

Try:
2
Correct answer is 2 1

Main idea is to split cube into 8 parts and query/add for each one.
Here is my code that have TL6.
Any ideas of how to improve it?

import java.io.*;

public class P1470 {
    static int [] tree = new int[10000000];
    private static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

        n = Integer.valueOf(reader.readLine());

        while (true) {
            String line = reader.readLine();
            if (line.startsWith("1")) {
                add(new Ufo(line));
            } else if (line.startsWith("2")){
                writer.println(query(new Region(line)));
            } else {
                break;
            }
        }
        writer.flush();
    }

    private static int query(Region region) {
        return doQuery(region, new Region(0, 0, 0, n - 1, n - 1, n - 1), 0);
    }

    private static int doQuery(Region q, Region r, int node) {
        if (!r.overlaps(q)) return 0;
        if (q.contains(r)) {
            return tree[node];
        }
        int xMid = (r.x1 + r.x2) / 2;
        int yMid = (r.y1 + r.y2) / 2;
        int zMid = (r.z1 + r.z2) / 2;

        return
            doQuery(q, new Region(r.x1, r.y1, r.z1, xMid, yMid, zMid), node * 8 + 1) +
            doQuery(q, new Region(xMid + 1, r.y1, r.z1, r.x2, yMid, zMid), node * 8 + 2) +
            doQuery(q, new Region(xMid + 1, r.y1, zMid + 1, r.x2, yMid, r.z2), node * 8 + 3) +
            doQuery(q, new Region(r.x1, r.y1, zMid + 1, xMid, yMid, r.z2), node * 8 + 4) +
            doQuery(q, new Region(r.x1, yMid + 1, r.z1, xMid, r.y2, zMid), node * 8 + 5) +
            doQuery(q, new Region(xMid + 1, yMid + 1, r.z1, r.x2, r.y2, zMid), node * 8 + 6) +
            doQuery(q, new Region(xMid + 1, yMid + 1, zMid + 1, r.x2, r.y2, r.z2), node * 8 + 7) +
            doQuery(q, new Region(r.x1, yMid + 1, zMid + 1, xMid, r.y2, r.z2), node * 8 + 8);
    }

    private static void add(Ufo ufo) {
        doAdd(ufo, new Region(0, 0, 0, n - 1, n - 1, n - 1), 0);
    }

    private static void doAdd(Ufo ufo, Region r, int node) {
        if (!r.contains(ufo)) return;

        tree[node] += ufo.count;

        if (r.isPoint()) return;

        int xMid = (r.x1 + r.x2) / 2;
        int yMid = (r.y1 + r.y2) / 2;
        int zMid = (r.z1 + r.z2) / 2;

        doAdd(ufo, new Region(r.x1, r.y1, r.z1, xMid, yMid, zMid), node * 8 + 1);
        doAdd(ufo, new Region(xMid + 1, r.y1, r.z1, r.x2, yMid, zMid), node * 8 + 2);
        doAdd(ufo, new Region(xMid + 1, r.y1, zMid + 1, r.x2, yMid, r.z2), node * 8 + 3);
        doAdd(ufo, new Region(r.x1, r.y1, zMid + 1, xMid, yMid, r.z2), node * 8 + 4);
        doAdd(ufo, new Region(r.x1, yMid + 1, r.z1, xMid, r.y2, zMid), node * 8 + 5);
        doAdd(ufo, new Region(xMid + 1, yMid + 1, r.z1, r.x2, r.y2, zMid), node * 8 + 6);
        doAdd(ufo, new Region(xMid + 1, yMid + 1, zMid + 1, r.x2, r.y2, r.z2), node * 8 + 7);
        doAdd(ufo, new Region(r.x1, yMid + 1, zMid + 1, xMid, r.y2, r.z2), node * 8 + 8);
    }

    static class Region {
        int x1, y1, z1, x2, y2, z2;

        Region(String s) {
            String[] split = s.split("\\s");
            x1 = Integer.valueOf(split[1]);
            y1 = Integer.valueOf(split[2]);
            z1 = Integer.valueOf(split[3]);
            x2 = Integer.valueOf(split[4]);
            y2 = Integer.valueOf(split[5]);
            z2 = Integer.valueOf(split[6]);
        }

        Region(int x1, int y1, int z1, int x2, int y2, int z2) {
            this.x1 = x1;
            this.y1 = y1;
            this.z1 = z1;
            this.x2 = x2;
            this.y2 = y2;
            this.z2 = z2;
        }

        boolean contains(Ufo ufo) {
            return ufo.x >= x1 && ufo.x <= x2 && ufo.y >= y1 && ufo.y <= y2 && ufo.z >= z1 && ufo.z <= z2;
        }

        boolean contains(Region r) {
            return overlaps(r) && x1 <= r.x1 && x2 >= r.x2 && y1 <= r.y1 && y2 >= r.y2 && z1 <= r.z1 && z2 >= r.z2;
        }

        boolean overlaps(Region r) {
            return r.x1 <= x2 && r.x2 >= x1 && r.y1 <= y2 && r.y2 >= y1 && r.z1 <= z2 && r.z2 >= z1;
        }

        boolean isPoint() {
            return x1 == x2 && y1 == y2 && z1 == z2;
        }
    }

    static class Ufo {
        int x, y, z, count;

        Ufo(String s) {
            String[] split = s.split("\\s");
            x = Integer.valueOf(split[1]);
            y = Integer.valueOf(split[2]);
            z = Integer.valueOf(split[3]);
            count = Integer.valueOf(split[4]);
        }
    }
}

How can i improve my O(n ^ 2 * logN) time and O(n * n) memory too pass all tests?
int n, y[2004], index = 1, maximum = 1, rati;
pair<int, int> x[2004];
map<int, int> s[2004];
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x[i].first;
        x[i].second = i;
        y[i] = 1;
    }
    sort(x, x + n);
    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j < i; j++){
            if(y[i] < s[j][x[i].first - x[j].first] + 2 && x[i].first - x[j].first != 0){
                y[i] = s[j][x[i].first - x[j].first] + 2;
                if(maximum < y[i]){
                    index = i;
                    maximum = y[i];
                    rati = x[i].first - x[j].first;
                }
            }
            s[i][x[i].first - x[j].first] = s[j][x[i].first - x[j].first] + 1;
        }
    }
    cout << maximum << "\n";
    int val = x[index].first, i;
    cout << x[index].second + 1 << " ";
    for(i = index - 1; i >= 0; i--)
    {
        if(val - x[i].first == rati && rati != 0)
        {
            val = x[i].first;
            cout << x[i].second + 1 << " ";
        }
    }
    return 0;
}

Number of zeros in bracket:  0     1     2      3      4
Sequence                  : (1)   (10)  (100)  (1000)  (10000)
1 is found at             : T0+1   T1+1  T3+1   T4+1    T5+1
Value of Ti+1             : 0+1    1+1   3+1    6+1     10+1

The i-th triangular number is the sum of the i natural numbers from 1 to i.

Ti = i(i+1)/2

i-th '1' is located at (Ti+1)-th position.
Let, z = (Ti + 1) = (i(i+1)/2) + 1
-> z = (i^2 + i + 2)/2
-> 2z = i^2 + i + 2
-> (1)x(i^2) + (1)x(i^1) + (-2(z-1)x(i^0) = 0
So, now if we solve for i using quadratic formula,
 i = (-1 +- squareRoot(8z-7))/2 [do calculation on your own]
z = {1,2,4,7,11,...}
plugin these values and you will find that squareRoot(8z-7) = an integersquare number for any z. So, a number belongs to z only and if only squareRoot(8z-7) can produce an integer. And here z is the position number where the digits are 1.

[code deleted]

Edited by author 24.12.2020 19:00

Edited by moderator 14.02.2021 18:16

Бред. В самом деле, достаточно искать символ, который чаще всего встречается....

Please, think about the problem yourself at first!
I think you could use this problem to exercise your heuristics and optimization skills and thus I'm sharing a solution that is both easy to think and implement so that somebody less experienced might learn new strategies in optimization problems.


//////


Yes, it's a Vehicle Routing Problem, as even confirmed by the author on this forum.

Firstly, you can compute —with Dynamic Programming— optimal distance visiting some subset of nodes starting at node 0 and ending at some other node. Let dp[S][last] be the state of such DP, which computes the smallest path cost that visits each vertex of S once and starts at 0 and ends at last. This is a classic TSP DP problem that can be computed in O(N^2 2^n). Note, that you have to use a type shorter than 32-bit to store the DP. The cost of a trip is then dp[S][last] + D(last, 0).

Generate a starting solution that performs a trip for each lorry, M trips in total.

So far, nothing a beginner cannot do!

Perform heuristic search to improve it.
I used a Large Neighbourhood Search heuristic.
Remove some number of lorries from trips from the CURRENT_SOLUTION and try to insert them one by one again. That is, greedily calculate the cost of insertion, using DP, of each lorry in each trip —or creating a new trip— and choose the lorry and a trip with smallest possible value.
Decide if the obtained repaired solution is the new CURRENT_SOLUTION. I implemented this decision using Simulated Annealing, but you can simply do it if the repaired solution has a better cost.
If the CURRENT_SOLUTION is better than the BEST_SOLUTION, well, you know what to do!
I started from the small number of removed lorries and gradually increased it if after some iterations there weren't an update to the BEST_SOLUTION. This is a gradual increase of Neighbourhood.


In fact, my solution is terribly inefficient, and I could use better data representation and save time making some calculations, improved heuristic by adding more complex rules, and perhaps get rid of the DP step in favor of simple random greedy insertions. But, I just decided to keep things simple.

0 0 0
1 0 0
2 1 1
2 2 1
ans Invalid
Совет для тех кто решает векторами, лично у меня не получилось сдать задачу векторами, пришлось писать уравнения прямой в пространстве

49 9
9 9 9 9 9 14 14 34 34 34 34 34 42 42 42 42 42 47 49 57 66 68 68 68 68 71 71 71 71 71 74 74 97 97 97 97 97 97 97 100 100 100 100 100 100 100 100 100 100
227 235 264 292 298 322 327 341 820

Can anybody post DP approach, if any exists?

Why would I move the hand to another box? We only have to put pieces in their places, we don't have to put our hand anywhere into the box.

Hi there!
Here is my code for this task: https://notabug.org/thrashzone_ua/c_examples/src/master/rock_heap.c

Short notes:
1) Cases when there is one or two rocks from input are separated
2) In case amount of rocks is more then 2, I'm checking if there is a sublist in list of rocks with sum(sublist) = sum(list) / 2. If there is such a sublist and the number of sum is even - 0 will be printed, if number is not even - 1;
3) In case there no such sublist - it's time for greedy algorithm.

Could you please take a look and comment my code? Or maybe provide with test set, on which it will fail?

Thank you in advance.

Пишу на C#:
using System;

namespace Timus_Console
{
    class Program
    {
        static void Main(string[] args)
        {
            int ans1 = Convert.ToInt32(Console.ReadLine());
            int ans2 = Convert.ToInt32(Console.ReadLine());
            int st = ans1 + ans2;
            Console.WriteLine(st);
            Console.ReadKey();
        }
    }
}

Edited by author 25.03.2016 11:48

Could some one advise regarding the test 16? As far as I can get my solutions works properly nontheless it fails on the test.

Edited by author 16.12.2020 13:34

Edited by author 16.12.2020 13:37

For those who has WA4 or WA7

Test #1:
20 10
3
94 3 3 18
36 7 1 10
73 2 15 19

Answer: 1


Test #2:
7 2
11
6 1 4 1
9 2 5 1
8 3 1 2
7 1 4 2
10 1 7 2
4 2 5 3
99 3 1 5
85 3 4 5
100 1 7 5
100 1 7 6
100 1 7 7

Answer: 4


Test #3:
55 14
87
84 26 14 12
24 14 41 27
85 6 42 18
42 5 49 44
54 1 13 40
85 1 55 17
77 1 9 55
34 5 15 50
31 1 32 55
18 2 54 45
59 8 26 44
79 3 43 52
72 4 51 51
101 5 34 46
35 1 52 18
31 8 47 3
92 1 20 38
10 2 50 1
46 2 5 51
10 2 48 13
92 3 21 52
84 1 12 55
58 2 11 17
24 1 46 54
74 1 30 9
32 2 54 43
29 3 28 52
23 2 1 41
89 1 19 44
49 2 53 1
52 2 40 1
77 6 1 33
44 1 42 9
28 1 52 16
53 1 9 52
74 1 42 2
16 1 37 54
27 1 40 55
72 6 3 21
58 1 13 55
9 1 44 55
37 2 50 23
51 7 21 2
6 1 34 43
27 5 39 43
16 1 40 54
63 2 2 54
93 1 7 55
63 2 13 9
12 1 18 55
94 1 54 12
34 2 41 54
91 1 12 47
99 1 55 27
97 4 25 40
70 1 55 29
21 1 39 54
42 1 9 41
89 1 31 53
84 2 50 17
93 1 14 55
81 4 7 36
68 1 55 14
84 2 7 43
51 1 21 55
85 3 53 23
46 6 1 44
49 2 3 28
42 1 20 53
58 1 53 13
15 2 54 21
59 2 47 50
94 1 17 55
28 2 40 25
49 2 48 54
88 1 55 32
55 4 17 8
47 4 3 17
41 3 49 20
7 1 52 20
67 1 49 52
33 1 38 55
85 5 3 4
23 3 21 45
19 3 11 50
36 1 2 39
67 8 31 1

Answer: 24


Good Luck!