Do you know where will the ICPC world finals 2025 be held?

Was it announced officially anywhere? I've heard from some people who were at the last world finals that the organizers didn't announce where next year's WF is going to be or mention anything about it.

Earlier this year I've heard rumors that the 2025's WF might be held in Sweden, and later on I've heard some people saying that it'll be held in Armenia, but the latest place I've heard is China.

Look at the following picture, don't you feel that there's something unusual?

You are right, the "Pay attention" block of the sidebar on the right is missing.

I've been on codeforces for several years, and this is the first time I don't see any contests on the top right of my home page.

Definitely happening for the first time

283556689

283556833

Finally done it. It only took a few contests.

The international finals of the International Informatics Olympiad in Teams (IIOT) 2024 will be happening in the next couple of days.

It will be hosted by Syria as a hybrid event. There will be 20 participating teams from 10 different countries.

Contest format:

• 7-10 problems (including subtasks)
• 4 hours
• 4 contestants and 2 computers per team

Authors of the problems used in this contest: Péter peti1234 Gyimesi, Áron mraron Noszály, Bernard BERNARD Brahimsha, Alessandro bortoz Bortolin, Zsolt birka0 Németh, Mihnea-Vicențiu MVB Bucă, Péter Csorba, and Gabriella Blénessy.

People who helped preparing the problems: davi_bart, Kaey, Virv, ApraCadabra, and stefdasca.

The practice round will be tomorrow on Friday, 10 May 2024, 17:30.

The main contest will happen on Saturday, 11 May 2024, 09:30.

For more info about the contest you can visit iio.team and iiot2024.sy.

You can find the problems of the previous editions here.

Wish the participating teams a good luck!

UPD: An unofficial list of participating teams could be found here: codeforces.com/blog/entry/129019

UPD2: The contest is happening right now, you can follow the live ranking at: https://gara.squadre.olinfo.it/ranking/ and it will become frozen during the last hour of the contest.

UPD3: The closing ceremony is now over. You can find the final results here.

UPD4: The editorial is out. You can find it here.

UPD5: An online mirror will be available here (live ranking is available here). It will start on Monday, 19 May 2024, 17:30 and will last for 30 hours.

Someone just sent me these from today's contest:

250648064

250772342

This year's Asia-Pacific Informatics Olympiad (APIO) is approaching, it will be open on the 20-th of May for official participants.

It is an IOI-Style contest with 3 problems and 5 hours. You can find more information on the official APIO 2023 site apio2023.cn.

Let's discuss problems/cutoffs/results here in the comments after the contest (and the mirror, if there's any) ends.

I wish everyone participating good luck!

UPD: The contest has ended, you can now discuss the problems in the comments.

This year's Asia-Pacific Informatics Olympiad (APIO) is approaching, it will be open on 28 May for official participants for a 48-hours window, and the mirror will be open for everyone on May 30 for 24 hours.

It is an IOI-Style contest with 3 problems and 5 hours. You can find more information on the official APIO 2022 site apio2022.org.

Let's discuss problems/cutoffs/results here in the comments after the contest (and the mirror) ends.

I wish everyone participating good luck!

UPD: You can find more information about the mirror here.

UPD2: Both the contest and the mirror are now over.

UPD3: The final ranking has been announced, you can find it here.

Hello, I have a problem and some variations on it that I would like to share. At the moment, I don't know solutions to all the problems, so any ideas/solutions are welcomed in the comments.

Problem 0: You are given an array $$$A$$$ of $$$n$$$ integers, and $$$q$$$ queries of the form "$$$l$$$ $$$r$$$ $$$x$$$" and each number in $$$A[l...r]$$$ appear either once or twice. For each query you have to print the number of elements $$$A_j$$$ $$$(l \le j \le r)$$$ such that $$$A_j \lt x$$$, and the number $$$A_j$$$ appears exactly once in $$$A[l...r]$$$.

Problem 1: The same as Problem 0, but without the restriction that each number in $$$A[l...r]$$$ appear either once or twice.

Problem 2: The same as Problem 1, but with the following change in the queries: "an odd number of times" instead of "exactly once".

Problem 3: The same as Problem 0, but we have updates of the form "$$$i$$$": swap $$$A_i$$$ and $$$A_{i + 1}$$$.

Problem 3.5: The same as Problem 0, but we have updates of the form "$$$i$$$ $$$j$$$": swap $$$A_i$$$ and $$$A_j$$$.

Problem 4: The same as Problem 1, but we have updates that change single elements (e.g. $$$A_i := x$$$, $$$A_i := A_i + x$$$, or some combination of updates like these).

Problem 5: The same as Problem 2, but we have updates that change single elements.

