### yubowenok's blog

By yubowenok, 3 months ago,

Are you fascinated by programming? We, the IEEEXtreme 15.0 Executive Committee, are opening the registrations for a select few judges and problem authors.

IEEEXtreme is a global challenge in which teams of IEEE student members compete in a 24-hour time span against each other to solve a set of programming problems authored by industry professionals and coding experts like yourself. Over the 15 years since it began, the competition has attracted over 70,000 competitors from over 2,500 schools in 90 countries around the world.

This is an opportunity where you can not only develop the coding challenges but also you can evaluate them while having the opportunity to associate with some of the top experts in the field. The judging staff of IEEEXtreme are all volunteers who strive to make the contest a fun and exciting experience for all.

Judges responsibilities may include one or more of the following:

• Develop at least 1 original and innovative problem. You may see examples of the format of the IEEEXtreme problems here: https://csacademy.com/ieeextreme-practice/
• Review and evaluate the problems proposed by another judge and provide feedback;
• Provide independent solutions to other proposed problems using any of the competition programming languages;
• Be online during the day of the competition for 1-2 hours based on their availability in order to address the contestants' questions related to the authored challenge.

While not everyone who submits a nomination will be selected, we will carefully review all nominations and thank you in advance for your time to express your interest! We look forward to welcoming you aboard to the IEEEXtreme community!

Please apply using this form on or before 2021/09/19.

More delineations can be acquired from: ieeextreme.problems@gmail.com

• +18

 » 3 months ago, # |   0 My background is in high-performance computing, would this competition include challenges that require parallel and/or distributed execution?
•  » » 3 months ago, # ^ |   0 Though we currently do not have distributed program execution infrastructure for the contest, IEEEXtreme's do have creative tasks that are a bit different from standard algorithm questions :)
 » 6 weeks ago, # |   +19 can the problem authors share the editorial of the contest ?
•  » » 6 weeks ago, # ^ |   0 Or at least the data for input/output
 » 6 weeks ago, # |   0 Is it still possible to become Problem Author?
 » 6 weeks ago, # |   +12 Could anyone show me how to do problem The tortoise and the hare and problem Candy Shop? The problems are with high quality in my opinion. It would be incredible if somebody help me. Thanks.
•  » » 6 weeks ago, # ^ |   +3 I couldn't solve these problems during the contest but I found this paper for "The tortoise and the hare" after the contest ended and I was able to get AC implementing this idea.
•  » » 6 weeks ago, # ^ |   +19 There is editorial of Candy Shop. Short editorialProblem can be solved using dp with optimizations based on operations with formal power series. After some conversions the following formula can be obtained: $A(x) = \prod_{i=1}^{n}\frac{1 - x^{(1 + a_i) \cdot b_i}}{1 - x^{b_i}}.$Calculate this expression and output coefficient at $x^k$. Full editorialThis task can be solved using dynamic programming. State $dp[i][j]$ is count of sets of size $j$ that can be construct using first $i$ types of candy. Transitions in dynamic programming: $dp[i + 1][j + q \cdot b_i] = dp[i + 1][j + q \cdot b_i] + dp[i][j], (0 \le q \le a_i, j + q \cdot b_i \le k)$. Answer is $dp[n][k]$. This solution have complexity $O(n\cdot k^2)$ and doesn't fit in time limit. All transitions for fixed $i$ can be done in $O(k)$ using prefix sums. Thus, complexity is $O(n\cdot k)$ but it's slow too.Let's try speed up solution using multiplying polynomials. Let $A_i(x) = \sum_{j = 0}^{k}dp[i][j] \cdot x^j,$than $A_{i+1}(x) = A_i(x) \cdot \left( \sum_{j=0}^{a_i}x^{j \cdot b_i} \right).$From this recursive expression, we can deduce that $A_n(x) = \prod_{i=1}^{n} \left( \sum_{j=0}^{a_i}x^{j \cdot b_i} \right).$Coefficient of the $k$-th degree $A_n(x)$ is answer to the problem. Multiplying polynomials of this kind is not convenient to calculate. Notice that $\sum_{j=0}^{a_i}x^{j \cdot b_i} = \frac{1 - x^{(1 + a_i) \cdot b_i}}{1 - x^{b_i}},$than expression for calculating $A_n(x)$ can be rewritten as follows: $A_n(x) = \prod_{i=1}^{n}\frac{1 - x^{(1 + a_i) \cdot b_i}}{1 - x^{b_i}}.$This expression can be solved using technique for solving subset sum problem. Let's perform the following transformations: $A_n(x) = exp \left( ln \left( \prod_{i=1}^{n}\frac{1 - x^{(1 + a_i) \cdot b_i}}{1 - x^{b_i}}\right) \right) = exp \left( \sum_{i=1}^{n} ln \left(\frac{1 - x^{(1 + a_i) \cdot b_i}}{1 - x^{b_i}}\right) \right) =$ $= exp \left( \sum_{i=1}^{n} ln \left(1 - x^{(1 + a_i) \cdot b_i} \right) - \sum_{i=1}^{n} ln \left( 1 - x^{b_i}\right) \right) = exp(L(x) - R(x)).$We use the Taylor series formula to calculate logarithm: $log(1 + x) = -\sum_{t=1}^\infty \frac{(-1)^t\cdot x^t}{k}$. Thus, we get: $L(x) = - \sum_{i=1}^{n} \sum_{t=1}^{\infty} \frac{x^{(1 + a_i) \cdot b_i \cdot t}}{t} .$Let's rewrite this expression modulo $x^{k + 1}$ (the coefficients at large powers are not of interest to us): $L(x) \ mod \ [x^{k+1}]= - \sum_{i=1}^{n} \sum_{t=1}^{\left\lfloor\frac{k}{(1 + a_i) \cdot b_i}\right\rfloor} \frac{x^{(1 + a_i) \cdot b_i \cdot t}}{t} .$Let $cnt_j$ is the count of $i$ that $j = (1 + a_i) \cdot b_i$. Then the formula takes the form: $L(x) \ mod \ [x^{k+1}] = -\sum_{j=1}^k \sum_{t=1}^{\left\lfloor\frac{k}{j}\right\rfloor} \frac{cnt_j \cdot x^{j\cdot t}}{t}.$Polynomial $R(x)$ can be calculated as well: $R(x) \ mod \ [x^{k+1}] = -\sum_{j=1}^k \sum_{t=1}^{\left\lfloor\frac{k}{j}\right\rfloor} \frac{cnt_j^{\prime} \cdot x^{j\cdot t}}{t},$where $cnt_j^{\prime}$ is the count of $i$ that $j = b_i$.Polynomials $L(x)$ and $R(x)$ can be calculated in time $O(n + \sum_{j=1}^{k}\frac{k}{j}) = O(n + k\cdot log(k))$.Let $P(X) = L(x) - R(x) = \sum_{i=0}^{k}p_i \cdot x^i$. We need to calculate $G(x) = exp(P(x)) = \sum_{i=0}^{k}g_i \cdot x^i$ to get answer. There are many ways to calculate the exponent of the polynomial. For example we can differentiate $G(x)$: $G^{\prime}(x) = G(x) \cdot P^{\prime}(x)$ and get recursive expression for coefficients: $g_i = \frac{\sum_{j=0}^{i-1}(i-j)\cdot g_j \cdot p_{i-j}}{i}.$This expression for each $i$ can be calculated using technique ''meet-in-the-middle'' and fast Fourier transform with complexity $O(k\cdot log^2(k))$.Answer to the problem is the coefficient of the $k$-th degree of the computed polynomial. Complexity of the solution is $O(n + k\cdot log^2(k))$.
•  » » 6 weeks ago, # ^ |   0 The tortoise and the hare can be easily solved with the same ideas in 1163F - Indecisive Taxi Fee's editorial. Basically you want to see which edge has a prefix shortest path from S and suffix shortest path from T which doesn't intersect with the entirety of the original shortest path and find the minimal of those paths.
•  » » 6 weeks ago, # ^ |   0 I would also appreciate an explanation for Polygon
 » 6 weeks ago, # | ← Rev. 3 →   +3 I really like the problems. The problemset was very diverse and interesting, although I suppose it was harder for beginners than previous editions. I also like the 24-hour format with few problems being released each hour, it's unique.However, in all the times that I've participated in this competition, I've never found an editorial after the contest ends (if there is a place where ieeextreme editorials are posted, please let me know). If you could provide an editorial for at least some problems, it would be really appreciated.
 » 6 weeks ago, # |   0 Is it possible to participate in this contest without joining IEEE and getting spam mails (including physical mails btw) every day?
 » 6 weeks ago, # |   +3 Did somebody get 100% on problem "Big Matrix Small Determinant"? I'm stuck trying to get over 50% :(.
