Blog entries - Codeforces

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	SecondThread	150
8	-is-this-fft-	149
9	pajenegod	145
10	BledDest	144

tourist's blog

XIX Open Cup: GP of Gomel

By tourist, 5 years ago, In English

XIX Open Cup Grand Prix of Gomel takes place on Sunday, February 10, 2019, at 11:00 AM Petrozavodsk time.

The links to the contest:

You need an Open Cup login to participate.

The Division 1 contest also serves as the open qualifying contest for MosCode Festival 2019.

I'm the writer of all the problems. Let's discuss them here after the contest!

Full text and comments »

+173

tourist
5 years ago
45

TCO 2019 Algorithm Rules

By tourist, history, 6 years ago, In English

The rules for advancement to the onsite finals of TCO 2019 Algorithm have changed from those for TCO 2018:

http://tco19.topcoder.com/home/algorithm/algorithm-rules

This page claims there are "three (3) ways to advance to the Onsite Finals"!

The first way to advance is to take part in SRMs. There are four three-month Online Stages, during which every positive score in an SRM counts towards a global ranking. The best competitor in each Online Stage advances to the onsite finals directly, with the next 10 competitors advancing to Online Round 4 (which is the final qualification round).

The other two ways stay the same. The best 10 competitors (used to be 14 though) advance from Online Round 4, and the best 2 competitors advance from Online Wild Card Round.

The changes seem to be big enough -- and already relevant, since SRM 736 on August 15 (in two days from now) already counts towards Online Stage 1. However, apart from TCO 2019 website I've only seen this information in Topcoder weekly newsletters, and I believe many people have missed it.

What do you think?

Full text and comments »

+162

tourist
6 years ago
6

XVIII Open Cup: GP of Gomel

By tourist, history, 6 years ago, In English

XVIII Open Cup Grand Prix of Gomel takes place on Sunday, February 18, 2018, at 11:00 AM Petrozavodsk time.

The link to the contest. You need an Open Cup login to participate.

I'm the writer of all the problems. Let's discuss them here after the contest!

Full text and comments »

+182

tourist
6 years ago
48

Topcoder SRM 728

By tourist, history, 6 years ago, In English

Hello!

Topcoder SRM 728 will be held tomorrow (January 25, 2018).

See what time it starts in your area.

I'm the writer. Everyone is welcome to participate!

Full text and comments »

+217

tourist
6 years ago
25

AtCoder Grand Contest 020

By tourist, history, 6 years ago, In English

What is better than setting one AtCoder Grand Contest? Setting two AtCoder Grand Contests, of course!

AtCoder Grand Contest 020 will be held on Sunday (time). The writer is tourist.

Contest Link

Contest Announcement

This is the first contest of 2018 counted towards AtCoder Race Ranking. If you get into top 30 in this contest, you will get GP30 scores.

The point values will be 300 — 500 — 700 — 1100 (500) — 1400 — 2100. Note that the contest duration is unusual (130 minutes).

Let's discuss problems after the contest.

Full text and comments »

+443

tourist
6 years ago
58

Hello 2018 -- Tutorial

By tourist, history, 6 years ago, translation, In English

Here is the tutorial of Hello 2018. Enjoy!

Modular Exponentiation

Christmas Spruce

Party Lemonade

Too Easy Problems

Problem writer: tourist

Tutorial is loading...

Solution with binary search

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, T;
  scanf("%d %d", &n, &T);
  vector<int> a(n), t(n);
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &a[i], &t[i]);
  }
  vector<int> res;
  int low = 0, high = n;
  while (low < high) {
    int mid = (low + high + 1) >> 1;
    vector< pair<int,int> > e;
    for (int i = 0; i < n; i++) {
      if (a[i] >= mid) {
        e.emplace_back(t[i], i);
      }
    }
    sort(e.begin(), e.end());
    bool ok = false;
    if ((int) e.size() >= mid) {
      int sum = 0;
      for (int i = 0; i < mid; i++) {
        sum += e[i].first;
      }
      if (sum <= T) {
        ok = true;
        res.resize(mid);
        for (int i = 0; i < mid; i++) {
          res[i] = e[i].second;
        }
      }
    }
    if (ok) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  int sz = (int) res.size();
  printf("%d\n%d\n", sz, sz);
  for (int i = 0; i < sz; i++) {
    if (i > 0) {
      putchar(' ');
    }
    printf("%d", res[i] + 1);
  }
  printf("\n");
  return 0;
}

Solution with set

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, T;
  scanf("%d %d", &n, &T);
  vector< vector< pair<int, int> > > at(n + 1);
  for (int i = 0; i < n; i++) {
    int foo, bar;
    scanf("%d %d", &foo, &bar);
    at[foo].emplace_back(bar, i);
  }
  vector<int> res;
  set< pair<int, int> > s;
  int sum = 0;
  for (int k = n; k > 0; k--) {
    for (auto &p : at[k]) {
      sum += p.first;
      s.emplace(p);
    }
    while ((int) s.size() > k) {
      sum -= (--s.end())->first;
      s.erase(--s.end());
    }
    if ((int) s.size() == k && sum <= T) {
      for (auto &p : s) {
        res.push_back(p.second);
      }
      break;
    }
  }
  int sz = (int) res.size();
  printf("%d\n%d\n", sz, sz);
  for (int i = 0; i < sz; i++) {
    if (i > 0) {
      putchar(' ');
    }
    printf("%d", res[i] + 1);
  }
  printf("\n");
  return 0;
}