Problem 6: The same as Problem 1, but we have updates that change the elements of ranges (e.g. $$$A_i := A_i + x$$$ for $$$(l \le i \le r)$$$, $$$A_i := min(A_i, x)$$$ for $$$(l \le i \le r)$$$, or some combination of updates like these).

Problem 7: The same as Problem 2, but we have updates that change the elements of ranges.

Time limit: ~4s

Memory limit: 256MB~512MB.

$$$(1 \le n, q \le 500 \space 000, 1 \le A_i \le 10^9)$$$

I'm not sure how hard/easy these problems are. I'll update the blog with founded solutions in the future.

Hello Codeforces' people

Since Innopolis Open Olympiad for this year is starting soon, I decided to share some of my favorite problems from this olympiad alongside solutions and hints.

This blog contains problems from the first qualification rounds only. I might post other blogs for the second qualification rounds and the finals before their respective contests this year if I got positive feedback on this.

102436D - Subset ``AND''

#include <bits/stdc++.h>

using namespace std;

int K, s, bit;
vector<long long> res;

void bld(int k) {
  if (k & 1) {
    if (k - 1 > 0) {
      bld(k - 1);
    }
    bit += 1;
    res.push_back((1LL << bit) - 1);
    return;
  }
  bld(k >> 1);
  for (int i = 0; i < (int) res.size(); i++) {
    res[i] |= (1LL << bit);
  }
  res.push_back((1LL << bit) - 1);
  bit += 1;
}

int main() {
  scanf("%d %d", &K, &s);
  bld(K);
  printf("%d\n", (int) res.size());
  for (int i = 0; i < (int) res.size(); i++) {
    if (i > 0) {
      printf(" ");
    }
    printf("%lld", res[i]);
  }
  puts("");
  return 0;
}

102436C - Painting Plan

#include <bits/stdc++.h>

using namespace std;

int n, k, x[14004];

bitset<30001> dp, pd, c[7003];

int main() {
  scanf("%d %d", &n, &k);
  for (int i = 0; i < 2 * n; i++) {
    scanf("%d", &x[i]);
  }
  vector<int> a;
  for (int i = 1; i < 2 * n; i += 2) {
    a.push_back(x[i] - x[i - 1]);
  }
  vector<int> b(1, 0);
  for (int i = 3; i < 2 * n; i += 2) {
    b.push_back(x[i] - x[i - 2]);
  }
  dp[0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = k; j >= 0; j--) {
      pd[j] = 0;
      if (i > 0 && j >= b[i] && dp[j - b[i]]) {
        pd[j] = 1;
        c[i][j] = 1;
      }
      if (j >= a[i] && dp[j - a[i]]) {
        pd[j] = 1;
        c[i][j] = 0;
      }
    }
    swap(dp, pd);
  }
  if (!dp[k]) {
    puts("NO");
    return 0;
  }
  vector<pair<int, int>> res;
  for (int i = n - 1; i >= 0; i--) {
    if (c[i][k] == 0) {
      res.push_back({2 * (i + 1) - 1, 2 * (i + 1)});
      k -= a[i];
      continue;
    }
    int j = i - 1;
    k -= b[i];
    while (c[j][k] == 1) {
      res.push_back({2 * (j + 1), 2 * (j + 1) + 1});
      k -= b[j];
      j -= 1;
    }
    res.push_back({2 * (j + 1), 2 * (j + 1) + 1});
    k -= a[j];
    res.push_back({2 * (j + 1) - 1, 2 * (i + 1)});
    i = j;
  }
  puts("YES");
  for (auto [f, s] : res) {
    printf("%d %d\n", f, s);
  }
  return 0;
}

102032D - Stones Distribution

#include <bits/stdc++.h>

using namespace std;

const long long inf = (long long) 4e18L;

int N, S, V, p[1003];
long long dp[1003][1003][2][3];

long long sol(int i, int j, int k, int l) {
  if (j == 0 && k == 1) {
    return 0;
  }
  if (i == N) {
    return inf;
  }
  long long& ret = dp[i][j][k][l];
  if (ret != -1) {
    return ret;
  }
  long long last = (l == 1) * V + (l == 2) * (S % V);
  ret = sol(i + 1, j, k, 0);
  if (j > 0) {
    ret = min(ret, (i ? p[i - 1] * last * V : 0) + sol(i + 1, j - 1, k, 1));
  }
  if (k == 0) {
    ret = min(ret, (i ? p[i - 1] * last * (S % V) : 0) + sol(i + 1, j, 1, 2));
  }
  return ret;
}

