[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2
Автор Сообщение
[Post] 11.04.2017 07:37:50
   Тема: Re:Описания решений задач IOI 2010 - ...
[#] [Up]
Михаил Долинский

Темы: 2072
Сообщений: 49927

Мой профиль


Гуленко Алексей:

railroads: перебор > ДП > граф (существование Эйлерова цикла с допущениями) > граф (#3 + минимальное основное дерево по компонентам) 


Паскаль:

1.

view source
print?
01.Unit Railroad;
02.{Mode ObjFPC}
03.Interface
04.  TYPE
05.    TInts  = Array of LongInt;
06.    TBools = Array of Boolean;
07. 
08.  Function Plan_Roller_Coaster (S, T : TInts): Int64;
09. 
10.Implementation
11.  Uses
12.    Math;
13. 
14.  Function FindMin (Len : QWord;  Speed, N : LongWord;  Const S, T : TInts;
15.      Var Used : TBools): Int64;
16.  Var
17.    X           : Int64;
18.    i, D        : LongWord;
19.    Found       : Boolean;
20.  Begin
21.    Found := False;
22.    For i:=0 To N-1
23.      Do If not Used[i] Then Begin
24.        Used[i] := True;
25.        D := 0;
26.        If S[i] < Speed
27.          Then D := Speed-S[i];
28.        X := FindMin(Len+D, T[i], N, S, T, Used);
29.        If not Found Then Begin
30.          Found := True;
31.          Result := X;
32.        End Else Result := Min(Result, X);
33.        Used[i] := False;
34.      End;
35.    If not Found
36.      Then Exit(Len);
37.  End;
38. 
39.  Function Plan_Roller_Coaster (S, T : TInts): Int64;
40.  Var
41.    Used        : TBools;
42.    N           : LongWord;
43.  Begin
44.    N := Length(S);
45.    SetLength(Used, N);
46.    FillChar(Used[0], N*SizeOf(Used[0]), False);
47.    Exit( FindMin(0, 0, N, S, T, Used) );
48.  End;
49. 
50.END.


2. 
view source
print?
01.Unit Railroad;
02.{$Mode ObjFPC}
03.Interface
04.  TYPE
05.    TInts  = Array of LongInt;
06. 
07.  Function Plan_Roller_Coaster (S, T : TInts): Int64;
08. 
09.Implementation
10.  Uses
11.    Math;
12. 
13.  CONST
14.    MaxN = 16;
15. 
16.  Operator In (Const i, Mask : LongWord): Boolean;   Inline;
17.  Begin
18.    Exit((Mask-1) and (1 shl (i-1)) > 0);
19.  End;
20. 
21.  Function Plan_Roller_Coaster (S, T : TInts): Int64;
22.  Var
23.    D                   : Array of Array [1..MaxN] of QWord;
24.    D1                  : QWord;
25.    NN, Mask, Mask1     : LongWord;
26.    N, i, j             : Byte;
27.  Begin
28.    N := Length(S);
29.    NN := 1 shl N;
30.    SetLength(D, NN);
31.    FillChar(D[0], NN*SizeOf(D[0]),77);
32.    For i:=1 To N
33.      Do D[1 shl (i-1)][i] := 0;
34.    For Mask:=1 To NN
35.      Do For i:=1 To N
36.        Do If (i in Mask)
37.          Then For j:=1 To N
38.            Do If not (j in Mask) Then Begin
39.              D1 := D[Mask-1][i] + Max(0, T[i-1] - S[j-1]);
40.              Mask1 := (Mask-1) or (1 shl (j-1));
41.              If D[Mask1][j] > D1
42.                Then D[Mask1][j] := D1;
43.            End;
44.    Result := A[NN-1][1];
45.    For i:=2 To N
46.      Do Result := Min(Result, A[NN-1][i]);
47.  End;
48. 
49.END.


3.
view source
print?
001.Unit Railroad;
002.{$Mode ObjFPC}
003.Interface
004.  TYPE
005.    TInts  = Array of LongInt;
006. 
007.  Function Plan_Roller_Coaster (S, T : TInts): Int64;
008. 
009.Implementation
010.  CONST
011.    MinX  =              1;
012.    MaxX  = 1000*1000*1000;
013.   
014.  CONST
015.    Yes = 0;
016.    No  = 1;
017. 
018.  TYPE
019.    TDSF = Object
020.      Id, Rank  : TInts;
021.      Size      : LongWord;
022.      Constructor Create (N : LongWord);
023.      Function Get (U : LongWord): LongWord;
024.      Function Merge (U, V : LongWord): Boolean;
025.    End;
026. 
027.  Constructor TDSF.Create (N : LongWord);
028.  Var
029.    i   : LongWord;
030.  Begin
031.    Size := N;
032.    SetLength(Id, N);
033.    SetLength(Rank, N);
034.    For i:=1 To N Do Begin
035.      Id[i-1] := i-1;
036.      Rank[i-1] := 0;
037.    End;
038.  End;
039. 
040.  Function TDSF.Get (U : LongWord): LongWord;
041.  Begin
042.    If Id[U] <> U
043.      Then Id[U] := Get( Id[U] );
044.    Exit( Id[U] );
045.  End;
046. 
047.  Function TDSF.Merge (U, V : LongWord): Boolean;
048.  Begin
049.    U := Get(U);   V := Get(V);
050.    If U = V
051.      Then Exit(False);
052.    If Rank[U] = Rank[V]
053.      Then Inc( Rank[U] );
054.    If Rank[U] < Rank[V]
055.      Then Id[U] := V
056.      Else Id[V] := U;
057.    Dec(Size);
058.    Exit(True);
059.  End;
060. 
061.  Procedure ToSet (Var A : TInts);
062.  Var
063.    B   : TInts;
064.   
065.    Procedure _Add (Var i, k : LongWord);
066.    Begin
067.      A[k] := B[i];
068.      Inc(i);   Inc(k);
069.    End;
070.   
071.    Procedure _Sort (L, R : LongWord);
072.    Var
073.      i, j, k, C        : LongWord;
074.    Begin
075.      If L >= R
076.        Then Exit;
077.      C := (L+R) div 2;
078.      _Sort(L, C);
079.      _Sort(C+1, R);
080.      For k:=L To R
081.        Do B[k] := A[k];
082.      k:=L;   i:=L;   j:=C+1;
083.      While (i <= C) and (j <= R)
084.        Do If B[i] <= B[j]
085.          Then _Add(i, k)
086.          Else _Add(j, k);
087.      While i <= C Do _Add(i, k);
088.      While j <= R Do _Add(j, k);
089.    End;
090.   
091.  Var
092.    i, j        : LongWord;
093.  Begin
094.    SetLength(B, Length(A));
095.    _Sort(0, Length(A)-1);
096.    j := 1;
097.    For i:=2 To Length(A)
098.      Do If A[i-1] > A[j-1] Then Begin
099.        A[j] := A[i-1];
100.        Inc(j);
101.      End;
102.    SetLength(A, j);
103.  End;
104. 
105.  Function Find (Const Points : TInts;  X : LongWord): LongWord;
106.  Var
107.    L, R        : LongWord;
108.  Begin
109.    L := 0;
110.    R := Length(Points);
111.    While L+1 < R
112.      Do If Points[(L+R) div 2] > X
113.        Then R := (L+R) div 2
114.        Else L := (L+R) div 2;
115.    Exit(L);
116.  End;
117. 
118.  Function Plan_Roller_Coaster (S, T : TInts): Int64;
119.  Var
120.    DSF                 : TDSF;
121.    Points, D           : TInts;
122.    Opened              : LongInt;
123.    N, M, i, U, V       : LongWord;
124.  Begin
125.    N := Length(S);
126.    SetLength(S, N+1);   S[N] := MaxX;
127.    SetLength(T, N+1);   T[N] := MinX;
128.    SetLength(Points, 2*N+2);
129.    M := 0;
130.    For i:=0 To N Do Begin
131.      Points[M] := S[i];
132.      Points[M+1] := T[i];
133.      Inc(M, 2);
134.    End;
135.    ToSet(Points);
136.    M := Length(Points);
137.    DSF.Create(M);
138.    SetLength(D, M);
139.    FillChar(D[0], M*SizeOf(D[0]), $00);
140.    For i:=0 To N Do Begin
141.      U := Find(Points, S[i]);   V := Find(Points, T[i]);
142.      DSF.Merge(U, V);
143.      Inc( D[U] );
144.      Dec( D[V] );
145.    End;
146.    Opened := 0;
147.    For i:=1 To M Do Begin
148.      Inc(Opened, D[i-1]);
149.      If Opened > 0
150.        Then Exit(No);
151.      If Opened < 0
152.        Then DSF.Merge(i-1, i);
153.    End;
154.    If Opened <> 0
155.      Then Halt(1);
156.    If DSF.Size = 1
157.      Then Exit(Yes)
158.      Else Exit(No);
159.  End;
160. 
161.END.
[Post] 11.04.2017 07:37:55
   Тема: Re:Описания решений задач IOI 2010 - ...
[#] [Up]
Михаил Долинский

Темы: 2072
Сообщений: 49927

Мой профиль
FULL.
view source
print?
001.Unit Railroad;
002.{$Mode ObjFPC}
003.Interface
004.  TYPE
005.    TInts  = Array of LongInt;
006. 
007.  Function Plan_Roller_Coaster (S, T : TInts): Int64;
008. 
009.Implementation
010.  CONST
011.    MinX  =              1;
012.    MaxX  = 1000*1000*1000;
013.   
014.  TYPE
015.    TDSF = Object
016.      Id, Rank  : TInts;
017.      Size      : LongWord;
018.      Constructor Create (N : LongWord);
019.      Function Get (U : LongWord): LongWord;
020.      Function Merge (U, V : LongWord): Boolean;
021.    End;
022.    TEntry = Record Key, Value : LongWord; End;
023.    THeap = Object
024.      Data : Array of TEntry;
025.      Size : LongWord;
026.      Constructor Create (Capacity : LongWord);
027.      Procedure Push (Key, Value : LongWord);
028.      Function Pop (): TEntry;
029.     Private
030.      Procedure Up (U : LongWord);
031.      Procedure Down (U : LongWord);
032.      Procedure Swap (U, V : LongWord);   Inline;
033.    End;
034. 
035. 
036.  Constructor TDSF.Create (N : LongWord);
037.  Var
038.    i   : LongWord;
039.  Begin
040.    Size := N;
041.    SetLength(Id, N);
042.    SetLength(Rank, N);
043.    For i:=1 To N Do Begin
044.      Id[i-1] := i-1;
045.      Rank[i-1] := 0;
046.    End;
047.  End;
048. 
049.  Function TDSF.Get (U : LongWord): LongWord;
050.  Begin
051.    If Id[U] <> U
052.      Then Id[U] := Get( Id[U] );
053.    Exit( Id[U] );
054.  End;
055. 
056.  Function TDSF.Merge (U, V : LongWord): Boolean;
057.  Begin
058.    U := Get(U);   V := Get(V);
059.    If U = V
060.      Then Exit(False);
061.    If Rank[U] = Rank[V]
062.      Then Inc( Rank[U] );
063.    If Rank[U] < Rank[V]
064.      Then Id[U] := V
065.      Else Id[V] := U;
066.    Dec(Size);
067.    Exit(True);
068.  End;
069. 
070. 
071.  Function Entry (Key, Value : LongWord): TEntry;
072.  Begin
073.    Result.Key := Key;
074.    Result.Value := Value;
075.  End;
076. 
077. 
078.  Constructor THeap.Create (Capacity : LongWord);
079.  Begin
080.    SetLength(Data, Capacity);
081.    Size := 0;
082.  End;
083. 
084.  Procedure THeap.Push (Key, Value : LongWord);
085.  Begin
086.    Data[Size] := Entry(Key, Value);
087.    Inc(Size);
088.    Up(Size-1);
089.  End;
090. 
091.  Function THeap.Pop (): TEntry;
092.  Begin
093.    Result := Data[0];
094.    Swap(0, Size-1);
095.    Dec(Size);
096.    Down(0);
097.  End;
098. 
099.  Procedure THeap.Up (U : LongWord);
100.  Var
101.    V   : LongWord;
102.  Begin
103.    While (U > 0) Do Begin
104.      V := (U+1) div 2 - 1;
105.      If Data[V].Key < Data[U].Key
106.        Then Break;
107.      Swap(U, V);
108.      U := V;
109.    End;
110.  End;
111. 
112.  Procedure THeap.Down (U : LongWord);
113.  Var
114.    V, W        : LongWord;
115.  Begin
116.    V := (U+1) * 2 - 1;
117.    While V < Size Do Begin
118.      W := V+1;
119.      If W = Size
120.        Then W := V;
121.      If Data[W].Key < Data[V].Key
122.        Then V := W;
123.      If Data[U].Key < Data[V].Key
124.        Then Break;
125.      Swap(U, V);
126.      U := V;
127.      V := (U+1) * 2 - 1;
128.    End;
129.  End;
130. 
131.  Procedure THeap.Swap (U, V : LongWord);
132.  Var
133.    Buff        : TEntry;
134.  Begin
135.    Buff := Data[U];
136.    Data[U] := Data[V];
137.    Data[V] := Buff;
138.  End;
139. 
140. 
141.  Procedure ToSet (Var A : TInts);
142.  Var
143.    Heap        : THeap;
144.    X, M        : LongWord;
145.  Begin
146.    Heap.Create( Length(A) );
147.    For X in A
148.      Do Heap.Push(X, X);
149.    M := 0;
150.    While Heap.Size > 0 Do Begin
151.      X := Heap.Pop().Value;
152.      If (M > 0) and (A[M-1] = X)
153.        Then Continue;
154.      A[M] := X;
155.      Inc(M);
156.    End;
157.    SetLength(A, M);
158.  End;
159. 
160.  Function Find (Const Points : TInts;  X : LongWord): LongWord;
161.  Var
162.    L, R        : LongWord;
163.  Begin
164.    L := 0;
165.    R := Length(Points);
166.    While L+1 < R
167.      Do If Points[(L+R) div 2] > X
168.        Then R := (L+R) div 2
169.        Else L := (L+R) div 2;
170.    Exit(L);
171.  End;
172. 
173.  Function Plan_Roller_Coaster (S, T : TInts): Int64;
174.  Var
175.    DSF                 : TDSF;
176.    Edges               : THeap;
177.    Points, D           : TInts;
178.    Edge                : TEntry;
179.    Opened              : Int64;
180.    N, M, i, U, V, DX   : LongWord;
181.  Begin
182.    N := Length(S);
183.    SetLength(S, N+1);   S[N] := MaxX;
184.    SetLength(T, N+1);   T[N] := MinX;
185.    SetLength(Points, 2*N+2);
186.    M := 0;
187.    For i:=0 To N Do Begin
188.      Points[M] := S[i];
189.      Points[M+1] := T[i];
190.      Inc(M, 2);
191.    End;
192.    ToSet(Points);
193.    M := Length(Points);
194.    DSF.Create(M);
195.    SetLength(D, M);
196.    FillChar(D[0], M*SizeOf(D[0]), $00);
197.    For i:=0 To N Do Begin
198.      U := Find(Points, S[i]);   V := Find(Points, T[i]);
199.      DSF.Merge(U, V);
200.      Inc( D[U] );
201.      Dec( D[V] );
202.    End;
203.    Result := 0;
204.    Opened := 0;
205.    Edges.Create(M);
206.    For i:=1 To M-1 Do Begin
207.      Inc(Opened, D[i-1]);
208.      DX := Points[i] - Points[i-1];
209.      If Opened <> 0 Then Begin
210.        DSF.Merge(i-1, i);
211.        If Opened > 0
212.          Then Inc(Result, Opened*DX);
213.      End Else Edges.Push(DX, i-1);
214.    End;
215.    If Opened <> -D[M-1]
216.      Then Halt(1);
217.    While DSF.Size > 1 Do Begin
218.      Edge := Edges.Pop();
219.      U := Edge.Value;
220.      If DSF.Get(U) <> DSF.Get(U+1) Then Begin
221.        Inc(Result, Edge.Key);
222.        DSF.Merge(U, U+1);
223.      End;
224.    End;
225.  End;
226. 
227.END.
[Post] 11.04.2017 07:38:06
   Тема: Re:Описания решений задач IOI 2010 - ...
[#] [Up]
Михаил Долинский

Темы: 2072
Сообщений: 49927

Мой профиль


Алексей Гуленко:

shortcut: дихотомия по ответу с возрастающе сложными оптимизациями проверки (даже не брался) 


Станислав Титенок:

Что перебирается дихотомией, диаметр графа или расположение добавляемого ребра?
Если диаметр, то как проверять, возможен ли заданный диаметр? Если ребро, то почему это возможно, ведь не факт, что при движении ребра диаметр будет стабильно возрастать/убывать? 


Алексей Гуленко:

Сказано же: дихотомией перебираем ответ. То есть, пытаемся выяснить, возможно ли получить диаметр, не превышающий рассматриваемый вариант. Сможешь определять за N2 – получишь 71 балл (5 групп то есть). Ускоришь до N*logN – получишь 93 (6-ая группа). Остальные баллы можно получить, добив проверку до линейной.

Для проверки на существование решения, дающего ответ не хуже рассматриваемого, достаточно оценить пространство решений. В нашем случае, для любой пары вершин, расстояние между которыми превышает рассматриваемое, сумма расстояний до концов ребра не должна превышать вполне конкретного значения; это ограничивает пространство решений четырьмя границами (при визуализации на декартовой плоскости образующие стороны наклонного квадрата). За N2 вполне можно перебрать все пары вершин и вычислить пересечение областей. После чего, путём определения закономерностей в искомых значениях, можно установить, как искать предельные значения (дерево минимумов/максимумов?), а затем найти порядок обработки, при котором эти значения можно поддерживать без запросов. 
[Post] 13.04.2017 07:06:25
   Тема: Re:Описания решений задач IOI 2010 - ...
[#] [Up]
Михаил Долинский

Темы: 2072
Сообщений: 49927

Мой профиль


Гуленко Алексей:

Набросал решение на shortcut (5-ая группа, дальше сами). 


Питон

view source
print?
01.__all__ = ['find_shortcut']
02. 
03.def ok (n, x, d, c, p):
04.    mins = mind = 0
05.    maxs = maxd = 2*x[-1]
06.    for u in range(n):
07.        for v in range(u):
08.            if d[u] + (x[u]-x[v]) + d[v] > p:
09.                limit = p - c - d[u] - d[v]
10.                mins = max(mins, x[u]+x[v]-limit)
11.                maxs = min(maxs, x[u]+x[v]+limit)
12.                mind = max(mind, x[u]-x[v]-limit)
13.                maxd = min(maxd, x[u]-x[v]+limit)
14.                if mins > maxs or mind > maxd:
15.                    return False
16.    for u in range(n):
17.        for v in range(u):
18.            if (mins <= x[u]+x[v] <= maxs and mind <= x[u]-x[v] <= maxd):
19.                return True
20.    return False
21. 
22.def find_shortcut (n, l, d, c):
23.    pl, pr, x = 0, sum(l)+2*max(d), [sum(l[:i]) for i in range(n)]
24.    while pl+1 < pr:
25.        p = (pl+pr) // 2
26.        if ok(n, x, d, c, p):
27.            pr = p
28.        else:
29.            pl = p
30.    return pr
[Post] 13.04.2017 07:06:53
   Тема: Re:Описания решений задач IOI 2010 - ...
[#] [Up]
Михаил Долинский

Темы: 2072
Сообщений: 49927

Мой профиль


Гуленко Алексей:

Набросал решение на shortcut (5-ая группа, дальше сами). 


Паскаль

view source
print?
01.Unit Shortcut;
02.{$Mode ObjFPC}
03.Interface
04.  TYPE
05.    TInts  = Array of LongInt;
06. 
07.  Function Find_Shortcut (N : LongInt;  L, D : TInts;  C : LongInt): Int64;
08. 
09.Implementation
10.  Uses
11.    Math;
12. 
13.  CONST
14.    MaxD = 1000*1000*1000;
15.    MaxN =      1000*1000;
16.   
17.  TYPE
18.    TLongs = Array [1..MaxN] of Int64;
19. 
20.  Function Ok (N : LongInt;  Const X : TLongs;  Const D : TInts;  C : LongInt;
21.      P : Int64): Boolean;
22.  Var
23.    Limit, MinS, MaxS,
24.    MinD, MaxD          : Int64;
25.    U, V                : LongWord;
26.  Begin
27.    MinS := 0;   MaxS := 2*X[N];
28.    MinD := 0;   MaxD := 2*X[N];
29.    For V:=1 To N
30.      Do For U:=V+1 To N
31.        Do If D[U-1] + (X[U]-X[V]) + D[V-1] > P Then Begin
32.          Limit := P - C - D[U-1] - D[V-1];
33.          MinS := Max(MinS, X[U]+X[V]-Limit);
34.          MaxS := Min(MaxS, X[U]+X[V]+Limit);
35.          MinD := Max(MinD, X[U]-X[V]-Limit);
36.          MaxD := Min(MaxD, X[U]-X[V]+Limit);
37.        End;
38.    For V:=1 To N
39.      Do For U:=V+1 To N
40.        Do If (MinS <= X[U]+X[V]) and (X[U]+X[V] <= MaxS) and
41.              (MinD <= X[U]-X[V]) and (X[U]-X[V] <= MaxD)
42.          Then Exit(True);
43.    Exit(False);
44.  End;
45. 
46.  Function Find_Shortcut (N : LongInt;  L, D : TInts;  C : LongInt): Int64;
47.  Var
48.    X           : TLongs;
49.    PL, PR, P   : QWord;
50.    i           : LongWord;
51.  Begin
52.    X[1] := 0;
53.    For i:=1 To N-1
54.      Do X[i+1] := X[i] + L[i-1];
55.    PL := 0;   PR := X[N] + 2*MaxD;
56.    While PL + 1 < PR Do Begin
57.      P := (PL + PR) div 2;
58.      If Ok(N, X, D, C, P)
59.        Then PR := P
60.        Else PL := P;
61.    End;
62.    Exit(PR);
63.  End;
64. 
65.END.
 
Индекс форума ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2
Time:0,046