Obviously many experienced users made new accounts just to increase their ratings and Mike asked people not to do this but they won't listen. This is pretty bad and unintended.

I think there should be some limit on the max increase possible for this round. Otherwise, it is very unfair for participants with rating >= 1400.

extension not working

Just wanna know, how accurate this CF PREDICTOR have been in the past ??

But even if someone with a low rating became Expert after this round, their rating will fall again drastically after a div 2 round due to the number of problems they will solve. So it doesn't make that much of a difference I guess!

The number of integers not divisible by $$$n$$$ among numbers $$$1, 2, \dots, x$$$ is $$$x - \lfloor\frac{x}{n}\rfloor$$$, so you can do binary search to find suitable value of $$$x$$$ (such smallest $$$x$$$ that $$$x - \lfloor\frac{x}{n}\rfloor < k$$$).

You may see my binary search implemented solution. 79500682

Hi, I have solved the ques in O(1) time without binary search. You can see here 79680203

This can be explained more easily if you understand that before each multiplier of $$$n$$$ there are $$$n-1$$$ integers not divisible by $$$n$$$, so we need to "skip" some number of such blocks. $$$\lfloor\frac{k}{n-1}\rfloor$$$ doesn't match because when $$$k$$$ is divisible by $$$n-1$$$ then we don't need to count the last block.

It's even worse than that, because there can be $$$c_0+c_1+c_2$$$ digits in each dp state, so you get something like $$$O(T \cdot (c_0+c_1+c_2) \cdot c_0c_1c_2) \approx 3 \cdot 10^{11}$$$, which will very clearly not pass.

You dont need to use it and it will most probably give MLE . Segment trees take huge amount of space and building and quering them would take additional logn time which would prove to be costly .

Checking all possible paths would lead to an exponential solution I think.

There can be cycles too [2->4->6->2] (>_<).

Maybe as someone mentioned above, don't cut lemons with swords.

removed

essentially, odd numbers can only be made with odd numbers, and an odd amount of numbers at that.

even numbers can be made with any amount of even numbers and an even amount of odd numbers.

then you set all the numbers to 1 or 2 (depending on if you want the array to be even or odd based on those rules) and then the last number is the amount that ur left with after subtracting all of the 1s and 2s

The vertex set can be represented as the set of all numbers from 1 to n. The adjacent numbers for a node 'x' would be {x-4,x-3,x-2,x+2,x+3,x+4} provided they are in between 1 and n inclusive. Now you can perform DFS. The answer would be the DFS which satisfies the given condition in the problem. (NOTE: Edited: It will not be the DFS which visits all vertices...since the graph formed is connected, each DFS will visit all vertices) Even if you do a DFS from each number, the complexity would be O(n^2) (this include the time for checking the validity of the current DFS), which I guess would pass the problem constraints.

Check it out! 79806425

O(n^2) is the time complexity and O(n) is space complexity. In this question space is unusually restricted so space complexity should not exceed O(n) but time complexity of O(n^2) works just fine

I played with small permutations, trying to find a working block small enough so I could replicate it, and built the big N-elements answer. For me, it turned out to be a block of the first 4 numbers:

2 4 1 3

For N = 4 this is good. So as I said, I tried to make it work like a "brick" to build the answer, making chains of this block. So, if you have N = 8, you can "link" two of these structures:

2 4 1 3 — 6 8 5 7

And so on. Then I worked out on the case when N = 5 (more generally, when N%4 = 1), and I noticed that simply adding n to the sequence is ok.

For N = 6, or N%4 = 2, you have to pop the last element (3) of your sequence, and mix the remaining two elements:

2 4 1 5 3 6

And lastly for N = 7 or N%4 = 3, an extra step, also removing the last element and mixing the remaining three elements:

2 4 1 5 7 3 6

Can you explain your approach

I just saw your solution for G, where you visit a node if it's not visited and then break out of the loop. What if you start from Node 1, then visit Node 3 and find out that permutation starting from 1->3 is not possible but permutation starting from 1->4 is possible ? You are not visiting node 4 from 1 as you have a break statement.

