Блог пользователя ankitkumar1234__

Автор ankitkumar1234__, история, 2 недели назад, По-английски

Hey Codeforces community,

The recent selections for the ICPC India Amritapuri Regionals just dropped, and the current selection algorithm feels increasingly broken for competitive programming as a sport.

In the preliminary round, we solved 6 problems (A-E and H) and finished with an overall rank of ~450. However, because we were College Rank 2 at our institute, we did not get selected for the regionals.

Meanwhile, teams with a global rank around ~3700 are advancing simply because they hold the College Rank 1 spot at their respective universities, often with only 1 or 2 solves.

It is incredibly frustrating to see top-500 teams get boxed out by 1-solve teams purely due to institutional diversity quotas. Guaranteeing spots to smaller colleges might help grassroots participation, but the current math heavily penalizes secondary teams at competitive colleges to the point where absolute merit is completely ignored.

I understand the underlying philosophy: ICPC wants to promote grassroots competitive programming across as many colleges as possible. Guaranteeing a slot to the top team from every college encourages participation and justifies registration fees for smaller institutions. But there has to be a limit to how heavily meritocracy is penalized in the name of ecosystem growth.

Is this really the best way to foster elite competitive programming?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +56
  • Проголосовать: не нравится

Автор ankitkumar1234__, история, 2 месяца назад, По-английски

Author ~Hamed_Ghaffari, While reading Problem E in today's Codeforces Round 1124 (Div. 2), I noticed an interesting visual similarity to a problem concept I was working on recently. While Problem E focuses on a fixed range with a range maximum, my version involves arbitrary array rearrangement and full partitioning into disjoint subsets.

You are given an array $$$A$$$ of $$$N$$$ integers. You may rearrange the elements of $$$A$$$ in any arbitrary order to form a new array $$$A'$$$.

After rearranging, you must divide $$$A'$$$ into $$$m$$$ ($$$m \ge 1$$$) contiguous, disjoint subarrays $$$S_1, S_2, \dots, S_m$$$ such that every element of $$$A'$$$ belongs to exactly one subarray.

Let $$$F(S)$$$ denote the bitwise AND of all elements in a subarray $$$S$$$:

$$$F(S) = \bigwedge_{x \in S} x$$$

Version 1 (Feasibility Check): Given an integer $$$K$$$, determine if there exists a valid rearrangement and partition such that:

$$$F(S_1) \oplus F(S_2) \oplus \dots \oplus F(S_m) = K$$$

Version 2 (Maximization): Find the maximum possible value of:

$$$F(S_1) \oplus F(S_2) \oplus \dots \oplus F(S_m)$$$

among all valid rearrangements and partitions of $$$A$$$ .

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор ankitkumar1234__, история, 12 месяцев назад, По-английски

I’m stuck on the following dynamic MST problem.

You are given an undirected, weighted graph with N vertices and M edges. The graph will undergo Q dynamic operations. After every operation, you must output the total weight of the current Minimum Spanning Tree (MST). The test data guarantees that an MST always exists after every operation.

Initial Graph:

  • Vertices are numbered from 1 to N.
  • The graph initially contains M edges.
  • Each edge is specified as:   u v w   representing an undirected edge between u and v with weight w.

Query Types:

  1. U u v w   Update or insert an edge.   * If an edge (u, v) already exists, change its weight to w.   * Otherwise, insert a new edge (u, v) with weight w.

  2. D u v   Delete an edge between u and v, guaranteed that it always exist.

Output: After each query, print the total weight of the MST of the current graph. The input guarantees that the graph always remains connected, so an MST always exists.

Constraints: 1 ≤ N ≤ 200000 0 ≤ M, Q ≤ 200000 1 ≤ u, v ≤ N 1 ≤ w ≤ 1e9

Help me in solving in this problem.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится