Osama_Alkhodairy's blog

By Osama_Alkhodairy, 6 months ago, In English

Codeforces now has 342281 testcases. But how many of these are actually relevant?

Let's call a test redundant if nobody has ever submitted a solution that failed on that test. Here's a graph showing what percentage of testcases are redundant over all rounds.

Turns out to be that 173195 tests out of the 342281 tests are actually redundant — no verdict would change if these tests were never there. That's around 50%. I actually expected more, but still, a lot of testcases are redundant.

Here is another representation of data, where the y-axis shows how many problems of each percentage of redundancy.

Codeforces can take advantage of this and save resources by not running these tests at all. But how long should we wait before deciding that the current non-redundant testcases are enough?

As you can see a lot of problems get saturated in the first month. But many others don't; however, don't treat these non-redundant testcases as absolutely essential because a solution failing at one of them doesn't mean that it passes all others (for example, all problems have solutions failing at the first testcase).

How many testcases, do you think, does a problem need on average if we were to pick them the most optimal way?

Thanks zoooma13 for sharing ideas and helping collecting the data.

Read more »

 
 
 
 
  • Vote: I like it
  • +282
  • Vote: I do not like it

By Osama_Alkhodairy, history, 8 months ago, In English

I was checking this problem on csacademy, and I came up with the dp combinatorics solution to calculate the number of topological orderings of a directed tree with a fixed root.

First, let me explain this solution. Let's root the tree at node $$$1$$$ and calculate $$$sz_v$$$ = size of the subtree rooted at $$$v$$$. Let $$$dp_v$$$ be the number of possible topological orderings of the subtree rooted at $$$v$$$. To calculate $$$dp_v$$$, let's imagine $$$v$$$ has only two children: $$$x$$$ and $$$y$$$. We can see quite easily that $$$dp_v = dp_x * dp_y * {sz_x+sz_y \choose sz_x}$$$. That's because any valid topological ordering of the subtree of $$$v$$$ will begin with $$$v$$$ itself and then $$$sz_x+sz_y$$$ nodes, and because the nodes of $$$x$$$'s and $$$y$$$'s subtrees are independent, all possible combinations between them are possible. So, we will choose $$$sz_x$$$ spots of the $$$sz_x+sz_y$$$ spots and put in them all the nodes form $$$x$$$'s subtree and put on the rest the nodes from $$$y$$$'s subtree. Of course, after assigning how we will combine the two subtrees, we can permute the nodes in these spots as long as these permutations are valid; that's why we are multiplying by $$$dp_x*dp_y$$$. What if $$$v$$$ has more than two children? We will loop over them and do the same thing accumulatively. The final expression after some reductions looks like this: $$$dp_v = \frac{(sz_v-1)!}{\prod sz_u!} * \prod dp_u$$$, where $$$u$$$ is a child of $$$v$$$. Actually we can reduce this further to $$$dp_v = \frac{sz_v!}{\prod sz_u}$$$, where $$$u$$$ will loop over all nodes in $$$v$$$'s subtree.

I felt really unsatisfied after all these reductions because the final expression didn't make sense on its own. But here's a simpler way to think about it without going through all of this.

The number of valid orderings for the whole tree is $$$dp_1 = \frac{n!}{\prod_{v=1}^{n} sz_v}$$$. Here, $$$n!$$$ represents all possible permutations. Of course, not all of them are valid. For example, the first element of any valid permutation must be $$$1$$$ (the root), and that's why we are dividing by $$$sz_1$$$. More generally, let's go through the subtrees from the largest to the smallest and perform the division. When considering a subtree, the root of that subtree must appear before all the other nodes from the subtree in the permutation. As we are going over the subtrees from the largest to the smallest, all the permutations of the current subtree contribute to the answer. However, not all of them are valid; we want to fix the root of the subtree in the beginning, so we divide by $$$sz_v$$$, so that, now, the current subtree is contributing to the answer by a factor of $$$(sz_v-1)!$$$, instead of a factor of $$$sz_v!$$$ (because we are fixing one of the nodes).

I found this way of thinking about it much more insightful than the way with reductions, so I wanted to share it with you.

Read more »

 
 
 
 
  • Vote: I like it
  • +88
  • Vote: I do not like it

By Osama_Alkhodairy, 11 months ago, In English
Tutorial is loading...
code
Tutorial is loading...
code
Tutorial is loading...
code
easier implementation
Tutorial is loading...
code
Tutorial is loading...

Author: MikeMirzayanov

code (pikmike)
Tutorial is loading...
code (mohammedehab2002)

Read more »

 
 
 
 
  • Vote: I like it
  • +132
  • Vote: I do not like it

By Osama_Alkhodairy, 11 months ago, In English

Hello Codeforces!

We are glad to invite you to Codeforces Round #613 (Div. 2), which will be held on Jan/10/2020 17:05 (Moscow time). The round is rated for Div. 2 contestants. There will be six problems with a duration of 2:15

The problems were prepared by me, mohammedehab2002, DeadPillow, and MikeMirzayanov.

I'd like to thank pikmike for coordinating the round, dorijanlendvaj, aryanc403, Ari, ZeroAmbition, defolaut, Pavlova, mahmoudbadawy, zoooma13, Mohammad_Yasser, Rox, and BledDest for the invaluable testing, and MikeMirzayanov for great Codeforces and Polygon systems.

Good luck!

UPD1: We decided to add one more problem and extend the duration to 2:15 to make the contest more balanced.

UPD2: Score distribution: 500-1000-1250-1750-2250-3000

UPD3: Editorial is out.

UPD4: Thanks for participating! Congratulations to the winners:

Div. 1 (unofficial) participants

  1. Benq
  2. tzuyu_chou
  3. Andreikkaa
  4. neal
  5. mango_lassi

Div. 2 participants

  1. fmota
  2. FSTForces
  3. yet_another_ATS
  4. iwasa
  5. DP_I_J_K_L_M_N_O

Read more »

 
 
 
 
  • Vote: I like it
  • +401
  • Vote: I do not like it