Logical Expression

Problem writer: budalnik

Tutorial is loading...

Solution 1

#include <iostream>
#include <set>
#include <vector>
#include <string>

using namespace std;

bool ls(const string& a, const string& b) {
	if (a.length() == b.length()) return a < b;
	return a.length() < b.length();
}

struct Expression {
	int p, t;
	string e;

	Expression(string _e, int t_, int _p) : e(_e), t(t_), p(_p) {}

	bool operator < (const Expression& ex) const {
		if (ex.e == e) {
			if (t != ex.t) {
				return t < ex.t;
			}
			return p < ex.p;
		}
		return ls(e, ex.e);
	}
};

set<Expression> q;

const int FULL = 0xff;
const vector<int> B = {1, 2, 4, 8, 16, 32, 64, 128};
const int X_TABLE = B[4] + B[5] + B[6] + B[7];
const int Y_TABLE = B[2] + B[3] + B[6] + B[7];
const int Z_TABLE = B[1] + B[3] + B[5] + B[7];

string dp[1 << 8][3];

void add(int pr, const string& s, int mask) {
	if (dp[mask][pr].empty() || ls(s, dp[mask][pr])) {
		dp[mask][pr] = s;
		Expression e(s, mask, pr);
		q.insert(e);
	}
}

int main() {
	add(2, "x", X_TABLE);
	add(2, "y", Y_TABLE);
	add(2, "z", Z_TABLE);
	while (!q.empty()) {
		auto e = *q.begin();
		q.erase(q.begin());

		if (e.p == 2) {
			add(2, "!" + e.e, ~e.t & FULL);
			add(1, e.e, e.t);
		}

		if (e.p == 1) {
			for (int mask = 0; mask < FULL; ++mask) {
				if (!dp[mask][2].empty()) {
					add(1, dp[mask][2] + "&" + e.e, mask & e.t);
					add(1, e.e + "&" + dp[mask][2], mask & e.t);
				}
			}
			add(2, "(" + e.e + ")", e.t);
			add(0, e.e, e.t);
		}

		if (e.p == 0) {
			for (int mask = 0; mask < FULL; ++mask) {
				for (int pr = 1; pr <= 2; ++pr) {
					if (!dp[mask][pr].empty()) {
						add(0, dp[mask][pr] + "|" + e.e, mask | e.t);
						add(0, e.e + "|" + dp[mask][pr], mask | e.t);
					}
				}
			}
			add(2, "(" + e.e + ")", e.t);
		}
	}

	
	int n;
	cin >> n;
	while (n--) {
		string s;
		cin >> s;
		int mask = 0;
		for (int i = 0; i < 8; ++i) {
			if (s[i] == '1') {
				mask |= (1 << i);
			}
		}

		cout << dp[mask][0] << endl;
	}

	return 0;
}

Solution 2

#include <bits/stdc++.h>

using namespace std;

string res[256][3];
bool changed;

void update(string &a, string &b) {
  if (a == "" || (b.length() < a.length() || (b.length() == a.length() && b < a))) {
    changed = true;
    a = b;
  }
}

int main() {
  res[(1 << 4) + (1 << 5) + (1 << 6) + (1 << 7)][0] = "x";
  res[(1 << 2) + (1 << 3) + (1 << 6) + (1 << 7)][0] = "y";
  res[(1 << 1) + (1 << 3) + (1 << 5) + (1 << 7)][0] = "z";
  changed = true;
  while (changed) {
    changed = false;
    for (int i = 0; i < 256; i++) {
      for (int j = 0; j < 3; j++) {
        if (res[i][j] == "") {
          continue;
        }
        { // op == 0
          string s = res[i][j];
          if (j > 0) {
            s = "(" + s + ")";
          }
          s = "!" + s;
          update(res[i ^ 255][0], s);
        }
        for (int ii = 0; ii < 256; ii++) {
          for (int jj = 0; jj < 3; jj++) {
            if (res[ii][jj] == "") {
              continue;
            }
            for (int op = 1; op <= 2; op++) {
              string s = res[i][j];
              if (j > op) {
                s = "(" + s + ")";
              }
              string t = res[ii][jj];
              if (jj > op) {
                t = "(" + t + ")";
              }
              string w = s + (op == 1 ? '&' : '|') + t;
              update(res[op == 1 ? (i & ii) : (i | ii)][op], w);
            }
          }
        }
      }
    }
  }
  int tt;
  cin >> tt;
  while (tt--) {
    string z;
    cin >> z;
    int mask = 0;
    for (int i = 0; i < 8; i++) {
      mask |= (z[i] - '0') << i;
    }
    string best = "";
    for (int j = 0; j < 3; j++) {
      update(best, res[mask][j]);
    }
    cout << best << endl;
  }
  return 0;
}

Strongly Connected Tournament

Power Substring

Problem writer: YakutovDmitriy

Tutorial is loading...

Python solution


