Problem C We should use items in ascending order because the first item thrown into the bin is finally multiplied by 1/2**(N-1).
Problem D I think the problem C is more difficult than the problem D.
Problem E We can find subsequence greedily. We just speed up it.
Problem F In binary representation, the number of digits of x and y must be the same. If same, y % x is equivalent to y-x. y-x and x^y is the same if and only if y-x has no borrows. Similar fact appears in recent ABC, which is not subtraction but addition. Therefore, we can solve it using digit DP.

2019-08-14

CF 579 Div. 3 F Complete the Projects

Problem - F2 - Codeforces

I wonder why my solutions passes. My solution is quite different from the official solution. We assume that the optimal solution forms like this. In the following figure, elements are sorted in descending order according to a[i].

 +-------+     +-----+     +---------+
 v       |     v     |     v         |
+-+-+-+-+-+   +-+-+-+-+   +-+-+-+-+-+-+
|5|1|2|3|4|   |4|1|2|3|   |6|1|2|3|4|5|
+-+-+-+-+-+   +-+-+-+-+   +-+-+-+-+-+-+
 |             | ^         | ^
 +---------------+         +-|------------ ...
               +-------------+

If this is right, we can solve this problem by the following algorithm. If you find any hack case, you can hack it from https://codeforces.com/contest/1203/submission/58747572.

#include <bits/stdc++.h>
 
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
 
using namespace std;
using ll = long long;
 
void chmax(int &x, int y) {
  x = max(x, y);
}
 
int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, r; cin >> n >> r;
  vector<int> a(n), b(n);
  vector<int> pos, neg;
  rep(i, n) {
    cin >> a[i] >> b[i];
    if (b[i] >= 0) pos.push_back(i);
    else neg.push_back(i);
  }
  sort(pos.begin(), pos.end(), [&](int i, int j) {
    return a[i] < a[j];
  });
  sort(neg.begin(), neg.end(), [&](int i, int j) {
    return a[i] > a[j];
  });
  int cnt = 0;
  for (int i : pos) {
    if (r < a[i]) continue;
    r += b[i];
    cnt++;
  }
  static int dp[101][102][102];
  rep(i, 101) rep(j, 102) rep(k, 102) dp[i][j][k] = -1e9;
  const int m = neg.size();
  dp[0][m][0] = r;
  for (int i = 0; i <= m; i++) {
    for (int j = 0; j <= m; j++) {
      for (int k = 0; k <= m; k++) {
        if (j != m) {
          if (dp[i][j][k] >= a[neg[j]]) {
            chmax(dp[i][m][k+1], dp[i][j][k] + b[neg[j]]);
          }
        }
        if (i < m) {
          chmax(dp[i+1][j][k], dp[i][j][k]);
          if (dp[i][j][k] >= a[neg[i]]) {
            chmax(dp[i+1][j][k+1], dp[i][j][k] + b[neg[i]]);
          }
        }
        if (i < m && j == m) {
          chmax(dp[i+1][i][k], dp[i][j][k]);
        }
      }
    }
  }
  repr(i, m+1) {
    if (dp[m][m][i] >= 0) {
      cout << i + cnt << endl;
      return 0;
    }
  }
}

2019-08-12

CF 578 Div 2 E. Compress Words

https://codeforces.com/contest/1200/problem/E

The array used in KMP algorithm is useful to compute the length of common string. Someone may think this algorithm is squared time, but we don't have to treat whole string, so it works in linear time.

#include <bits/stdc++.h>
 
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
 
using namespace std;
using ll = long long;
 
vector<int> kmp(string s) {
  int n = s.size();
  vector<int> p(n + 1);
  p[0] = -1;
  int j = -1;
  for (int i = 0; i < n; i++) {
    while (j != -1 && s[i] != s[j]) j = p[j];
    p[i + 1] = ++j;
  }
  return p;
}
 
int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n;
  cin >> n;
  string ans;
  rep(i, n) {
    string s;
    cin >> s;
    string tmp = ans.substr(max(0, (int)ans.size() - (int)s.size()));
    ans += s.substr(kmp(s + "$" + tmp).back());
  }
  cout << ans << endl;
}

2019-08-10

ABC 137 screencast

F - Polynomial Construction

drive.google.com

Problem C: I forget a hashtable whenever I use C++. C++'s hashtable is really dangerous because it doesn't use randomness.

Problem D: Considering reversed time, the items we can choose increases. Therefore, we can solve it greediliy.

Problem E: Since the problem statements says you should use Bellman-Ford, I solved it speedily. However, I mistook the way to detect positive cycles. I thought by 2N iterations the effect of positive cycles propagates to the terminal.

Problem F: Just use Lagrange's interpolation. It is difficult for me to implement division and Lagrange's interpolation. Both of them are rarely appears in contests, so that is natural. But I hope to implement them more rapidly.

