0

I am veryamazed by this contest.

ezraft will apply ezraft to win ICPC NAC 2026

Nope, it's a joke from last year (organizers were debating whether or not to fill the balloons with helium, and someone suggested filling the gym with argon instead so that regular balloons would float)

Hey, they’re pretty good solutions!

Sorry. Online teams will not receive shirts.

I like the cat in the announcement

Everyone can participate. Middle schoolers are eligible for prizes since they are precollege.

We'll try to live up to the expectations :-)

studying.

Gratitude is a wonderful feeling for both parties involved :-)

Regarding this:

...we had many 1k+ upvoted announcements a few years ago but these days they are gone...

Here's a theory: could this have to do with the increase in cheating that seems to have been happening lately? Cheating is the ultimate form of disrespect and ingratitude, it makes sense that these same people would take all the amazing problems out there (available for free!) for granted.

Let $$$A=[1,2,3,1,5]$$$. If you set $$$A[4] := 4$$$ you get an answer of $$$5$$$.

But the LIS of $$$A=[0,2,3,1,5]$$$ gives you an answer of $$$4$$$.

me when i see arul hii arul

Sorry for the wait! We've just uploaded the written solutions to Dropbox.

Yessir: https://mirror.codeforces.com/contestInvitation/7eaef6721133a047c0bd60a7ad9d97e41d81aa8c

The number of states in our model solution is exponential, but writing a DP to count the worst-case number of states gets us around $$$2 \cdot 10^5$$$. Code included here (which we also used to generate some of the tests):

#include "bits/stdc++.h"

using namespace std;

#define ll long long
const int M = 100;

// sum so far, last one
ll dp[M + 1][M + 1];
pair<int,int> pv[M + 1][M + 1];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  dp[0][0] = 1;

  for (int i = 0; i <= M; i++) {
    for (int j = 0; j < M; j++) {
      for (int k = j + 1; k <= M; k++) {
        for (int l = 1; k * l + i <= M; l++) {
          ll nv = dp[i][j] * ((ll)(l + 1));
          if (nv > dp[i + k * l][k]) {
            dp[i + k * l][k] = nv;
            pv[i + k * l][k] = {i, j};
          }
        }
      }
    }
  }

  ll ans = 0;
  pair<int,int> st;
  for (int i = 0; i <= M; i++) {
    for (int j = 0; j <= M; j++) {
      if (dp[i][j] > ans) {
        ans = dp[i][j];
        st = {i, j};
      }
    }
  }

  cout << ans << "\n";

  vector<pair<int,int>> hv;
  while (st.first > 0) {

    int val = st.second;
    int diff = st.first;

    st = pv[st.first][st.second];

    diff -= st.first;

    hv.push_back({val, diff});

  }

  for (auto [x, y] : hv) {
    cout << x << " appears " << y / x << " times\n";
  }
  
}

One could even say the contest was LIT...

Thanks! We set it at 3 hours because we expected there to be many beginner teams that would have trouble working for a full 5 hours, but we'll see what feedback we get about this.

When will practice submissions be enabled? I'm not able to submit right now.

lunchbox hard carry orz

Looks like it should be fine, NAQ only starts 25 min after the round ends :)

I found this on google: link

In short, you sweep through all possible lines through the origin. Each one divides the points into two sets, and you consider each of those two sets as a possible answer.

Carnegie Mellon (USA, North America) will be kobortor, 4fecta, and BucketPotato.

I had the same issue, switching to HTTP Tunnel A seems to fix it.

The author set $$$k \le 142\,023$$$ ($$$1\,4\,2023$$$) to make the checker work quickly, the $$$10^{18}$$$/redacted business was intended as a bit of a red herring.

orz flamestorm

• I distinctly remember getting FST on 1567F - One-Four Overload from a n/m typo :( but the problem itself is good
• Your 1698F - Equal Reversal was useful to me while upsolving 1458D - Flip and Reverse, cute idea and both nice problems

Thank you — I've had the same thing on my mind for a while now and I'm happy to see someone posting about this.

My opinion: CF rounds are a privilege. Sponsors, authors, testers, and coordinators combined put in hundreds — or even thousands — of hours of work into creating every contest (not to mention the effort and money that goes into maintaining the CF website), and we get to enjoy the results of that labor for free. Sometimes authors make mistakes, this is inevitable for humans, but downvoting a round just for that reason is like throwing away a collection of gifts just because one was broken during shipping. It's a sign of ungratefulness. Participating in an imperfect round, in the worst case, maybe you lose a few hours of time and some internet points. That's no excuse for being ungrateful, especially considering how much effort everyone involved put into creating that contest.

My solution to A, which I grossly overcomplicated:

Luckly the code is pretty short compared to the explanation :P

Here's my solution to G. I think it's somewhat similar to the editorial. It looks long and complicated, but I've tried to thoroughly explain the motivation behind it, the central idea is fairly straightforward, and I think all the steps are pretty intuitive. I hope it can help anyone confused by the main editorial.

XXXXX
X....
X....
X....
X....

...XX
...X.
.XXX.
.X...
XX...

EFGHI
DEFGH
CDEFG
BCDEF
ABCDE

..XXX
...XX
X...X
XX...
XXX..

..XFF
.XX.F
.X..Y
FX.YY
FFYY.

.....
!....
F!...
FF!..
FFF!.

.....
.....
S....
FS...
FFS..

My AC code: 174160936

You could use a private group (create one under the GROUPS tab) to post. It would also allow you to choose who can see the blogs :)