def dlog(x, n):
  bigMod = 5 ** n
  ans = [None, 0, 1, 3, 2][x % 5]
  val = 2 ** ans % bigMod
  mod, phi = 5, 4
  phiVal = 2 ** phi % bigMod
  for i in range(2, n + 1):
    nextMod = mod * 5
    while val % nextMod != x % nextMod:
      val = val * phiVal % bigMod
      ans += phi
    phi *= 5
    phiVal = (phiVal *
              phiVal % bigMod *
              phiVal % bigMod *
              phiVal % bigMod *
              phiVal % bigMod)
    mod = nextMod
  return ans

def main():
  inp = input()
  n = len(inp)
  a = int(inp)
  for m in range(n + 1):
    l = a * 10 ** m
    x, mod = l, 2 ** (n + m)
    if x % mod != 0:
      x += mod - x % mod
    if x % 5 == 0:
      x += mod
    if x < l + 10 ** m:
      assert x % mod == 0 and x % 5 != 0
      x = x // mod
      mod = 5 ** (n + m)
      print(n + m + dlog(x % mod, n + m))
      return
  assert False

if __name__ == '__main__':
  cnt = int(input())
  for i in range(cnt):
    main()

C++ solution

#include <bits/stdc++.h>

using namespace std;

inline long long mul(long long a, long long b, long long md) {
  long long res = 0;
  while (b > 0) {
    if (b & 1) {
      res += a; if (res >= md) res -= md;
    }
    a += a; if (a >= md) a -= md;
    b >>= 1;
  }
  return res;
}

inline long long power(long long a, long long b, long long md) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a, md);
    }
    a = mul(a, a, md);
    b >>= 1;
  }
  return res;
}

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    long long a;
    cin >> a;
    int n = (int) to_string(a).length();
    for (int m = 0; ; m++) {
      long long b = (-a) & ((1LL << (n + m)) - 1);
      if ((a + b) % 5 == 0) {
        b += (1LL << (n + m));
      }
      if ((b == 0 && m == 0) || (int) to_string(b).length() <= m) {
        long long c = (a + b) >> (n + m);
        long long t = vector<long long>{-1, 0, 1, 3, 2}[c % 5];
        long long p5 = 5;
        for (int i = 1; i < n + m; i++) {
          while (power(2, t, p5 * 5) != c % (p5 * 5)) {
            t += p5 / 5 * 4;
          }
          p5 *= 5;
        }
        t += n + m;
        cout << t << endl;
        break;
      }
      a *= 10;
    }
  }
  return 0;
}

Don't Exceed

Problem writer: tourist

Tutorial is loading...

O(n^5) solution

#include <bits/stdc++.h>

using namespace std;

const int md = 998244353;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  return power(a, md - 2);
}

const int N = 77;

int C[N][N];

typedef vector<int> poly;

poly integrate(poly a) {
  poly b = {0};
  for (int i = 0; i < (int) a.size(); i++) {
    b.push_back(mul(a[i], inv(i + 1)));
  }
  return b;
}

void sub(poly &a, poly b) {
  while (a.size() < b.size()) {
    a.push_back(0);
  }
  for (int i = 0; i < (int) b.size(); i++) {
    sub(a[i], b[i]);
  }
}

poly plug(poly a, int delta) {
  // a(x + delta)
  poly b(a.size(), 0);
  for (int i = 0; i < (int) a.size(); i++) {
    for (int j = 0; j <= i; j++) {
      add(b[j], mul(a[i], mul(C[i][j], power(delta, i - j))));
    }
  }
  return b;
}

int eval(poly a, int x) {
  int res = 0;
  for (int i = (int) a.size() - 1; i >= 0; i--) {
    res = mul(res, x);
    add(res, a[i]);
  }
  return res;
}

const int COEFF = 1000000;

int main() {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      C[i][j] = (j == 0 ? 1 : (i == 0 ? 0 : (C[i - 1][j] + C[i - 1][j - 1]) % md));
    }
  }
  int n;
  cin >> n;
  vector<int> x(n), fracs;
  for (int i = 0; i < n; i++) {
    double foo;
    cin >> foo;
    x[i] = (int) (foo * COEFF + 0.5);
    fracs.push_back(x[i] % COEFF);
  }
  fracs.push_back(0);
  sort(fracs.begin(), fracs.end());
  fracs.resize(unique(fracs.begin(), fracs.end()) - fracs.begin());
  int cnt = (int) fracs.size();
  vector<int> point(n * cnt + 1);
  for (int i = 0; i <= n * cnt; i++) {
    point[i] = mul(i / cnt * COEFF + fracs[i % cnt], inv(COEFF));
  }
  vector<int> cut(n);
  for (int i = 0; i < n; i++) {
    cut[i] = (int) (find(point.begin(), point.end(), mul(x[i], inv(COEFF))) - point.begin());
  }
  vector<poly> a(n * cnt);
  for (int i = 0; i < n * cnt; i++) {
    a[i] = {i < min(cnt, cut[0]) ? 1 : 0};
  }
  for (int id = 1; id < n; id++) {
    for (int i = 0; i < n * cnt; i++) {
      a[i] = integrate(a[i]);
    }
    for (int i = n * cnt - 1; i >= 0; i--) {
      sub(a[i][0], eval(a[i], point[i]));
      for (int j = i - 1; j >= i - cnt && j >= 0; j--) {
        add(a[i][0], eval(a[j], point[j + 1]));
        if (j > i - cnt) {
          sub(a[i][0], eval(a[j], point[j]));
        } else {
          sub(a[i], plug(a[i - cnt], md - 1));
        }
      }
    }
    for (int i = cut[id]; i < n * cnt; i++) {
      a[i] = {0};
    }
  }
  int ans = 0;
  for (int i = 0; i < n * cnt; i++) {
    poly b = integrate(a[i]);
    add(ans, eval(b, point[i + 1]));
    sub(ans, eval(b, point[i]));
  }
  printf("%d\n", ans);
  return 0;
}

