You can use xor convolution to check each colour, so the time complexity is $$$c n \log n $$$, where $$$c = 4$$$ is the number of colours.

A naive checking in n * number of primes would be $$$4 * 10^9$$$ roughly (2e4 primes less than 2e5), it is possible that this is fast enough as is.

Because I know that I mixed up the code, submitting it again would lead to skipped, so I naively thought it could be done this way.

Do you mind explaining why did you put 11 unwanted for loops in this Submission

I'm sorry for logging into a computer with an incorrect account, which led to both submissions being skipped. However, these two codes were indeed submitted by the same person, and there was no intention to use someone else's code. I hope to be forgiven for this mistake![user:GoymyGo]

Clearly I made no attempts to hide that, when I link my submissions from main. Though, I think it is the right time to make a quick comment why I choose to use alt even well aware of the single account policy.

It is a combination of a few things:

Firstly, codeforces have nonzero incentive for staying at >=3000 rating that is LGM. You can say that no one cares about ranks and colours but it is there, and I do care, and I believe many do. In fact I care about it a lot. Everything that follows will seem nonsense if you don’t believe 3000 is something meaningful, so please bear with me

(It is the only final goal of CP, if you don’t count dethroning tourist etc.)

After my second ICPC world finals, I decided that I have to focus on my studies. If my studies do not work out, I basically have to quit CP for a decently long time, even if not, I cannot train for CP seriously competitively for two years or so.

My current rating in this retirement state is somewhere between 2900 and 3100, I don’t know because I did not play enough rounds. A safe bet would be 2950 now.

At my prime, this would be closer to 3100, so there is less risk of losing LGM — and if I lose it I do deserve it, by either a very bad round or just not actually maintaining a good skill above 3000. I am fine with losing it if I am currently seriously looking for improvements in CP, that just means an impactful lesson (I did lost it a few times across the 3 accounts). However, I don’t want to lose it just because I cannot spend time to maintain the same level of “not rusty”, especially when I have proven I can hold it with ease when not in rust.

Therefore the idea is simple: I just play on bruhopen when I am in “retirement state” and on this account when I am serious and aiming for improvements and even higher ranks. I just keep the two records separate, which they really should be. I wouldn’t hesitate to play on an “unrated” option if there is one, which is supposingly being implemented but it is not happening yet.

This is the current reason why I chose to play on bruhopen. This was very different from the reasons I play on FastFreeTask in the past, those reasons do actually seriously violate the spirit of the blog so I stopped doing that.

I think the harm done to the community by this action is within manageable magnitude, for the following reasons:

I am actually not top 50:if I were comfortably top 50, I would be far away from the 3000 line that I don’t have to worry about it. There shouldn’t be much impact on the rating list you see on the right.

I only talk and play on unrated round on my main account( this one). The above is an unfortunate exception because I need to signify it was this account that I had an in-contest submissson. I am not trying to hide the fact that I have multiple accounts, it is just not actually useful information for anyone so there is no reason to bring it up.

In terms of rating dist(arvindf232,bruhopen) is actually very likely within 100. It is simply unfortunate that this difference cross the 3000 barrier that makes it an issue for myself.

(Plus the usernames are cool ok? My main name have to stay serious but I definitely want to use other names)

Therefore I will stop using alts altogether when i can be 3200 at my prime = not losing LGM even when rusty = firmly step into top 50, but that day will have to wait because I don’t have time to train on CP.

Finally I didn’t actually care about rating, rating on this account is inconsequential (cool if it hits 3000 though), and unrating it is just a consolation (recalculate submission time for E and remove 30 minutes of penalty for F and G, I am already at +50 delta, not counting the impact of momentum and losing opportunity to do H). It is just that rightful requests should be made.

Sorry for the coincides but i don't know about that I don't no zhe ID is others but i have not copy any code of the problem 1991C and 1991B this is just a coincidence i don't violate any rule of the contest and the codeforces so pls give my rating back and consider my solution for the contest.

Sorry for the coincides but i don't know about that the same code exists or already submitted but i have not copy any code of the problem 1991C this is just a coincidence i don't violate any rule of the contest and the codeforces so pls give my rating back and consider my solution for the contest.

asking me??

How did you make D's checker?

273306239 this submission i have made but was giving constant tle but as soon as i converted it in c++ was giving an accepted solution(but how is this possible)...this is the converted code --->273310051