int main() {
  scanf("%d %d %d", &N, &S, &V);
  for (int i = 0; i < N; i++) {
    scanf("%d", &p[i]);
  }
  int C = S / V;
  memset(dp, -1, sizeof dp);
  cout << sol(0, C, (S % V) == 0, 0) << '\n';
  return 0;
}

101627E - K-th order statistic

#include <bits/stdc++.h>

using namespace std;

string max(const string& a, const string& b) {
  return "(" + a + "+" + b + "+abs(" + a + "-" + b + "))/2";
}

string min(const string& a, const string& b) {
  return "(" + a + "+" + b + "-abs(" + a + "-" + b + "))/2";
}

string eq(const string& a, const string& b) {
  return "1-" + min(string(1, '1'), "abs(" + a + "-" + b + ")");
}

int n, k;

int main() {
  scanf("%d %d", &n, &k);
  string res = "", K = to_string(k);
  for (char c = 'a'; c < char('a' + n); c++) {
    if (c > 'a') {
      res += '+';
    }
    string tmp = "", C(1, c);
    for (char d = 'a'; d < char('a' + n); d++) {
      if (!tmp.empty()) {
        tmp += '+';
      }
      string D(1, d);
      tmp += eq(C, max(C, D));
    }
    res += C + "*(" + eq(tmp, K) + ")";
  }
  puts(res.c_str());
  return 0;
}

Sometimes you might need to use multiple segment trees over some set of elements, for example, you have to answer range queries on a single array from a lot of small arrays or to make a segment tree on a tree to answer path queries.

I knew that in cases like these, it might be more efficient to use a single segment tree to represent everything, for example, instead of building a segment tree on each one of the small arrays, you represent each array as a continuous range in one big segment tree.

I've used this whenever I needed an unknown/big number of segment trees, thinking that this is more efficient and uses less memory, but sometimes it wasn't the case as doing this has made my code slower, I once ended up doing a binary search on every query to find the actual borders of the queries, which I could've avoided by making a separate segment tree on each array.

I've thought about the advantages of using this technique, but I really couldn't find any.

I've found that, in both ways, I'm using the same amount of memory ($$$4\sum n = \sum 4n$$$), and both had the same speed.

So what I want to ask is, when does this technique give me real practical advantages to not use multiple segment trees in those cases? (other than HLD)

How to solve this?

You have queries of the following three types:

• $$$add(i, v)$$$: add an element with value $$$v$$$ at index $$$i$$$.

• $$$query(l, r)$$$: count the number of distinct values of elements on the range from $$$l$$$ to $$$r$$$ (inclusive).

• $$$remove(i, v)$$$: remove one of the elements with value $$$v$$$ from the index $$$i$$$.

Notes:

• let $$$Q$$$ be the number of queries of first and the third types, and $$$Q'$$$ be the number of queries of the second type, $$$1 \le Q \le 10^5$$$, $$$1 \le Q' \le Q\space log\space Q$$$.

• $$$1 \le v \le 10^5$$$.

• $$$0 \le i, l, r \le 10^8\space\space(l \le r)$$$.

• in $$$add$$$ queries some index might have multiple elements at the same time and some may share the same value.

• in $$$remove$$$ queries it is guaranteed that there will be at least one value at index $$$i$$$ which equals $$$v$$$.

• $$$query$$$ queries should be preformed online, but the the other two types can be preprocessed if needed.

• notice the unusual constrains over $$$l$$$, $$$r$$$ and $$$i$$$.

Is there is any way to do this in $$$O(log\space n)$$$ time for the queries of the second type and $$$O(log^2 n)$$$ or faster for the first the third types?

Hello, I was solving the problem 461B - Appleman and Tree but misread the problem statement — thinking that I have to calculate the number of ways such that each subtree has at least one black node, but I couldn't find a solution to this. Can anyone help me with this version of the problem?

Hello codeforces,

On this problem 1277E - Two Fairs, there is t test cases and I am using a vector<vector> ed(N) to store the edges of the graph, so in end of each test case I need to clear my vector ed so I created another one vector<vector> em(N) and it's empty all the running time, in the end of each test case I did ed = em to save time, but I were always getting a TLE on the 2nd test, and I don't know why. In the first submission 68468115, I did

vector<vector<int> > ed(N), em(N);
int main() {
  cin >> t;
  while(t--){
    ...
    ...
    ...
    ed = em;
  }
  return 0;
}

But when I did the following in this submission 68489443, I got an AC.

vector<vector<int> > ed(N);
int main() {
  cin >> t;
  while(t--){
    ...
    ...
    ...
    for(int i=0; i<n; i++) ed[i].clear();
  }
  return 0;
}

Can someone explain why I were getting a TLE on the first submission, even that in the first submission I were doing one operation but in the second one I were doing N operations.