O(n^4) solution

#include <bits/stdc++.h>

using namespace std;

const int md = 998244353;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  return power(a, md - 2);
}

typedef vector<int> poly;

poly integrate(poly a) {
  poly b = {0};
  for (int i = 0; i < (int) a.size(); i++) {
    b.push_back(mul(a[i], inv(i + 1)));
  }
  return b;
}

void sub(poly &a, poly b) {
  while (a.size() < b.size()) {
    a.push_back(0);
  }
  for (int i = 0; i < (int) b.size(); i++) {
    sub(a[i], b[i]);
  }
}

int eval(poly a, int x) {
  int res = 0;
  for (int i = (int) a.size() - 1; i >= 0; i--) {
    res = mul(res, x);
    add(res, a[i]);
  }
  return res;
}

const int COEFF = 1000000;

int main() {
  int n;
  cin >> n;
  vector<int> x(n), fracs;
  for (int i = 0; i < n; i++) {
    double foo;
    cin >> foo;
    x[i] = (int) (foo * COEFF + 0.5);
    fracs.push_back(x[i] % COEFF);
  }
  fracs.push_back(0);
  sort(fracs.begin(), fracs.end());
  fracs.resize(unique(fracs.begin(), fracs.end()) - fracs.begin());
  int cnt = (int) fracs.size();
  vector<int> point(n * cnt + 1);
  for (int i = 0; i <= n * cnt; i++) {
    point[i] = i / cnt * COEFF + fracs[i % cnt];
  }
  vector<int> cut(n);
  for (int i = 0; i < n; i++) {
    cut[i] = (int) (find(point.begin(), point.end(), x[i]) - point.begin());
  }
  vector<int> sz(n * cnt);
  for (int i = 0; i < n * cnt; i++) {
    sz[i] = mul((point[i + 1] - point[i] + md) % md, inv(COEFF));
  }
  vector<poly> a(n * cnt);
  vector<int> sum(n * cnt);
  for (int i = 0; i < n * cnt; i++) {
    a[i] = i < min(cnt, cut[0]) ? vector<int>{0, 1} : vector<int>{0};
    sum[i] = a[i].size() == 1 ? 0 : sz[i];
  }
  for (int id = 1; id < n; id++) {
    for (int i = n * cnt - 1; i >= 0; i--) {
      if (i >= cut[id]) {
        a[i] = {0};
        sum[i] = 0;
      } else {
        for (int j = i - 1; j >= i - cnt && j >= 0; j--) {
          add(a[i][0], sum[j]);
        }
        if (i - cnt >= 0) {
          sub(a[i], a[i - cnt]);
        }
        a[i] = integrate(a[i]);
        sum[i] = eval(a[i], sz[i]);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n * cnt; i++) {
    add(ans, sum[i]);
  }
  printf("%d\n", ans);
  return 0;
}

Full text and comments »

Tutorial of Hello 2018

+463

tourist
6 years ago
124

Hello 2018

By tourist, history, 6 years ago, translation, In English

Hello 2018!

If you're still thinking what to do on the eighth day of year 2018, pay attention! The first round for both divisions of the new year starts on January 8 at 17:35 Moscow time (what about other timezones?).

Four important components of Hello 2018 will be the same as in Good Bye 2017:

Div1 + Div2 combined
8 problems
2 hours 30 minutes
Rated

But there will also be a substantial difference:

Different problems

The problems of this round have been proposed and prepared by YakutovDmitriy, budalnik and myself.

Thanks to everyone without whom this round wouldn't be possible as well: AlexFetisov, Golovanov399, KAN, MikeMirzayanov, PavelKunyavskiy, qwerty787788, VArtem, winger.

Good luck!

Scoring distribution: 500 — 750 — 1000 — 1250 — 1750 — 2250 — 3000 — 3500.

Problem tutorial can be found here.

Congratulations to the winners!

Full text and comments »

Announcement of Hello 2018

+2848

tourist
6 years ago
346

AtCoder Grand Contest 019

By tourist, history, 7 years ago, In English

AtCoder Grand Contest 019 will be held on Saturday (time). The writer is tourist.

Contest Link

Contest Announcement

The point values will be 300 — 500 — 900 — 1000 — 1700 (1200) — 2000 (1500). Note that the contest duration is unusual (150 minutes).

Let's discuss problems after the contest.

Full text and comments »

atcoder, agc, agc019

+569

tourist
7 years ago
41

My strategy at AtCoder & CS Academy

By tourist, 7 years ago, In English

There's been much controversy lately about the late submission strategy not penalized by scoring systems of AtCoder and CS Academy. Most of the relevant discussion happened earlier at http://codeforces.com/blog/entry/53431 and http://codeforces.com/blog/entry/53449.

I have a lot of thoughts on the topic, so I've decided to share them in a separate blog post.

I really like the strategic part of programming competitions. Of course, problem solving is more important. But every contest consists of multiple problems, so there has to be a way of comparing participants which performed better at different problems. There's a huge variety of scoring rules, and I find it truly amusing.

The "submit after solving all problems" strategy looks widely attributed to me now, mostly due to Petr's remarks regarding my participation in AtCoder contests. In my opinion, it's wrong for multiple reasons.

A closer five-word description of my strategy is "implement after solving several problems". It's still quite inaccurate, though.

Here is my typical behavior during the last few contests:

Read all the problems. Usually starting with the last one, but it's not important.
While reading each problem, try to understand what it asks for, think about it for a minute.
Start thinking about problems in random order, frequently jumping from one problem to another.
Strive to make progress or look at a problem from a different perspective every time you get back to it. For easy problems, this usually means solving them from the first try, as there's little progress to be made.
Look at the scoreboard to get a grasp of the amount of time people typically spend on each problem. This helps understand whether one should look for a simple solution.
At some moment, I feel stuck in every problem I haven't solved yet (possibly an empty set). This usually happens during the first half of the contest. Implement solutions to solved problems in any comfortable order. Submit them. Here, there are two main options: submit a solution after implementing it, or do a batch submit after implementing all of them. I've tried both, and I think it doesn't matter too much. At least the latter option doesn't make me upset with WA in the process of implementing another solution, and also saves me from the urge of refreshing the submissions page for each problem separately :)
Try to solve the rest of the problems, again jumping between problems if there's more than one, but spending more time on one problem in a row. Once a problem is solved, implement its solution and submit.

I feel like this strategy has only one major disadvantage. Time spent in the beginning on problems one doesn't eventually solve is counted towards the penalty, which doesn't happen when using the standard "solve -- implement -- submit -- move on to the next problem" working cycle. For example, this could've cost me several places during AtCoder Grand Contest 018 -- I spent more than 10 minutes thinking on E and F before deciding to implement A-D, so if I hadn't solved problem F, I would've taken place 10 instead of place 7 with the normal strategy. It would've been even worse if both E and F had turned out to be unsolvable (which happens sometimes too) -- place 5 instead of place 1 for me. So, there's a prerequisite which one might call a disadvantage too: it's important to estimate problem difficulty well and feel when it's time to move from thinking to implementing.

On the other hand, I see multiple advantages. The first and foremost advantage for me: I feel very comfortable with this kind of behavior. I know that for many people it's hard and non-profitable to switch between problems too often, as it takes time to change the context. But I'm used, if not say addicted, to switching between problems often, and it seems in this case I come up with new ideas faster and better. Maybe that's due to subconscious thinking happening in background, or just a fresh look at the problem helps, it's hard to say. Implementing several solutions in a row also turned out to be comfortable and effective enough for me, as unlikely as it may seem.

Another slight advantage is, as Petr mentioned, not giving information to other participants. Intentionally withholding submissions to prevent giving information does help sometimes. It's a rare thing, though. In most cases, if you want to optimize your own result, you want to submit when it feels like you should submit, not when the scoreboard tells that you may submit.

And a small advantage I also consider important is seeing the whole picture of the problemset this way. Like, when you come to an exam, you can either start working on the problems one by one until you run out of time, or consider all the stuff you need to do and start with the most important things. The latter option feels better to me, though it might be very subjective.

Finally, the most controversial point is the possibility to bail out of the contest if your performance is poor. I wouldn't call it an advantage of this strategy. I believe considering the option of leaving the contest without submitting is disadvantageous, as you spend time thinking whether you should submit, while other participants work on the problems at the same time. The only profit you might get is the possibility to save your rating, which is a way of comparing contestants over many rounds but doesn't influence anything except one's self-esteem. And leaving the contest doesn't boost your skill anyway, so this is a meaningless thing to do in the long run.

To the admins of AtCoder and CS Academy: I think there's no need to change the rules. In my opinion, the "loophole" of leaving the contest without submitting doesn't create any big troubles. Clicking on the "Read Problems" button making the round rated for oneself requires a higher level of commitment from contestants which sometimes they aren't ready to provide. There are people for whom the rating is more important than participating in the contest; let them be. We are not reaching any goals by requiring much commitment, we're just decreasing participation.

Have fun!

Full text and comments »

atcoder, csacademy, strategy

+972

tourist
7 years ago
42

VK Cup 2017 Round 3 + Codeforces Round #412 -- Tutorial

By tourist, history, 7 years ago, translation, In English

Here is the tutorial of VK Cup 2017 Round 3 and Codeforces Round #412. Enjoy!

Is it rated?

T-Shirt Hunt

Success Rate

Dynamic Problem Scoring

Prairie Partition

Tutorial is loading...

Code with the second optimization

n = int(input())
a = sorted(list(map(int, input().split())))

maxe = max(a)
cnt = []
cur = 1
k = 0
i = 0
while i < n:
    cnt.append(0)
    while i < n and a[i] < cur:
        cnt[2 * k] += 1
        i += 1
    cnt.append(0)
    while i < n and a[i] == cur:
        cnt[2 * k + 1] += 1
        i += 1
    k += 1
    cur *= 2
cnt.append(0)
cnt.append(0)
maxe = len(cnt) - 1

maxk = cnt[1]
was = False
for l in range(maxk):
    cur = 1
    while cnt[cur] > 0:
        cnt[cur] -= 1
        cur += 2
    cnt[cur] -= 1
    cursum = 0
    ok = True
    for t in range(maxe, 0, -1):
        cursum += cnt[t]
        if cursum > 0:
            ok = False
            break
    if ok:
        print(l + 1, end=" ")
        was = True

if not was:
    print(-1)

Code with both optimizations

#include <bits/stdc++.h>

using namespace std;

const int MAX = 66;

int power[MAX + 10];
int between[MAX + 10];
int extra[MAX + 10];
int ende[MAX + 10];

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    long long foo;
    cin >> foo;
    int cc = 0;
    bool good = true;
    while (foo > 1) {
      if (foo & 1) {
        good = false;
      }
      cc++;
      foo >>= 1;
    }
    if (good) {
      power[cc]++;
    } else {
      between[cc]++;
    }
  }
  int low = 1, high = power[0] + 1;
  while (low < high) {
    int mid = (low + high) >> 1;
    int cur = mid;
    for (int i = 0; i < MAX; i++) {
      extra[i] = power[i] - cur;
      int new_cur = min(cur, power[i + 1]);
      ende[i] = cur - new_cur;
      cur = new_cur;
    }
    bool fail = false;
    int open = 0;
    for (int i = MAX - 1; i >= 0; i--) {
      open += ende[i];
      open -= between[i];
      open -= extra[i + 1];
      if (open < 0) {
        fail = true;
        break;
      }
    }
    open -= extra[0];
    if (open < 0) {
      fail = true;
    }
    if (fail) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  if (low > power[0]) {
    cout << -1 << endl;
    return 0;
  }
  for (int i = low; i <= power[0]; i++) {
    cout << i << " ";
  }
  cout << endl;
  return 0;
}