2019-08-05

ABC 136 F. Enclosed Points

https://atcoder.jp/contests/abc136/tasks/abc136_f

I solved problems with F# because I don't want to use C++. Although I prefer to OCaml, I gave up it due to 64bit integers. I use verbose F# because in off-side rule we can't restore indents when carelessly erase them. OCaml is almost as fast as C++, where F# is a little slow regarding IO, so we should prepare own IO functions. Unbuffered IO is really slow.

UPD: I thought F# is available in Codeforces, but it is unavailable now. OCaml is not suitable for contest because OCaml doesn't have binary operators for 64bit integers. In 64bit platform, int has 64 bit precision, but Codeforces is now 32bit.

UPD: The following source code realize Int64 arithmetics. I want to use https://caml.inria.fr/pub/docs/manual-ocaml/manual042.html, but no contests support now. I want to replace all int with Int64, but some functions in the standard library takes int, so I can't.

open Scanf
open Printf

module L = struct
  open Int64
  let ( + ), ( - ), ( * ), ( / ), ( % ), ( ~- ) = add, sub, mul, div, rem, neg
end
let ( ~~ ) = Int64.of_int
let ( !! ) = Int64.to_int

let readint () = scanf " %d" (fun x -> x)
let readint64 () = scanf " %Ld" (fun x -> x)

module M = struct
  let md = 7L
  let ( + ) x y = let z = Int64.add x y in if z < md then z else Int64.sub z md
  let ( - ) x y = let z = Int64.sub x y in if z >= 0L then z else Int64.add z md
  let ( * ) x y = Int64.rem (Int64.mul x y) md
end

type bit = { dat : int64 array }

module BIT = struct
  let make (n : int) : bit = { dat=Array.make (n + 1) 0L }
  let update (bit : bit) (k : int) (v : int64) =
    let { dat } = bit in
    let i = ref (k + 1) in
    while !i < Array.length dat do
      dat.(!i) <- L.(dat.(!i) + v);
      i := !i + (!i land -(!i))
    done
  let query (bit : bit) (k : int) : int64 =
    let { dat } = bit in
    let i = ref k in
    let ans = ref 0L in
    while !i > 0 do
      ans := L.(!ans + dat.(!i));
      i := !i - (!i land -(!i))
    done;
    !ans
end

let () =
  assert (L.(2L + 3L) = 5L);
  assert (L.(2L - 3L) = -1L);
  assert (L.(2L * 3L) = 6L);
  assert (L.(2L / 3L) = 0L);
  assert (L.(2L % 3L) = 2L);
  assert (L.(min 2L 3L) = 2L);
  assert (M.(4L + 5L) = 2L);
  assert (M.(4L - 5L) = 6L);
  assert (M.(4L * 5L) = 6L);
  let bit = BIT.make 10 in
  for i = 0 to 9 do
    BIT.update bit i ~~(i+1)
  done;
  for i = 0 to 10 do
    let i = ~~i in
    assert (BIT.query bit !!i = L.(i * (i + 1L) / 2L))
  done;
  try (BIT.query bit (-1) |> ignore; failwith "") with _ -> ();
  try (BIT.query bit 11 |> ignore; failwith "") with _ -> ();

I used the following template. I'll omit the template.

#nowarn "62"
#light "off"
open System;;
open System.IO;;

let reader = new StreamReader(new BufferedStream(Console.OpenStandardInput ()));;
let writer = new StreamWriter(new BufferedStream(Console.OpenStandardOutput ()));;

let skipSpaces () = while reader.Peek () <= int ' ' do reader.Read () |> ignore done;;
let read f = skipSpaces (); [|while reader.Peek () > int ' ' do yield char (reader.Read ()) done |] |> System.String |> f;;
let readint () = skipSpaces (); let s = if reader.Peek() = int '-' then (ignore (reader.Read()); -1) else 1 in let mutable ans = 0 in while reader.Peek () > int ' ' do ans <- ans * 10 + (reader.Read () - int '0'); done; s * ans;;
let write (s : string) = writer.Write s;;
let writeln (s : string) = writer.WriteLine s;;

(* Write code here *)

reader.Close();;
writer.Close();;

Problem A

let a, b, c = readint (), readint (), readint();;
c - min (a - b) c |> printfn "%d";;

Problem B

I wrote keta function. string >> String.length may be simpler than it.

let rec keta n = if n = 0 then 0 else 1 + keta (n / 10);;
let N = readint ();;
{1..N} |> Seq.filter (fun x -> keta x % 2 = 1) |> Seq.length |> printfn "%d";

Problem C

As looking at elements from left to right, greedily subtract one from each element if we can.

A.[0] <- A.[0] - 1;;
let mutable ans = true;;