Rated for participants below 1400 rating

Map has a time complexity of O(nlogn).

The total complexity becomes $$$n^2*\log{n}$$$, which is higher than the expected complexity. The extra $$$\log{n}$$$ factor arises because of using map

there is no valid answer for cases like n1=0 and n0 and n2 being both being non zero .your submission will not be evaluated on these type of cases.

I got accepted with two pointers (which you can relate to sliding window). My approach was going through each element of the array and finding a subsegment with a sum equal to the element, as long as the difference between the two indices $$$l$$$ and $$$r$$$ is higher than 1. Two pointers has a complexity of $$$O(2n)$$$...so you can simplfy it to $$$O(n)$$$, and doing it for each element gives a complexity of $$$O(n^2)$$$.

Here's my submission: 79549243

Just to be sure, I also used printf and scanf instead of cin, cout and FAST I/O, as it can be even faster with large inputs. Also note that I could have also saved the result for previous numbers to make it faster when there are repetitions, but in the worst case scenario where that wouldn't happen, it wouldn't be of much help.

use this function for each elements of array ,increment ans by 1 if this function return true,take care of the function it return true for subarray of length one also but in our case it should be at least two. overall time complexity O(n*n),space complexity O(n). my sol

Rating will be updated soon!

1 1 8 1

For a case 1 2 0, your code is producing a output 10100. In your output n2 = 3, but it should be 2.

submit GNU C++14 or GNU C++17

I had the same problem during the round. I fixed it by replacing pow function with a variable starting in 1 outside the loop, and multiplying by 10 each cycle.

(I kind of misunderstood what you said, so I'm rewriting my comment.)

That sentence means how to handle cases like 3 0 0 or 0 0 4.

For 3 0 0 you need 0000, and for 0 0 4 you should output 11111.

Testcases such as 3 0 3 will not appear at all, since there must exist "01" or "10" somewhere so there is no solution for this case. The problem statement says that impossible testcases will not be given.

In your submission of that code, the judge says it failed in case 54 of the 2nd test, as you didn't give an answer to it, although it exists. Luckily that line of the test case is shown, and it seems that fails with 6 4. And as you can see, you can represent it with numbers 1 1 1 3.

The issue with your code is that you are using map, and increases the complexity of your solution to $$$O(n^2*n log n)$$$, giving TLE.

for every n integers , there are n-1 integers before it which are not divisible by n; say n=4, then there are n-1=3 integers 1,2,3 which are not divisible by 4.

so for after every n-1 positions,there is multiple of n . So our ans is shifted by 1; then for k postions, your ans is shifted by k/(n-1);

but if k is divisble by n-1 , we dont need to count the final shift.

So we can check for only k-1 pos , i.e shift= k-1 / (n-1)

shift=(k-1)/(n-1); ans= k + shift ; print ans;

problem E

Arrays in C or c++ are allocated in contiguous memory. Let your array size is 6 and you store 8 elements in the array. Then the two extra elements may or may not be stored in the array. It depends on your memory location. If the two extra elements stored lie in another's memory location (i.e. stored in those locations where memory is already allocated) then the compiler will show some error, but if those additional elements get some unallocated memory or free memory then there will be no problem while running the program.

In your case, the additional elements are getting free unallocated memory in the memory allocation (i.e. program's virtual memory), so your program is not showing any error. It varies compiler to compiler.

That depends on the perspective and the mathematical background. For me 1329B is more or less unsolvable. I remember having read the editorial some days ago but still could not instantly tell how it works.

You Can Refer This Explaination

You did not check the sum int k = pre[j]-pre[i]; to be in bounds of the array, but then write at that position. h[k]=0;

It is guaranteed that the answer for given n0,n1,n2 exists.

Because either of them will eat the candy at the index l=r. If you use l<r then 1 candy will remain uneaten.

This loop?

for(k = 0;k<=i;j++)
		{
			u+=x[k];
		}