Perishable Roads

Blog Post Rating

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

inline int signum(int x) {
  return (x < 0 ? -1 : (x > 0 ? 1 : 0));
}

const int inf = (int) 1e9;

const int N = 500010;

pair <int, int> a[N];
int pos[N];

pair <int, int> mn[4 * N];
int add[4 * N];

void push(int x) {
  add[x + x] += add[x];
  mn[x + x].first += add[x];
  add[x + x + 1] += add[x];
  mn[x + x + 1].first += add[x];
  add[x] = 0;
}

void pull(int x) {
  mn[x] = min(mn[x + x], mn[x + x + 1]);
}

void build(int x, int l, int r) {
  add[x] = 0;
  if (l == r) {
    mn[x] = make_pair(a[l].first, l);
    return;
  }
  int y = (l + r) >> 1;
  build(x + x, l, y);
  build(x + x + 1, y + 1, r);
  pull(x);
}

void modify(int x, int l, int r, int ll, int rr, int v) {
  if (ll <= l && r <= rr) {
    add[x] -= v;
    mn[x].first -= v;
    return;
  }
  push(x);
  int y = (l + r) >> 1;
  if (ll <= y) {
    modify(x + x, l, y, ll, rr, v);
  }
  if (rr > y) {
    modify(x + x + 1, y + 1, r, ll, rr, v);
  }
  pull(x);
}