•  » » 5 weeks ago, # ^ |   +3 I did because I am an author
•  » » » 5 weeks ago, # ^ |   0 Could you give me some hints? :^)
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Hint $1$: read the first answer hereHint $2$: find a matrix with the needed number of odd numbers and with an odd determinant. Using it, you can get the required matrix. @@@ solution On finding a matrix with an odd determinantIt's equivalent to finding a nondegenerate matrix in $\mathbb{Z}_2$ with the required number of $1$ s in each row. Btw, at this point, it's obvious for which cases the answer is $\text{-}1$. Assuming the answer exists, generate each row randomly until it's linearly independent of previously generated rows (exercise: proof the existence of at least one linearly independent row at each step). Oh, and if you have $a_i = n$ in the input, then generate that row before others. On getting from the odd determinant to 1You have a matrix of $0$ and $1$ with the required number of $1$ in each row. Run Gaussian elimination (in $\mathbb{Z}_2$) to get a triangular matrix. Go back to $\mathbb{Z}$ and run the steps of the performed elimination in the reversed order. You'll get a matrix with the needed number of odd numbers and its determinant is $1$ or $\text{-}1$.
 » 6 weeks ago, # |   +6 How to do the interactive problem Secret boxes?Thanks.
•  » » 6 weeks ago, # ^ | ← Rev. 5 →   +4 Hint 1If you know the location of the box with one candy and the box with two candies, you can compare two boxes in one query, and sort the array ($a < b$ if and only if $a + 1 < b + 2$ for different $a, b$) Hint 2Given 4 boxes, we can always eliminate at least one box for not being the box with one / two candies, in three queries (asking all possible pairings) How?Suppose our boxes have $a < b < c < d$ candies. We will ask all three possible queries: $a, b$ vs $c, d$: Obviously the result will be $<$ $a, c$ vs $b, d$: Once again, $<$ $a, d$ vs $b, c$: This is the interesting case, as all three symbols can occur. Anyway, the claim is that a box with a maximal amount of wins (strict wins) will never have one or two candies (not the, as there can be multiple). The proof is by casework, which I won't do here :D. SolutionTherefore, we can start with every box, select a quadruplet and eliminate the box selected by the process above. We will end up with three boxes, such that the boxes with one and two candies are among them. I will leave it to you to figure out how to eliminate the last box. After that you sort and finish.
 » 5 weeks ago, # | ← Rev. 2 →   +9 Ok, I just solved Big Matrix Small Determinant and that got me thinking again about something that has bothered me about IEEEXtreme for a long time.It is not such a hard problem; the fact that it was unsolved during the contest and has 2 solves in upsolving really shows something about the level of the contest. None of the really good and strong universities (I mean WF medalist strong) ever participated during my participation.I really enjoyed the unique format of IEEEXtreme every time I participated, and I would really like to continue participating in the future. The problem quality varies a lot, but it has improved consistently. And the prizes are respectable.Here's the thing though. Actually getting to participate in the contest seems hard. You need to be a student in an university, and then you need someone who is a full member of the IEEE to proctor. Why is the IEEE membership necessary? I think it is actually a pretty big hurdle to overcome. And honestly, I don't think it should be limited to students either.I also think that the IEEE hasn't done enough to reach out to the competitive programming community. It seems to exist in isolation. Competitive programmers don't know what it is, and the people who actually do participate don't know what competitive programming is. This year is the first time I actually see a post on Codeforces, all the previous years I have only heard of this contest because by happenstance, someone at my university heard of it once and started organizing it.