Hello Codeforces.
We are introducing a new type of problem which may appear in future Codeforces rounds, called Communication problems!
In these problems, your program would be ran twice, with different input and output formats between the runs. All variables stored in the memory will be lost between runs. However, the information given to you on the first run may be important to you for completing the second run correctly. Therefore, one of the key challenges in these types of problems would be to find a way to use the limited amount of output you are given in the first run to communicate information to the second run. Below shows a flowchart.
Flowchart for communication problems
In these problems, time and memory limits for both runs would be kept separately. For example, if a problem has a time limit of $$$2$$$ seconds, you will only get the Time Limit Exceeded if program runs for more than $$$2$$$ seconds on one of the runs, but not if both runs takes $$$1.5$$$ seconds.
It is also possible that a problem is both interactive and run-twice. There may be interaction on either run of your program. For these types of problems, it is especially important to read the problem statement carefully to ensure you are getting the input and interaction format correctly, especially regarding whether you must flush your outputs.
To give participants a feel of these new types of problems, we will hold Testing Round 20 (Unrated, Communication Problems), which will start on Nov/03/2025 17:35 (Moscow time). You will be given $$$1$$$ hour to solve $$$3$$$ run-twice problems. The problems are authored by cry, yse, SpyrosAliv, and chromate00. One problem on the set will be interactive, so you are recommended to read the guide for interactive problems if you are unfamiliar with these types of problems. Of course, this round will be unrated. Good luck, and I hope you will have fun with the new type of problem!
Edit: The contest will be in ICPC format with no pretests and hacks disabled.
Auto comment: topic has been updated by Proof_by_QED (previous revision, new revision, compare).
$$$67$$$
wow
sybau
cry meant this inspiration N which is also a run twice problem
PHSCO MENTIONED !!!
Oh no...
So now we solve for alice and bob, yaay
Anthony and Catherine :)
As Competitive Programmers, we already have communication problems.
hope that this test round fix it
Me to my child : And thats how my contribution increased !
damn true!
damn!!
soo true . :( .
I'm Excited..
As a tester, wait where is the tester list.
As a tester, if the tester list is not posted, can we participate?
It's a Testing Round! I guess that makes everyone the testers!
bro won't get any more upvote ;))
if everyone is a tester, then no one is
Any good advice on how to test communication problems locally in a fast and simple manner? Because for interactive problems it's the most painful part despite problems themselves being fun.
It will be better for communication problems than interactive ones. Because you just need to copy the data, run it once, copy the result, then run it again. There is no need to think what should be input like interactive problems.
the input for the 2nd run will be dependent on the output of the 1st run, it doesn't mean it'll be the same. well we'll get to know today
Well, now I know it depends. You are right. It happens to me that there may be even harder situations. XD.
On olympiads the problem author gives an archive file containing a program that will test your code automatically for both interactive and communication problems, and I would definitely like seeing that implemented in codeforces. One can only hope.
My crush already ran twice (away from me)
Mine was disabled,still managed to do so
My subscription money ran out too.
This being posted one week after my run-twice problem in PHSCO is a pretty funny coincidence lol
Either way, run-twice is a very under-appreciated problem format in Codeforces and I'm excited for its debut in a future rated round!
Also, will this contest mean that Codeforces will give better debugging feedback for run-twice problems (i.e. sample verdicts)? Because a big issue with run-twice right now is that the only judging information shown is the input during the first run and the output during the second run (first run output and second run input is notably hidden).
Will the run-twice problem(s) being announced in contest post like interactives? When will the first rated contest using this new setup of problem?
Would this format help combat AI? I think interactive problems are generally harder for chatGPT to figure out (is this true?). If we make interaction non-trivial, we have more potential choke points.
Around half a year ago (probably before o3 and o4-mini) that might have been true. But now, judging from their performance at IOI 2025, I suppose we can't be so sure about it. Similar to interactive problems, the coordinators need not (and probably should not) care about AI when choosing such problems for rounds.
It got the least amount of points on the communication problem. So, it might be correct to say that it performs worse on communication problems relatively to batch problems. And maybe it's due to the fact that #communication_problems << #batch_problems, thus less data for it to train on.
Even 65 points was not easy on that problem. Notice that a plenty of Gold and Silver-winners could not get past 65, let alone 30.
I guess it's subjective then; I got 85 on it but could not do that well on batch problems.
It got the least point on that problem, because that problem is the hardest problem in the contest. Your comparison would make sense if you were comparing batch vs communication of the same difficulty.
by "hardest" you mean, the only problem which was not solved during the contest. Notice that it's not the one with the least average points. I mean, 75 people got more than 65 points, so AI should be able to do that kind of stuff no?
Judging AI by just from their performence in IOI is wrong. Not because AI didn't do that, AI in fact did do that. But what's not being told is that google and microsoft consumed hundreds of thousands of dolars worth of electricity trying to get those scores, and no AI company is going to give access to that to a customer paying 20$ or so per month. Yes, AI is good. But it costs a lot. And there is no way in it's current state it's going to be solving IOI problems for the average customer.
Did I reject that? Everyone knows this and it's neither a secret nor a surprise. The point is not that the model is too strong, it's that their "expected rating" isn't any different with regard to problems with different formats.
WOW
Similar type of problem
it might be helpful to share approx difficulty level of these problems so that I can decide if I should take part ...
I am fascinated by this new problem type, but also curious about why authors conceived of this new problem type.
A very interesting problem type. Looking forward to seeing these problems in following codeforces rounds!
Seems interesting... Let me too register for this and help in testing
new type of interactive-like problem, yum yum
As a non-tester, I hope to be a part of this testing round. (Does that actually make me a tester?)
As fun as it might be, I'm definitely cooked. I still haven't gotten the hang of interactive
Dope!
As a participant, am I going to test?
DREAMS DO COME TRUE
This is a testing round, so if I participate, I will be a tester.
Finally, codeforces supports communication problems!
Nice
i dont understand this
It’s basically that your program is going to run twice (during each run the memory is going to erase). The judge is going to take the output from the first run and going to use as input for the second run. Think about implementing an algorithm that could perfectly reconstruct the original data.
It would be nice to have a "Communication" tag for these problems
:fire:
So the only CF round where all participants are testers !?!?
It's the 18th (I know it says testing round 20, but rounds 17 and 18 are non-existent on the contest list)
Very interesting problem type. Next update to this would be 'run k+1' times where k would be decided in the first run.
Bold of you to assume i have any communication skills
Will the tasks be similar to oj.uz communication? For example https://oj.uz/problem/view/JOI21_shopping
Hopefully, Olympiad organizers in Syria won't see this as a chance and decide to organize our TST on codeforces
can someone provide communication based problems difficulty wise from various platforms please ? atleast 5-6?
A lot of those problems can be found in The 2nd Universal Cup. Stage 16: Run Twice. IOI has also had such problems for a few years, but probably their different "implement the function" format is not the best for practicing in the same format as Codeforces will have.
I can imagine that this will be very tedious to debug without a grader :'(
I absolutely have no idea how this will work. Could someone please explain how it differs from conventional contest problems?
Can we just solve the problem in the first run and then transfer it through compression algorithms to the second run and then decode? Is this solution meant for these problems or not? Or, both is okay?
Depends. You can check out the various type of problems of this format on the contest I linked above. Sometimes it's about devising a compression method, sometimes it can be about devising a way to make the data resistant to error, or sometimes it can be something else!
What will we get in the future? Simulation Problems?
I would like to see approximation algorithms represented.
AI cheaters: sobs...
They're soooo done haha
Are the problems going to be actual problems? Or will it be print a + b difficulty to test that the grader doesn’t explode?
Is the purpose of this new problem-type to prevent cheating ?
No
In the Russian community, such tasks are called "Double-run tasks" (Задачи с двойным запуском). The most popular of them is to implement the "Hamming code" (you must encode and decode binary string)
So basically, Codeforces just said, “your code has short-term memory loss, deal with it.” Time to teach my program how to leave notes for its future self. :)
As a Participant, I am really excited for this contest.
Or we could just say we're testers.
Yeaaah,,, That’s true.
1392E - Omkar and Duck
Here is a nice run twice type problem
This was my first time doing communication problems and I hecking love these tasks but I'm an ICPC participant now 😭😭
ICPC (sub-)Regionals are starting to also have these kind of problems.
I am a bit disapointed, because I allways get "Idleness limit exceeded on test 1" :/ No idea what is wrong.
This problem seems more like encryption and decryption kind of think..
This type of problem doesn’t have a corresponding error type, so you have no idea what went wrong.
This communication format is really awesome. Great to see CF trying out new stuff!
Someone please explain the approach for Problem C? Please give some hints.
There's a problem D??
There is no problem D. If you mean problem C, google Hamming code.
yes, problem C
Wow that is brilliant, thanks for mentioning it.
Here's my approach.
(First Phase) Use $$$1$$$ to $$$15$$$ bits to express $$$x$$$ (its binary expression) , then calculate the xor for these used bits. This will give you a number which is less than $$$16$$$ . So then save this number use $$$16$$$ to $$$19$$$ bits. Then finally, add $$$20$$$ when there is odd number of bits from $$$16$$$ to $$$19$$$ .
(Second Phase) So, when change is at $$$16$$$ to $$$20$$$ , you can find it by calculate bits count of them. (Its parity will tell you whether it is changed or not) If it is changed, it tells us bits from $$$1$$$ to $$$15$$$ is right, then just calculate $$$x$$$ back. If it is not, calculate the xor for former $$$15$$$ bits using the same strategy and the value expressed by bits $$$16$$$ to $$$19$$$ . If the result is not $$$0$$$ , it will tell you the bit that is changed. Filp it and you will get the answer. If it is $$$0$$$ , then the set is unchanged(And of course you will know the answer then).
Summing up the above，you are able to find the answer $$$x$$$ .
Does this approach have a name? It is quite similar to Hamming code and almost as efficient as it (requires at most 1 more bit than Hamming codes).
Well, I don’t know if it has a name or not because I think it up myself:) Actually, I would like to think that I was inspired by Hamming codes and the goals are similar.
Not sure if this has been mentioned before, but it would be nice to maybe introduce the communication problem tag!
I think the problems were very easy. But considering it was for testing purpose, its fine. But loved the theme anyways.
Kept on getting WA on test 9
Check the constraints for the length of s
Brdr I also get wrong answer then I read output format it shows string length. So, I get that you should focus on encoding to make sure your encoding should not produce larger string.
I enjoyed those new types of questions, codeforces should really add these in regular contests
Loved this Round, and the new concept ggs!!
How to solve B and how to use x?
Without using x you can easily find [l, r] such that a[l] and a[r] are 1 and n or vice versa using binary search. You can use x to tell if l is 1 or n by setting x to 1 if the position of 1 is lesser than n in the original array
Really enjoyed the problems a lot. This is really interesting task type.
Why do you need to shuffle tests in B? And if this becomes a common practice in problemsetting, can you please not say the number of shuffled test in verdict?
I had wa1 in B with this message: "Second run message: wrong answer Guessed 2, Expected 1 (test case 2)". The tests look like this
first 3 3 3 2 1 5 1 2 3 4 5 5 4 2 3 5 1
But the answer to the second test is 5, not 1 nor 2. Turns out second case in the second run was [3, 2, 1] which is the first test in preview.
Tests are shuffled in order to prevent sending information about what test case it is in the first run. But yes, we will ensure that this issue will not happen in communication problems in actual rounds.
In order to prevent sending information wholly using multi-cases, you can also secretly split tests in the first phase into two or more parts and run them separately. For time limit, just sum them up(or maybe a max in case there’s initializations). I believe that adopt this strategy or mix them(I mean, both shuffle and split) together will block this method better.
Can we see how to set the tasks of TR20 with Polygon, as a sample?
https://mirror.codeforces.com/blog/entry/142052
I think it's time to add this line into our template:
while (t--) { #ifdef MULTI_RUN string s; cin >> s; if(s.compare("first") == 0) solve(); else solve2(); #endif }That fails for the problem B where the no. of test cases $$$t$$$ comes after the phase "first" or "second". The phase string will always come before the test case count because only one particular phase is expected per execution.
Also,
if (s == "first"sv)works fine, or you can also just compare the length of the string but that would lose clarity.nice i am excited
i am excited
That seems brilliant and will introduce many new ideas and problems!
I just have a question for Proof_by_QED of any of who started this brilliant initiative: why limit to one-round communication? Is it possible that the problems will have multiple rounds as well? (May be $$$k \leqslant 20$$$ determined by the judge at the beginning of the problem)
Communication is a standard idea in Algorithms and Complexity Theory, so I'm excited for what this has to offer (for example, C in the testing round introduced the idea of error-correcting codes!)
multirun is not supported by the cf infrastructure as far as we know
Do you think it can be in the near future?
idk maybe if mike stops playing genshin impact /hj
Cool ideas Can anyone give some brief on the creative side of problems that could unlock or kind of a why such class of problems exist in general?
For A2,You can simply encode each digit to corresponding character, so at max 10 digits+ a separation character(to understand that was a number ending there), exactly fitting in the length(10^4*10), except for 10**9 you need to encode a separate character(otherwise wa on 9).
People working in different computational fields of computer science should try involving real-world applications in competitive programming on codeforce. It helps you grow in all directions, and such problems are really fun!
one more annoying type of problems! 2 times bigger code... O_o
Ok, so to be honest, at first I was very hesitant about communication problems and failed to see why they would be interesting at all, in fact both a and b were extremely easy and overall boring, quick to figure out, and nothing interesting. However, I admit C was cool, maybe one of my favourite problems of recent times
It was pretty easy to figure out
that we need 3 sections to check each other, to guarantee no ambiguity of correct solutions when messing with the string
The
XOR idea was really beautiful, where you XOR the section and since it would be sectionXor^something in the section to break/fix the string, we can see that there are no ambiguous solutions as as long as a!=b sectionXor^a!=sectionXor^b, this was a very neat observation and it did take me some time too (~45m?)
However then I got stuck as
I wanted to do it twice, and I thought this would work for some reason because i thought 2^15-1 could be stored in 14 bits
so my solution would do first 15 bits, first xor compression, then i would xor compress 0,1,2,3 for 16 to 19, and 20/21 would hold that binary representation of the second xor compression. I was stuck on this for a while thinking how to make it better.
In the end the idea of using another invariant came to mind, and removing or adding in any case would swap the parity of those, so the 20th bit would be used to check parity, with this I got ac.
(btw for retrieval you just do brute force) as with 3 sections only one configuration will have all 3 agree with each other, we can just do 10^4*400 which is fine, first (and only time) the sections agree, we take the first 15 bits to calculate answer as in this case they are all correct
Overall, very nice problem, and completely changed how I view communication problems, I think these are a welcome change to CF as long as they require creative never-before-seen (in cf) ideas
However, I still think B is a useless problem and I question why it exists? Its trivial and does not require any neat tricks in the first place.
These are testing problems. C is basically hamming codes, so also nothing new. There are great communication problems
Will there be communication problems in future rounds?
Yes, there will. I think this will add some more fun problems and a little bit of spice to the round.
The new Communication Problems are one of my favorite type of problems. I can suggest you to look to the Ejoi 2020 day 2 Problem B Card Trick, if you want to solve more Communication Problems. https://eolymp.com/en/compete/c008c563-2b60-42ca-a5cf-1881ed4e2195/problem/2
Here is my solution.
hi
In C can there be multiple second runs? (I see that it runs exactly twice but can this be implemented?)
For example for each first run there are 21 second runs, one for each possible change. Or maybe just put everything in one run with 21x more testcases, but if there are no multiple testcases then that doesn't work.
I also wanted to ask this because I was wondering whether tasks like APIO 2022 Mars can be implemented (where the second runner is called multiple times or at least in absence of previous memory)
wait apparently it was already addressed in previous threads lol
Try CF Submitter : https://marketplace.visualstudio.com/items?itemName=DevXSayan.cf-submitter - Fetch all the problems of a contest inside vscode, run test cases, and submit in one click, all without leaving vscode
So it is interactive but not interactive also
Wow, this idea is really interesting. Now I’m thinking about a type of problem that involves executing the code K times (possibly more than twice). For instance, manually running a CNN. It might take a week for a submission to be judged. :)
I didn't really understand anything, but I'll pretend like I did... By the way, how do we solve communication problems? I mean, we are programmers...
Can someone explain what is the difference between just these types of problems and the previous already existing problem. We know that if the run is first then execute solve1 else execute solve2.
The behavior of
solve2heavily depends on the behavior ofsolve1, it is not like you are solving two completely independent problems.One example, a task that requires you to prove that there is a bijection between two sets by constructing one can't be easily evaluated without this format.
Check the problems in this contest: https://contest.ucup.ac/contest/1465
Hello, respected Codeforces coordinators. I received a plagiarism warning for submission 346344726 . I assure you that I did not share my code with anyone or copy from others intentionally. I might have used a similar approach or template that could have caused this similarity. If needed, I can provide my code history, local editor files, or screenshots showing my development process. I kindly request a recheck or reconsideration of this case. Thank you for your understanding and for maintaining fairness on the platform.[user:c231080_masrur][submission:346344726] ~~~~~ Your code here... ~~~~~
include <bits/stdc++.h>
using namespace std; using ll = long long;
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; if (!(cin >> T)) return 0; while (T--) { int n; ll k; cin >> n >> k; vector<vector> adj(n+1); for (int i = 0; i < n-1; ++i) { int u,v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } vector parent(n+1, 0), order; order.reserve(n); parent[1] = 0; order.push_back(1); for (size_t i = 0; i < order.size(); ++i) { int u = order[i]; for (int v : adj[u]) if (v != parent[u]) { parent[v] = u; order.push_back(v); } } vector sz(n+1, 0); for (int i = n-1; i >= 0; --i) { int u = order[i]; sz[u] = 1; for (int v : adj[u]) if (v != parent[u]) sz[u] += sz[v]; } ll total = 0; for (int v = 1; v <= n; ++v) { ll cnt = 0; if (n >= k) cnt += 1; for (int u : adj[v]) { ll s_u; if (u == parent[v]) s_u = n — sz[v]; else s_u = sz[u]; if ((ll)n — s_u >= k) cnt += s_u; } total += cnt; } cout << total << '\n'; } return 0; }
I think that communication problems have good potential and I am looking forward to seeing them in future contests.
As others have mentioned it is now time to update code templates to handle them. I have also written some shell command lines that allow easier testing.
For problem A I have used:
Where
example.inis the input of the first execution. Anda.outis the compiled binary.For problem C we need to pass the number of test cases to the second program. The command now looks as follows:
It doesn't do communication mangling which was in C, and interactive problems still require special handling. However, I believe this should at least be helpful for most of such programs.
Feel free to use it and share your commands if you came up with something better.
tung tugnb tung saHUR
It seems that will have more great problem
orz
okay