pair <int, int> find_min(int x, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) {
    return mn[x];
  }
  push(x);
  int y = (l + r) >> 1;
  pair <int, int> res = make_pair(inf, -1);
  if (ll <= y) {
    res = min(res, find_min(x + x, l, y, ll, rr));
  }
  if (rr > y) {
    res = min(res, find_min(x + x + 1, y + 1, r, ll, rr));
  }
  pull(x);
  return res;
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  sort(a, a + n);
  for (int i = 0; i < n; i++) {
    pos[a[i].second] = i;
  }
  build(1, 0, n - 1);
  set <int> minus, zero, plus;
  for (int id = 0; id < n; id++) {
    int i = pos[id];
    auto p = find_min(1, 0, n - 1, i, i);
    int vote = signum(p.first);
    if (vote == 0) {
      zero.insert(i);
    } else {
      if (vote == -1) {
        minus.insert(i);
        modify(1, 0, n - 1, i, n - 1, -1);
        int last_minus = *(--minus.end());
        if (a[last_minus].first == 1 - (int) minus.size()) {
          minus.erase(last_minus);
          modify(1, 0, n - 1, last_minus, n - 1, 1);
          zero.insert(last_minus);
        } else {
          if (!zero.empty()) {
            int first_zero = *(zero.begin());
            zero.erase(first_zero);
            plus.insert(first_zero);
            modify(1, 0, n - 1, first_zero, n - 1, 1);
          }
        }
      } else {
        plus.insert(i);
        modify(1, 0, n - 1, i, n - 1, 1);
        auto q = find_min(1, 0, n - 1, i, n - 1);
        if (q.first == -1) {
          int pos = q.second;
          plus.erase(pos);
          modify(1, 0, n - 1, pos, n - 1, -1);
          zero.insert(pos);
        }
      }
    }
    printf("%d\n", (int) plus.size() - (int) minus.size());
  }
  return 0;
}

