Team based round... interesting, will participate.

Users rated >= 2100 can't seem to register for the round?

I like when contests are at this time. (5:35 AM, Saturday for me) It forces me to not sleep in and be a lazy bum

hopeforces

Will the problems be a different style than regular rounds?

i see olympiad i upvote (unless its russian, then i just comment)

CF 791 -> ABC 251 -> Code Jam Round 2

No clashes with 20-25 mins break each. Sweet. Thanks for the unusual time :)

Is it only me, or does everyone feel that contest at an unusual time has less participation than the usual time contest? Hence have less probability for the rating to increase. I know we should not give contest for rating, but still...

This round will be hard. Good luck everybody!!!

How to know if a contest is unrated for me, I am new to the cf and could not find any official post on this info yet ?

The unusual time strikes back.

Why so unusual time? anyone any idea

Please add the contest link in the blog.

If the score is more than 2100, why do people with a score of more than 2100 participate in the ranking

"i_am_completely_useless for being completely useless." -- Sakura :))xD

Thank you for the unusual time!

excited for this contest, go go go !

Unfortunately, I need classes at that time, so I can't participate in this contest.

QueryForces

Pretests in C must be extremely weak

waiting for contest finish to get solution for problem E

Why Segment tree solution is giving TLE in C. :(

#include <bits/stdc++.h>
using namespace std;
 
 long long int st1[2000005];
 long long int arr1[100005];
 long long int st2[2000005];
 long long int arr2[100005];
 
void build1( long long int node,  long long int start,  long long int end)
{
      if(start == end)
      {
            st1[node] = arr1[start];
            return;
      }
       long long int mid = start + ((end-start)/2);
      build1(2*node+1, start, mid);
      build1(2*node+2, mid+1, end);
      st1[node] = st1[2*node+1] + st1[2*node+2];
}
 
void update1( long long int node,  long long int start,  long long int end,  long long int k,  long long int u)
{
      if(start == end)
      {
            st1[node] = u;
            arr1[k] = u;
            return;
      }
       long long int mid = start + ((end-start)/2);
      if(start <= k && k <= mid)
      {
            update1(2*node+1, start, mid, k, u);
      }
      else update1(2*node+2, mid+1, end, k, u);
      st1[node] = st1[2*node+1] + st1[2*node+2];
}
 
 long long int query1( long long int node,  long long int start,  long long int end,  long long int l,  long long int r)
{
      if(start >= l && r >= end) return st1[node];
      else if((r < start) || (l > end)) return 0;
      else
      {
             long long int mid = start + ((end-start)/2);
             long long int p1 = query1(2*node+1, start, mid, l, r);
             long long int p2 = query1(2*node+2, mid+1, end, l, r);
 
            return (p1+p2);
      }
}
 
 
void build2( long long int node,  long long int start,  long long int end)
{
      if(start == end)
      {
            st2[node] = arr2[start];
            return;
      }
       long long int mid = start + ((end-start)/2);
      build2(2*node+1, start, mid);
      build2(2*node+2, mid+1, end);
      st2[node] = st2[2*node+1] + st2[2*node+2];
}
 
void update2( long long int node,  long long int start,  long long int end,  long long int k,  long long int u)
{
      if(start == end)
      {
            st2[node] = u;
            arr2[k] = u;
            return;
      }
       long long int mid = start + ((end-start)/2);
      if(start <= k && k <= mid)
      {
            update2(2*node+1, start, mid, k, u);
      }
      else update2(2*node+2, mid+1, end, k, u);
      st2[node] = st2[2*node+1] + st2[2*node+2];
}
 
 long long int query2( long long int node,  long long int start,  long long int end,  long long int l,  long long int r)
{
      if(start >= l && r >= end) return st2[node];
      else if((r < start) || (l > end)) return 0;
      else
      {
             long long int mid = start + ((end-start)/2);
             long long int p1 = query2(2*node+1, start, mid, l, r);
             long long int p2 = query2(2*node+2, mid+1, end, l, r);
 
            return (p1+p2);
      }
}
 
 
int main()
{
 
	#ifndef ONLINE_JUDGE
 
	    freopen("input.txt", "r", stdin);
	    freopen("output.txt", "w", stdout);
 
	#endif
 
	// think twice
	
	long long int n, q;
	cin >> n >> q;
	build1(1, 1, n);
	build2(1, 1, n);
	// for(long long int i = 1; i <= n; i++)
	// {
	// 	arr1[i] = 0;
	// 	arr2[i] = 0;
	// }
	while(q--)
	{
		long long int t; cin >> t;
		if(t == 1)
		{
			long long int x, y; cin >> x >> y;
			update1(1, 1, n, x, 1);
			update2(1, 1, n, y, 1);
		}
		else if(t == 2)
		{
			long long int x, y; cin >> x >> y;
			update1(1, 1, n, x, 0);
			update2(1, 1, n, y, 0);
		}
		else
		{
			long long int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
			if((x2-x1+1) == query1(1, 1, n, x1, x2) || (y2-y1+1) == query2(1, 1, n, y1, y2)) printf("Yes\n");
			else printf("No\n");
		}
	}
 
 
	return 0;
}

Used a single loop in Problem-B, still exceeded the time limit, is it me or python at fault here?

Thanks to iura for setting F! I really enjoyed solving it during testing. Here is my alternate solution to F that works for much larger constraints.

Let $$$S_i$$$ be sets containing all representatives of all arrays $$$a$$$ of size $$$i$$$ and $$$C_i$$$ be the set of cliques of size $$$i$$$. When we talk about clique, we are talking about cliques on the graph where we draw the edges as $$$(u_i,v_i)$$$. Also when we talk about arrays, we will basically refer to its equivalence class, so treat $$$a$$$ as the representative.

Take some array $$$a$$$ and let $$$s_a$$$ be the possible values of the first element of $$$a$$$ after some operations. Note that it is necessary that $$$s_a$$$ is a clique because otherwise, we are not able to swap all values in $$$s_a$$$ to the start of $$$a$$$.

Let us suppose that we know $$$S_j$$$ for all $$$j \lt i$$$ and now we want to find $$$S_i$$$. For all arrays $$$a \in S_{i-x}$$$ and $$$c \in C_{x}$$$,put $$$(c,a)$$$ into $$$T_{x}$$$. That is, we want to think about arrays $$$a \in S_i$$$ as the concatenation of some clique and another array. Unimportant remark: $$$c \subseteq s_{c+a}$$$.

However, the problem with this is that are multiple ways to make a certain array. As a simplest example, consider when we can swap $$$(1,2)$$$ only. To make array $$$[1,2,3]$$$, we can split it into $$$([1,2],[3])$$$, $$$([1],[2,3])$$$ and $$$([2],[1,3])$$$. Of course, we do not want to double count.

Let us consider some $$$a' \in S_i$$$ where $$$k=|s_a|$$$. There are $$$2^k-1$$$ combinations of $$$c+a$$$ that produces $$$a'$$$. Every subset $$$c$$$ of $$$s_a$$$ corresponds to a $$$(c,a)$$$ tuple, and there are obviously $$$\binom{k}{x}$$$ such subsets with $$$|c|=x$$$, so $$$\binom{k}{x}$$$ tuples in $$$T_x$$$ corresponds to array $$$a'$$$.

One can see that $$$|S_i|=|T_1|-|T_2|+|T_3|-\ldots$$$ by looking at the individual term of some $$$a' \in S$$$ and noticing when only considering tuples that correspond to $$$a'$$$, we have $$$\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \ldots =1$$$ on the right hand side. Note that by definition, $$$|T_x|=|S_{i-x}| \cdot |C_x|$$$.

Let the number of digits be $$$d$$$. If we let $$$ans_i$$$ be the answer for length $$$i$$$, we have the explicit recurrence $$$ans_i=\begin{cases} 0,& \text{if } i \lt 0 \\ 1, & \text{if } i=0 \\ \sum\limits_{j=1}^d ans_{i-j} (-1)^{j-1}|C_ j| & \text{if } i \gt 0\end{cases}$$$.

We can find all $$$|C_j|$$$ in $$$O(2^d)$$$ by brute force. To do this, we check if some mask $$$bm$$$ is a clique in $$$O(1)$$$ by taking an arbitrary bit $$$b$$$ from $$$bm$$$, checking if $$$bm \oplus b$$$ is a clique and that $$$b$$$ is connected to everything in $$$bm \oplus b$$$. Since we can solve linear recurrence in $$$O(d \log d \log n)$$$, we have total complexity of $$$O(2^d+d \log d \log n)$$$ but it probably does not matter what algorithm we use to solve the linear recurrence since there is no way it is going to dwarf the $$$2^d$$$ term.

Can we find all terms of $$$|C_j|$$$ faster than $$$O(2^d)$$$?

Code: 157227780

segment tree forces

n = 2 should have been in the samples in A :(
Btw, I wonder how many people solved B using segment tree

I tried to hack C with 2e5 queries and it said input cannot exceed 256kB, what T_T

how to solve c ? some one pls tell me your approach :* (i've tried to do it with brute force by making maps in the last 10 min I was knowing that it gonna get me tle :D ) so how can we solve it:*