When will roll back happen?

https://mirror.codeforces.com/blog/entry/124418

arvindf232 = bruhopen (= FastFreeTask)

I see, you certainly have the right to be unrated.

Your code can't handle the case when there is only one vertice. Try this:

glaze of doom

Good luck to you!

ZhouShang2003 I am having the same issue in problem E.

TLE during contest (50+ of them) AC after contest, codes identical.

TLE code in contest: 273157246, AC code resubmission 273253391. Please check that the code are identical.

Please look into the situation,

Far more importantly, please clarify what made the differences and so I can avoid running into it again: If the interactors or test case 1 had been changed between the contest and after systest.

Plus please consider un-rating the affected people. I lost at least 30 minutes and all my momentum and mood, (in fact I think I would have gotten at least a moderate positive delta without this).

Can anyone help me find out why my 273201975 on 1991E - Coloring Game received a WA verdict, Checker comment is "wrong answer Integer 3 violates the range [1, 1] (test case 19)" :)

Can you please explain why?

construct, construct, construct...

A<D<B<C<E<F. Thus averaging out to intending difficulty.

This round wins the "Cutest prizes" title

ofc no. The best are Tractor rounds

nice contest

0 0 5e8 ... 5e8 1e9 1e9

This test will make you loop indefinitely.

Taking 1st and 2nd max element each time and doing operations each time with the average of both, will it work in 40 operations? Or will it work ever irrespective of number of operations?

E was amazing!

I updated my soln. can you check again plz ? this soln handle of case n=1 ig

thanks btw

upd: got it. thanks

Refer to my root comment, that was how I envisioned the problem. Absolute values on differences feel like a mirror and/or interrupting borderline to me, so that idea just comes naturally (also perhaps given the fact I used to learn basic linear regressions before, so the imagery was engraved).

Can you tell me how we can think like this during contest.

I simply guessed subtract sum(arr)/size(arr) as it was giving correct output for given samples and also, for most of the testcases this guess was correct but got WA on testcase 2

try this case:

can u check my code plz ? i also cried tho its regular event xD

nb: I commented my soln below 2/3 comments

idk, when I was crying after the contest, it suddenly became AC somewhen

if you feel so, then problem D makes me Idiot of the century.

I went to color the graph greedily, and messed up.

To get constructive, I built a graph for n = 20,

n = 20;
repl(i,1,n) {
	repl(j,i+1,n) {
		if(isPrime(i^j)) {
			g[i].PB(j);
			g[j].PB(i);
		}
	}
}
repl(i,1,n) {
	cout << " node number " << i << " is connected to " ;
	for(auto j : g[i]) {
		cout << j << " " ;
	}
	NL 
}
NL NL

 

Then I started colouring the graph greedily.

1. What I mean is, I gave color-1 to node 1.
2. Then I went to node-2, and checked. I can't give color-1 to node-2, because, node-1 and node-2 are connected.

3. Then I went to node 3, and node-3 is connected to node-1 ( we are checking colors from node 1 to node (i-1)). So, I assigned node-3, also color-2.