Test Data Generation

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const long double pi = acos((ld)-1.0);

const int maxn = 1 << 16;

typedef complex<double> comp;

comp oddc[maxn], evenc[maxn], tmp[maxn];
comp w[maxn], invw[maxn];
ll odd[maxn], even[maxn];
int oldodd[maxn], oldeven[maxn];
int btr[maxn];
int n, A, mod;
int st2;
int answer;

inline int bitrev(int x)
{
    return btr[x];
}

void fft(comp *a, int n, comp *w, comp *res)
{
    for (int i = 0; i < n; i++) res[bitrev(i)] = a[i];
    for (int len = 2; len <= n; len *= 2)
    {
        int step = n / len;
        for (int i = 0; i < n; i += len)
        {
            int curw = 0;
            for (int j = 0; j < len / 2; j++)
            {
                comp x = res[i + j];
                comp y = res[i + len / 2 + j] * w[curw];
                res[i + j] = x + y;
                res[i + len / 2 + j] = x - y;
                curw += step;
            }
        }
    }
}

void preparefft(int n)
{
    for (int i = 0; i < n; i++)
    {
        int cur = i;
        for (int j = 0; (1 << j) < n; j++)
        {
            btr[i] = (btr[i] << 1) | (cur & 1);
            cur >>= 1;
        }
    }
    for (int i = 0; i < n; i++)
    {
        w[i] = comp(cos(2 * pi / n * i), sin(2 * pi / n * i));
        invw[i] = w[i];
    }
    reverse(invw + 1, invw + n);
}

void conv(ll *from, comp *to)
{
    for (int i = n + 1; i < st2; i++) tmp[i] = 0;
    for (int i = 0; i <= n; i++) tmp[i] = from[i];
    fft(tmp, st2, w, to);
}

void convback(comp *from, ll *to)
{
    fft(from, st2, invw, tmp);
    for (int i = 0; i < st2; i++) tmp[i] /= st2;
    for (int i = 0; i <= n; i++)
    {
        to[i] = (ll)(tmp[i].real() + 0.5);
        assert(abs(tmp[i].imag()) < 0.1);
    }
}

void addans()
{
    for (int i = 1; i <= n; i += 2) answer = (answer + odd[i]) % mod;
}

void go(int A)
{
    if (A == 1)
    {
        even[0] = 1;
        odd[0] = 0;
        odd[1] = 1;
        addans();
        return;
    }
    go(A / 2);

    for (int i = 0; i <= n; i++) oldodd[i] = odd[i];
    for (int i = 0; i <= n; i++) oldeven[i] = even[i];
    conv(even, evenc);
    conv(odd, oddc);
    for (int i = 0; i < st2; i++)
    {
        if ((A / 2) % 2 == 0)
        {
            tie(oddc[i], evenc[i])  = make_pair((oddc[i] + evenc[i]) * oddc[i], (oddc[i] + evenc[i]) * (evenc[i] - (comp)1));
        } else
        {
            tie(evenc[i], oddc[i])  = make_pair((oddc[i] + evenc[i]) * oddc[i], (oddc[i] + evenc[i]) * (evenc[i] - (comp)1));
        }
    }
    convback(oddc, odd);
    convback(evenc, even);
    for (int i = n + 1; i <= 2 * n; i++)
    {
        odd[i] = 0;
        even[i] = 0;
    }
    for (int i = 0; i <= n; i++)
    {
        odd[i] = (odd[i] + oldodd[i]) % mod;
        even[i] = (even[i] + oldeven[i]) % mod;
    }
    if (A % 2 == 1)
    {
        for (int i = n; i >= 1; i--)
        {
            odd[i] = (odd[i] + odd[i - 1] + even[i - 1]) % mod;
        }
    }
    addans();
}