You're right, that's my mistake. It will be fixed soon.

Actually, in the original version of the round, B and C were swapped. But feedback from testers suggested that their current placement would be better.

The main idea is the same, but the way you go about it is different:

Your solution uses a vector<list<int>> to help determine cmx (using variable names from your code), and has to update the lists as you sweep through.

The intended solution also finds all values of cmx, but uses the additional idea of prefix maxes on increasing functions to simplify the memory usage to a single int pf[100000 + 1].

Sorry, the link has been fixed

Sorry about that. Try again?

Hi, the intended solution codes for D2 have now been posted (here and here). IMO, the implementation in both is very clean and easy, no optimizations needed.

As I said in a different comment, the difficulty in this problem seems to lie on whether you want to painfully optimize a simple idea or think a little more to find a nicer solution.

Sorry to hear. What did you dislike about D?

You're right. Unfortunately none of the setters or testers came up with this idea :(

Sorry to hear :(

Our correct intended solutions take some more thinking, but have clean and easy implementations (no optimizations needed).

So I guess the difficulty of this task was in, do you want to optimize your code or think of a cleaner solution?

(copy-pasted from here)

There is a $$$n \sqrt n$$$ two-pointers memory solution in D2 that we wanted to cut off. We decided it would be fine since all of the correct $$$O(n)$$$ memory solutions (from testers, authors, and the coordinator, including in Python and Java) use less than 1/6 of that memory.

Sorry for the trouble, there is a $$$n \sqrt n$$$ two-pointers memory solution in D2 that we wanted to cut off. We decided it would be fine since all of the correct $$$O(n)$$$ memory solutions (from testers, authors, and the coordinator, including in Python and Java) use less than 1/6 of that memory without any optimizations.

As for the difficulty, there was originally a problem F, but testing suggested that up to E was hard enough.

Originally, the statement looked something like this (this is a very condensed version of it):

You are preparing carrots to cook. The carrot can be modeled as a non-decreasing array, and your chopping skills are represented by an integer k. The roughness of an array p is max(a / p) — min(a / p), find the minimum roughness of the carrot you can achieve.

The flavor text was ultimately taken out since testers found it made the statement more confusing.

(sorry if this is a bit long/confusing, I'm not the most experienced at explaining)

First off, imagine choosing some subset of the letters in $$$s$$$ that form $$$t$$$: for example if $$$s$$$ is zzzabczzz and $$$t$$$ is abc, then the abc is useful but all the zs are useless fluff.

Then you want to delete all the fluff. Here's one approach: first, you delete fluff from the end of the string until you come to useful letters. Then, you iterate past the useful letters, until you come to more fluff to delete. Repeat until all the fluff is gone.

This may not always be optimal, for example if $$$s$$$ is zaaaa and $$$t$$$ is aaaa: then you want to go to the start, go forward, and delete the singular z.

When you're deleting fluff from the back, it takes $$$1$$$ operation to iterate past useful letters and $$$1$$$ operation to delete the fluff. When you delete fluff from the beginning, it takes $$$1$$$ operation to iterate past useful letters, but $$$2$$$ operations to delete fluff (you need to iterate forward then delete).

Then, the optimal solution will look something like this: there is some prefix (possibly empty) of the string where you've deleted from the beginning, then some contiguous segment of useful letters you haven't iterated over, and finally, some suffix of the string where you've deleted from the end.

If the prefix isn't empty, then it needs $$$2x+y+1$$$ operations, where $$$x$$$ is the number of fluff characters in the prefix, and $$$y$$$ is the number of useful characters. Otherwise it takes $$$0$$$ operations.

Next, the contiguous segment of useful letters, this takes $$$0$$$ operations since you don't iterate over it at all.

Finally, for the suffix, it takes $$$x+y$$$ operations.

At least in my solution, the dp[3][N] was something like this: 0 for the prefix, 1 for the contiguous segment, and 2 for the suffix. The transitions were somewhat tedious to implement but fairly straightforward.

1. If $$$gcd(x+i, x+i+lcm)$$$ is divisible by some integer $$$y$$$, then $$$x+i \equiv 0 \mod y$$$, in other words $$$x \equiv -i \mod y$$$.

2. All the prime integers I’m using as modulos for the CRT (2, 3, 7, 11, 13, 17, 19, 23, 29) are less than 30, so it’s certain that for each of them, at least one integer in $$$[x, x+30)$$$ divides it.

153047261

I used the CRT implementation from this blog.

Maybe you can use 1508D - Swap Pass as an example. It looks like they use this:

\begin{center}
\includegraphics{sample1.png}
\end{center}

Where sample1.png is an apng (animated png) file. You can convert gifs to apng here.

My approach to F2 seems a bit different from the editorial's:

Say $$$dp_i$$$ contains all values $$$(ind_j, v_j)$$$, sorted by $$$ind_j$$$, such that it is possible to get an increasing subsequence with an xor of $$$v_j$$$ and last element at index $$$ind_j$$$, using only elements in the array less than or equal to $$$i$$$. If there are multiple possible values for one $$$v_j$$$, only store the one with the minimum $$$ind_j$$$.

To transition from $$$dp_{i - 1}$$$ to $$$dp_{i}$$$, first, add all elements already in $$$dp_{i-1}$$$ to $$$dp_i$$$. Then, for each $$$(ind_j, v_j)$$$ in $$$dp_{i-1}$$$, take the minimum index $$$k$$$ such that $$$a[k] = i$$$ and $$$k \gt ind_j$$$. Then, add $$$(k, v_j \oplus i)$$$ to $$$dp_i$$$ (if this $$$k$$$ does not exist, don't do anything). This can be done in linear time with two pointers if you store the occurrences of each $$$i$$$.

Two important details:

1. To make sure that each $$$dp_i$$$ remains sorted, while transitioning, you can store the values $$$(k, v_j \oplus i)$$$ and $$$(ind_j, v_j)$$$ in two separate vectors, since each of these separately will be sorted. Then, combine the two in linear time (same method used in mergesort).
2. To make sure you only store the minimum $$$ind_j$$$ for each $$$v_j$$$, you can keep track of the minimum value $$$ind_j$$$ for each $$$v_j$$$ with an array $$$minindex$$$. Then, only add a pair $$$(ind_j, v_j)$$$ to the dp if $$$ind_j = {minindex}_{v_j}$$$.

My code: 132932565

Just a heads up, there's a small error in the announcement:

five Kotlin Heroes competitions which were held previously

Anyhow, looking forwards to this contest!

New accounts get a boost in their rating changes for their first 6 contests. You can see Mike's blog here for more details.

The LCM might be very large and overflow, e.g. $$$lcm(99971, 99961, 99929, 99923, 99907) = 9969136729118531781864539$$$ will not fit a 64-bit integer.

Thanks for the problems! I could tell that the problemsetters put a great deal of effort into making this contest.

Don't ever upsolve. If a problem appears at one contest, what is the chance it will appear at another? - Gennady Korotkevich

You aren't alone; this seems to be a common issue. The way I usually get around it is double-clicking on the graph until it zooms in to the point where I can click on the box without a different one appearing.

This blog should answer your questions.

I believe problems A, B, C, and D1 had 3 pretests each.

PurpleCrayon is a skilled programmer, and I'm excited to see the tasks he and ijxjdjd have prepared. Good luck to all participants, and hopefully we can see more crayon rounds in the future!

I'm assuming that this stress is coming from the prospect of losing rating or getting a low rank on the scoreboard. It can be demoralizing to see everyone else solving difficult tasks while you're stuck on the first problem.

I find it helpful to think of it this way— a contest you do poorly on shows you more clearly what you need to improve on, and provides you with problems to practice those skills. You can always regain rating in a later contest— for now, just try to solve problems and have fun. A single contest doesn't define your coding career.

Say you choose some value a such that l < a < r, and you've already chosen some value b for another node. If a ≥ b, then adding 1 to a will increase |a - b|. Otherwise, subtracting 1 will increase it. You can keep adding/subtracting until you get to l or r, and get a max value.

This blog should help explain the calculations.

looking forward to a contest where gyrating cats can participate

The most I've ever had was 124 submissions on a POJ suffix array problem... I can't really say I had fun debugging, but it did feel great when I finally got it accepted :)

Thank you for the problems!

Thank you for the contest!

Thanks for the contest :)