for i in 1..N-1 do
  if A.[i-1] > A.[i] then
    ans <- false
  elif A.[i-1] < A.[i] then
    A.[i] <- A.[i] - 1
done;;

(if ans then "Yes" else "No") |> printfn "%s";;

Problem D

It seems that doubling solution is easy to write than I thought. I wrote two pointers.

let S = read string;;
let N = S.Length;;

let mutable i = 0;;
let ans = Array.create N 0;;

while i < N do
  let j = i in
  i <- {i..N} |> Seq.find (fun i -> i = N || S.[i] <> 'R');
  let k = i in
  i <- {i..N} |> Seq.find (fun i -> i = N || S.[i] <> 'L');
  let a, b = k - j, i - k in
  ans.[k-1] <- ((a + 1) / 2 + b / 2);
  ans.[k] <- (a / 2 + (b + 1) / 2);
done;;

ans |> Array.map string |> String.concat " " |> writeln;;

Problem E

Once we notice that the sum doesn't change, we almost have solved this problem. That's a lie. Greedy part is not trivial for me.

let divisors x = Seq.initInfinite ((+) 1) |> Seq.takeWhile (fun i -> i * i <= x) |> Seq.filter (fun i -> x % i = 0) |> Seq.collect (fun i -> seq [i; x / i]);;

let N, K = readint (), readint ();;
let A = Array.init N (ignore >> readint);;

let f d =
  let x = Array.init N (fun i -> A.[i] % d) |> Array.sort in
  let mutable i = 0 in
  let mutable j = N - 1 in
  let mutable souwa = 0 in
  while i < j do
    let tukau = min x.[i] (d - x.[j]) in
    souwa <- souwa + tukau;
    x.[i] <- x.[i] - tukau;
    x.[j] <- x.[j] + tukau;
    if x.[i] = 0 then i <- i + 1;
    if x.[j] = d then j <- j - 1;
  done;
  souwa <= K;;

divisors (Array.sum A) |> Seq.filter f |> Seq.max |> printf "%d";;

Problem F

If we can notice that x[i]!=x[j] and y[i]!=y[j], this problem become a little easier. However, we can solve this problem without this constraint (My first solution is so).
[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>] is too long.

let MOD = 998244353;;
type Mint = Mint of int
  with
    static member (+) (Mint x, Mint y) = Mint (let z = x + y in if z < MOD then z else z - MOD)
    static member (-) (Mint x, Mint y) = Mint (let z = x - y in if z >= 0 then z else z + MOD)
    static member (*) (Mint x, Mint y) = int64 x * int64 y % int64 MOD |> int |> Mint
    override this.ToString() = match this with Mint x -> x.ToString()
  end;;

type BIT = { dat : int [] }
[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module BIT =
  begin
    let create n : BIT = { dat = Array.create (n + 1) 0 }
    let update ({dat=dat} : BIT) (k : int) (v : int) =
      let mutable i = k + 1 in
      while i < Array.length dat do dat.[i] <- dat.[i] + v; i <- i + (i &&& -i) done
    let query ({dat=dat} : BIT) (k : int) : int =
      let mutable i = k in
      let mutable ans = 0 in
      while i > 0 do ans <- ans + dat.[i]; i <- i - (i &&& -i) done;
      ans
  end;;

let N = readint ();;
let X, Y = Array.init N (fun _ -> readint (), readint ()) |> Array.sort |> Array.unzip;;
let YD = Y |> Array.distinct |> Array.sort |> Array.mapi (fun i x -> x, i) |> Map.ofArray;;
for i in 0..N-1 do Y.[i] <- YD.[Y.[i]] done;;
let L = BIT.create YD.Count;;
let R = BIT.create YD.Count;;
for y in Y do BIT.update R y 1 done;;

let two = Array.replicate N (Mint 2) |> Array.scan (*) (Mint 1);;

let mutable ans = two.[N] * (Mint N);;
for i in 0..N-1 do
  BIT.update R Y.[i] (-1);
  let d = BIT.query L Y.[i] in
  let c = BIT.query R Y.[i] in
  let a = i - d in
  let b = (N-1-i-c) in
  [Mint 1;
  two.[a] - Mint 1; two.[b] - Mint 1; two.[c] - Mint 1; two.[d] - Mint 1;
  (two.[a] - Mint 1) * (two.[b] - Mint 1);
  (two.[b] - Mint 1) * (two.[c] - Mint 1);
  (two.[c] - Mint 1) * (two.[d] - Mint 1);
  (two.[d] - Mint 1) * (two.[a] - Mint 1)] |> List.iter (fun x -> ans <- ans - x);
  BIT.update L Y.[i] 1;
done;;
printfn "%O" ans;;

pekempey's blog

ABC 138 screencast