int main()
{
    cin >> n >> A >> mod;
    if (A == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    st2 = 0;
    while ((1 << st2) <= n) st2++;
    st2++;
    st2 = 1 << st2;
    preparefft(st2);
    go(A / 2);
    cout << answer << endl;
    return 0;
}

Full text and comments »

Tutorial of Codeforces Round 412 (rated, Div. 1, based on VK Cup 2017 Round 3)

Tutorial of VK Cup 2017 - Round 3

Tutorial of Codeforces Round 412 (rated, Div. 2, base on VK Cup 2017 Round 3)

+570

tourist
7 years ago
67

VK Cup 2017 Round 3 + Codeforces Round #412 (Div. 1 + Div. 2)

By tourist, 7 years ago, translation, In English

Hi everyone!

The last elimination round of VK Cup 2017, Round 3, will take place on May 7 at 18:35 MSK (check your timezone here), along with separate Codeforces Round #412 for both divisions. All three rounds will be three hours long, and all three rounds will be rated.

The contest "VK Cup 2017 — Round 3" is for teams qualified from Round 2 or Wildcard Round 2. The top 20 teams will advance to the final which will be held in July 2017 in Saint Petersburg!

Huge thanks to KAN, qwerty787788, PavelKunyavskiy, AlexFetisov, MikeMirzayanov, and VK company for making this round possible.

Codeforces will be the main character of most problems. Don't forget that it's useful to read the statements of all the problems.

Good luck!

As we're in year 2017, the scoring will obviously be static. The exact scoring distribution will be announced before the round.

UPD 1. The scoring distribution is:

Div. 1 and VK Cup Round 3: 500 — 1000 — 1750 — 2500 — 2750 — 3500

Div. 2: 500 — 1000 — 1500 — 2000 — 2750 — 3500

UPD 2. Due to yesterday's registration troubles the start of the contest is delayed by 10 minutes.

UPD 3. Congratulations to the winners!

VK Cup Round 3:

Div. 1:

Div. 2:

UPD 4. Tutorial is now available.

Full text and comments »

Announcement of Codeforces Round 412 (rated, Div. 1, based on VK Cup 2017 Round 3)

Announcement of VK Cup 2017 - Round 3

Announcement of Codeforces Round 412 (rated, Div. 2, base on VK Cup 2017 Round 3)

vk cup, vk cup 2017, 412

+2247

tourist
7 years ago
218

XVII Open Cup: GP of Gomel

By tourist, history, 7 years ago, translation, In English

XVII Open Cup Stage 10: Grand Prix of Gomel takes place on Sunday, February 5, 2017, at 11:00 AM Petrozavodsk time.

The link to the contest. You need an Open Cup login to participate.

I'm the writer of all the problems.

This problemset will also be used at Barcelona ACM ICPC Bootcamp on Monday, February 6. Unfortunately, this means I have to ask you to refrain from discussing the problems in public until the end of the contest in Barcelona on Monday, 5:30 PM Barcelona time.

Let's discuss the problems here on Monday evening!

Full text and comments »

+270

tourist
7 years ago
19

TCO 2016 Algorithm Final Round

By tourist, history, 7 years ago, translation, In English

Topcoder Open 2016 Algorithm Final Round starts in 28 minutes.

The finalists are bmerry, Enot (aka enot110), Kankuro (aka vepifanov), krijgertje, Petr and rng_58.

Live broadcast will be available on Twitch.

Watch the action in the Topcoder Arena.

Also follow my live commentary on Twitter.

Full text and comments »

+402

tourist
7 years ago
18

Codeforces Round #127

By tourist, 12 years ago, translation, In English

Hello everyone!

As many of you already know, today is the day for Codeforces Round #127 missing which is really undesirable ;)

Original problems for you were created by tourist and Romka. We tried to emphasize the ideological component of the problems, thus we hope that you'll spend more time thinking than coding. Special thanks for helping in setting the contest go to Codeforces coordinator Gerald. We also thank Delinur for translating the problem statements and Alex_KPR for reviewing them.

We hope that this round won't be just a regular Codeforces round for you, but will bring you new experience and new knowledge. For the authors all problems are equally easy, yet we tried to arrange them in decreasing order of simplicity :)

Problems' point values in Division 1 are 1000-1000-1500-2000-2500. Problems' point values in Division 2 are 500-1000-2000-2000-2500.

Wish you success!

UPD: The contest is over, thanks all for participating. We hope you enjoyed it :)

In Division 1 rng_58 was a clear winner, solving all 5 problems in an hour and a half! No one else managed to solve all problems in two hours.

The winners in Division 1 are (full results):

In Division 2 every problem was solved by somebody, but nobody managed to solve all problems. The battle was very tough and the gaps were very small.

The winners in Division 2 are (full results):

Congratulations to the winners!

UPD2: The editorial is available now.

Full text and comments »

Announcement of Codeforces Round 127 (Div. 1)

codeforces round, 127

+305

tourist
12 years ago
62

CodeChef November Cook-off

By tourist, 12 years ago, translation, In English

Hello everyone!

I invite you to participate in the upcoming short contest at CodeChef.com (http://www.codechef.com/COOK16). The contest starts on November 20 at 20:00 Moscow time (check the starting time in other time zones here). This time I'm setting the problems, while Anton Lunyov (Anton_Lunyov) is the tester. Anton made a significant contribution into setting the contest, so my big "thank you" goes to him :)

Here is some information for those who has never participated in short contests at CodeChef. The length of the contest is 2.5 hours, there will be 5 problems of different difficulty levels. The contest will be held by the traditional ACM rules. No special registration for the contest is needed, it's enough to register at the CodeChef site.

Unfortunately I won't be able to monitor the contest as I'll participate in All-Russian School Team Olympiad in Programming on the same day. Nevertheless, Anton will be able to answer all your questions (if any).

Good luck! ;)

Full text and comments »

codechef, cookoff

+123

tourist
12 years ago
9

Codeforces Beta Round #17 Tutorial

By tourist, 14 years ago, translation, In English

Contest discussion

Problem A. Noldbach problem

To solve this problem you were to find prime numbers in range [2..N]. The constraints were pretty small, so you could do that in any way - using the Sieve of Eratosthenes or simply looping over all possible divisors of a number.
Take every pair of neighboring prime numbers and check if their sum increased by 1 is a prime number too. Count the number of these pairs, compare it to K and output the result.

Problem B. Hierarchy

Full text and comments »

Tutorial of Codeforces Beta Round 17

beta round #17, codeforces, contest

tourist
14 years ago
24

→