And this is where I went wrong :( . I was getting answer 36, for n=2054. and was trying to find pattern here :( .

Honestly, kind of demotivating D problem.

I know that any planar graph is 4 colorable, but this is no planar graph :( .

when does it get ac ?

no i think you will only get penalty if any of your solution gets accepted after some wrong submissions

nvm figured it out.

Any clue on why taking average of all the unique elements does not work at each iteration for subtracting doesn't work?

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

const ll N= 1e5+5;
ll val[N];
bool vis[N], chk;
vector<ll> even,odd;
vector<ll> adj[N];

void dfs(ll u){
   vis[u]= 1;
   if(val[u]==0) even.pb(u);
   else odd.pb(u);
   for(ll v: adj[u]){
      if(vis[v]){
         if(val[u]==val[v]) chk=0;
         continue;
      }
      if(val[u]==0) val[v]= 1;
      else val[v]= 0;
      dfs(v);
   }
}

int main(){
   FastIO;

   ll T=1; cin>>T;
   while(T--){
      ll n,m; cin>>n>>m;
      for(ll i=1;i<=n;i++){
         adj[i].clear();
         val[i]= 0;
         vis[i]= 0;
      }
      odd.clear(); even.clear();

      for(ll i=0;i<m;i++){
         ll x,y; cin>>x>>y;
         adj[x].pb(y);
         adj[y].pb(x);
      }
      // val[1]= 0;
      chk=1;
      // dfs(1);
      for(ll i=1;i<=n;i++){
         if(!vis[i]){
            val[i]= 0;
            dfs(i);
         }
      }

      // for(auto it: odd) cout<<it<<' '; cout<<endl;
      // for(auto it: even) cout<<it<<' '; cout<<endl;

      if(chk==0){
         cout<<"Alice"<<endl;
         for(ll i=0;i<n;i++){
            cout<<1<<' '<<2<<endl;
            ll x,y; cin>>x>>y;
         }
      }
      else{
         cout<<"Bob"<<endl;
         ll oddl= odd.size(), evenl= even.size();
         ll oo=0,ee=0;
         bool ooo=0,eee=0;
         for(ll i=0;i<n;i++){
            ll x,y; cin>>x>>y;

            if((x==1 || y==1) && oo<oddl){
               cout<<odd[oo]<<' '<<1<<endl;
               oo++;
               if(oo==oddl) ooo=1;
            }
            else if((x==2 || y==2) && ee<evenl){
               cout<<even[ee]<<' '<<2<<endl;
               ee++;
               if(ee==evenl) eee=1;
            }
            else if((x==3 || y==3) && ee<evenl){
               cout<<even[ee]<<' '<<3<<endl;
               ee++;
               if(ee==evenl) eee=1;
            }
            if((x==3 || y==3) && oo<oddl){
               cout<<odd[oo]<<' '<<3<<endl;
               oo++;
               if(oo==oddl) ooo=1;
            }
            // else if(ooo){
            //    cout<<even[ee]<<' '<<3<<endl;
            //    ee++;
            // }
            // else if(eee){
            //    cout<<odd[oo]<<' '<<3<<endl;
            //    oo++;
            // }
         }
      }

   }
   return 0;
}
/*

*/
/*

*/

why it is wrong ?

idea: odd cycle: alice else
even level fill by 0 and odd level fill by 1. if any level full others level fill by 3.

Same here :/

I just spent 45 minutes crying and finding for a bug in vain, feeling completely meaningless

Same for me

if you submit a wrong solution for a task and you never submit a correct one, will you still get the penalty?

Is upsolving restricted now??

Human intelligence round

We can quickly halven until the maximum height difference being at most $$$1$$$ (never going to take more than $$$40$$$ times). If it is $$$1$$$, it won't converge (drawing a line between two consecutive height is invalid as we're only allowed integers). Otherwise, it will.

is there some bugs in judging system of prob E? Somehow my E become AC after the contest ?

ZhouShang2003 Is there any issue with problem E? I was getting WA in pretest1 but now it is accepted?

In this case: 1 1 0 Your code would output 1 0 but the correct answer is 0.

As wouldn't $$$k = n = m$$$

Oh wow, that's actually a really cool solution. I completely missed the importance of 2 being the only even prime even though I analyzed cycles for edges of 2 and 3...

How do you know that if it is going to converge to 0 ?

A sample test with $$$\min(n,m)=k<\max(n,m)$$$ wouldn't hurt in G. Very silly bug.

Thanks for speedforces and cool problem G, enjoyed the round!

In the last step you will have all elements equal in the array.

So , we need to make atleast two different elements equal at each step (and complete within 40 steps). So we select two distinct elements , decrease the whole array with their average. Since we take absolute values both chosen elements will become equal by this operation.

In this way in 40 steps we can make all elements =0 , if possible.

However all elements must be of same parity initialy in the array. (Think about it yourself).

humorous problem D

Think of a set of points with different height, and you are trying to draw a line in between them. If you drew perfectly and mirror the points below that line (which is literally this problem), you'll see that the maximum height difference between any two points will be halved.

Damn thanks. I did not look at it that way. It was a tricky one.

Intuition is that you keep halving the biggest number — because smallest cannot become than x -, meaning that eventually everything will become 0 (as long as parity is equal and you choose ceil(max/2)). It will also take log2(initial max) steps.

can some one tell the reason for problem C approach or what is your thinking process

interesting constructives early on.

I think the idea is just a somewhat intuitive approach that keeps popping up for this kind of problem. For example, this problem is an even earlier problem I set that uses the same key idea.

At the time I came up with it, I hadn't seen any problem use this approach before, but since then I've seen multiple other problems use the exact same idea of "3-colour bipartite colouring with restrictions on when / how many times you can use a given colour".

I have no casework in my solution. I actually had two WA2 from trying casework on K = N

I really hate problem of D kind

guess until get it right

I did the same :(

Thanks for the round! Maybe the best round in this year!

Where is $$$998244353$$$? X(

The fact that both H and I are solvable surprised me a lot. Strange feeling. Thanks for the preparing the round!

can't agree more

This Round is the worst round i have ever seen

then you could just pick all the first numbers into S1 and all the 2nd numbers into S2

G is a great challenge to the player's guessing ability. But I don't like it. ()(())

Feeling quite retarded , not able to get old form back. That's the thing with CP... if we stop practising. Performing in contest is a different skill. Anyways CP is best.

Poor experience

the answer is very small

I just hope that someone can tell us why and not just like most of the time where it's just a pure guessing

Yeah, but the hardest case is if the interactor only plays the same 2 numbers, if it plays the third, even easier. I colored it in the same way you check a graph for bipartiteness. I can't think of a counterexample

what was C? and why am i getting WA in this

doesnt change anything

1 3 is lexicographically larger than 1 2

It doesn't work the best is actually x = max(array) / 2

What is the difference lmao

Thank you for the round!

D makes me feel stupid. It's so simple but somehow I used 1h.

GuessTrickForces :(

A<B<C<E<F<D ???

ConstructiveForces

n=1 on E was hell to debug for 2 hours, this is the worst i've tilted since this round lmao

Nodes $$$u$$$ and $$$v$$$ if sharing the same parity will have an edge only when $$$u \oplus v = 2$$$. The remaining edges are always from one parity to another, i.e. virtually bipartite graphs. For large enough $$$n$$$, each parity will need $$$2$$$ colors, and thus maximum colors should only be $$$4$$$. $$$n = 6$$$ already reaches $$$4$$$ as most optimal ones, therefore all $$$n > 6$$$ should do the same.

let S1 be the nodes that you will color 1, S2 be the nodes that you color 2

what would you do once you color all nodes in S1 (or S2)

if you just fill S1 with 1 or 3 then S2 would be a really chaotic mess of 2s and 3s that might fail (and vice versa)

to be more specific, once you color all the nodes of S1 then alice could just keep sending "1 3" and if S1 contains any nodes that's colored 3 then that's WA

you should've spammed "1 3" I think

Problem E is a repeated problem Original Problem

The solution is very simple and stupid. I also wandered in incorrect direction for some time.

1 2 3 4 1 2 3 4 1 2 ...

$$$a \oplus (a + 4k) = \dots 00$$$ which is divisible by $$$4$$$ and hence not prime.

D is one of those problems (that I hate) where the solution is really simple but 99% of coders are unable to prove the greedy algorithm. For $$$n\leq6$$$ we copy the sample solutions. For $$$n\geq7$$$, we take the periodic sequence $$$1, 2, 3, 4, 1, 2, 3, 4, \dots$$$.

PS can someone share the solution for E?

D > E, F in my opinion, the starting point for E (non-bipartite are definitely winnable for Alice) / F (answer is always yes for arrays with $$$\gt 63$$$ elements for $$$a_i \leq 10^9$$$) is fairly obvious to me.

But I just spent ~30 mins working out cases and trying random stuff on D with no luck.

feels like your pfp

The only odd cycles in the graph must include pairs $$$(n, n + 2)$$$ where $$$n \oplus (n + 2) = 2$$$. So, removing just these edges, the graph is bipartite with the two sides being the parities. Then, we can 2-color each parity since the only edges between vertices of same parity are those of the first kind. This gives a 4 coloring for all $$$n\ge 6$$$.

If you don't mind, can you please share?

my solution was:

observe that odd verticies will only connect with even verticies

with the exception of u^v = 2 -> just alternate between a and a+2

tho there's the edge case of n = 3

so turns out the output still ends up as 1 2 3 4 1 2 3 4 1 2 3 4 ...

Yes. I actually came up with a proof (sorta) before doing that.

hey Tourist why you so smart,

the way you solve problem is just pure art.

How are you so fast

You come first, I come last.