My solution was calculating the probability of obtaining an array of length n with the gcd of the array(except the last elemnent) as x with ending element y where $$$x,y \in [1,m]$$$, $$$ n \in [1,\inf]$$$ and y is coprime to x.
Then, summed up the contributions with a bit of math.

Really cool problem set!
Although, I do wish the contest was 2.5 hours instead!

(F[x] * (F[x] - 1)) / 2 should give us the number of subarrays with XOR == 0.
This works for all positive x and fails when x = 0.
The correct formula when x = 0 is (F[0] * (F[0] + 1)) / 2. (You can just take a prefix of the array with ending element as 0 but this is not possible when x!=0 ).

Also (F[0] * (F[0] + 1)) / 2 = ((F[0] + 1)) * ((F[0] + 1) - 1)) / 2.

So we can just increment F[0] at the beginning to handle this case.

If original P had the values x₀, x₁, x₂, x₃ and suppose you flip x₁, then P would become .
( prefix xor is basically prefix sum for each bit mod 2. If you flip the parity of any bit, then all the parities of further elements in that bit would be flipped too.)

Then if you flip x₂, it would become .

So, regardless of the elements you've flipped, either the current prefix xor is correct or it's complement is correct.

Knowing which one is correct does not matter since you will be comparing both of them anyway.

We need to minimize the number of subarrays with xor==0.
Let's build a prefix xor array, P, and use a map, F, to track the frequency of each element in P.
If we cannot change any element, then answer would be:

If we can change elements to its complement, we can try minimizing the summation.

To do so, we can try breaking up a single element with large frequency to many elements with lower frequency. This will decrease the sum because of the property a₁² + a₂² + ... ≤ (a₁ + a₂ + ...)² for non-negative integers.

We can iterate over the prefix array and if x is the current element and as its complement, we choose the element with the smaller frequency until this point and increment its frequency.

Now, the only case left is how do we handle choosing when .
It actually does not matter.

Suppose we choose x over , then it would only negatively impact us when we have another element later on with x as one choice and the second choice being some other value apart from . But this will never happen because each x is associated with only one, unique .

Hence, the greedy algorithm would work.

Has the distribution been decided yet?

I used co-ordinate compression. I got WA TC #5 when I was printing K in terms of the compressed value instead of the real value.

This has happened before and the rating changes of both contests were based on the rating before edu round.
You can actually hit orange if your rating is ~1900 and you are top 10 in both div 2 contests.

Edit: Looks like they fixed it this time.

Most likely it will be held this week. Will update with finalised date/time once I get that info.

We apologise for the scoring issue. We underestimated/overestimated a few problems.

Glad to hear you like the problem set :)

It was a last minute decision, unfortunately. Please check the update for more info.
Really sorry about this :/

Yes, there were issues which were out of our control. Please check the update.
Extremely sorry!

Auto comment: topic has been updated by Vicennial (previous revision, new revision, compare).

Auto comment: topic has been updated by Vicennial (previous revision, new revision, compare).

Yes, you wouldn't be able to copy-paste the code.

Although, You could try writing it manually on your system at the expense of time.

You can assume for now that all of the contests would be unrated.
If there are any changes, we will announce them.

Do you use tournament tree in this case because iteration is faster than recursion or is there more?

The time spent after skipping first 'x' classes and last 'y' classes.
It can be calculated in O(1) if you store all lecture times in a vector.
Let size of vector be vs.
val= 0 if x+y>=vs
val= v[vs-y-1]-v[x]+1

Both Pre-calculation and main DP are O(nk^2)

Observe that its useless to skip any lecture which is not at the beginning or the end.
So, we should always skip some prefix and suffix of lectures.
Let x be number of skipped prefix lectures and y be number of skipped suffix lectures.
Try all x,y such that x+y<= k .
pre[i][x+y]=min(pre[i][x+y], val)
(pre[i][x+y] is initialised to inf)

Calculate pre[i][j] = Minimum time spent in university on i'th day after using j skips on this day.
Then calculate dp[i][j] = Minimum time spent in first i days after using j skips.
Answer is dp[n][k].
Transition is dp[i][j]=dp[i-1][z] + pre[i][j-z]. 0<= z<= j

Consider ranges [3,5] and [9,12]. After [3,5] you will move the left pointer to 9 while deleting elements 3-8. But you haven't added elements 6-8.

One way to fix this is to always expand the range first and then contract it.

Is there a CHT list?

Can be done in an even easier way using only vector+lower_bound.
Refer here

Another problem which can be solved by this technique: Coloring Tree
Its easier than 600E - Lomsat gelral.

One more : 932F - Escape Through Leaf

Refer to DQUERY solution using BIT here.
For this question, ans= Number of distinct elements in range — Number of elements having L[A[i]](last occurence) within the range.

99 after the plagiarism check, congrats :)

You can also solve it in O(M*(N/32)) in a very short code using bitset and exploiting codechef's memory limit.
Code

Why does each chapter cost $29.95 when you can get all 15 chapters for $39.99 on Springer?

I think it would be better if each chapter costs around $3-$4 so that those of us who cant afford the whole book can still read the chapters we need.

Could you delay the round by 10-15 mins ?
It would allow people to participate in both CF #460 and CSA #67.

X=(A+1)*(C+1)-1 + B*D.
A=10/1010 type in left string.
B=1/101 type in left string.
C=10/1010 type in right string.
D=0/010 type in right string.

For each type A seq, we can join it to a type C seq. We add +1 to each of these values to account for empty seq and subtract -1 finally to account for taking empty seq from both sides.

For each B seq, we must combine it with some type D seq. So this contributes B*D sequences.

Till now, I've only seen one person actually hit their target after making a post/comment similar to this blog.
Reyna's Comment

Oh right, answer will never be -1 in this case.
Thanks

Any idea what TC4 is in C?

I did the same but used LCA to check if its an ancestor and it got TLE on TC10.
Submission
Fixed and it passed well within the time limit (271ms)
Submission

Not sure how yours passed.

Lets say you need to find x! where 2*10⁹ > x.

Now, we have stored 0! , 10⁶ ! , 2*10⁶ !, 3*10⁶ ! .... and so on till 2000*10⁶ ! .

Now there will exist some integer 'z' such that z*10⁶ <= x <= (z+1)*10⁶.

Since 'z' will always be <=2000, we would have already calculated z*10⁶!
Now note that the difference between (z+1)*10⁶ and z*10⁶ is 10⁶.

Therefore we would need to multiply the pre-calculated z*10⁶! value by atmost 10⁶ integers.

Cool. Think what you will.

Here's my perception of you: "Coward".

You must be so brave spouting shit about people behind that fake account.

It doesn't matter if it was for you or for someone else.Main fact is you do this shit in name of fun.

You're acting like I'm shoving it down your throat.
a) It was posted on his wall. Not on cf,not on some blog but his own goddamn facebook profile.
b) Privacy setting was: Kumar's friends of friends. Not public.

Are you so alone that you never have fun with friends?

How is this even related to this blog? I posted it on my own classmate's profile and the post was meant for our friend circle and it isn't even serious.
Anyway here's some additional context:

Source: Check comments

Hey, we registered our team Phoenix under the name 'phoenixiiti' on the pantheon website because someother team had taken the name 'Phoenix' already.
Commenting to avoid any issues.

This is mostly related to the browser.
It happens to me on chrome regularly.

I use firefox for hacking and I haven't faced this issue.

Hack cases for B and C?

Rating Change: 2340 -> 1989 ( -351 )

Please fix...

Author solution uses persistent segment tree for offline solution
Persistent segment tree is used for online solution , not offline.
You can also use a merge sort tree for online solutions. (Queries are log^2(N) though)

Is it solvable by Mo's Sqrt Decomposition?
If you use BIT along with MO's, then yes.
But you can just do a linear traversal if you're using BIT.(As mentioned in the editorial)

The top 100 will also win awesome hoodies. (Winners will be required to give proof that they are currently enrolled in the university they represented during the University CodeSprint.)

Am I right in assuming its top 100 from student leaderboard?

Because of this:

#ifdef PRINTERS
#include "printers.hpp"
using namespace printers;
#define tr(a)		cerr<<#a<<" : "<<a<<endl;
#else
#define tr(a)    
#endif

On online judge, the #ifdef PRINTERS condition fails so tr(a) is substituted with a space.

If you iterate the above process 10 times, the probability of not getting the correct answer is about 10^(-30).Thus, the solution works because k/n is less than equal to 0.02.

How do you derive this? The concept seems similar to 844D - Interactive LowerBound but a derivation would help me understand better.

How do you solve The Six Thatchers?

Substring aacb = 3(aacb(0, 2, 3), acb(0, 2, 3), acb(1, 2, 3))
Substring acb = 1(acb(0,1,2)

You have to find the answer for each substring and sum up the values.

Holy shit! Been using HR for more than a year and did not know it had a 'college contest' section :P

C++11 isn't always better either.

#include<bits/stdc++.h>
using namespace std;
int n;
void go(string s,int x){
	if(x>n) return;
	string p="1";
	s+=p;
	for(int i=0;i<20;i++){
		go(s,x+1);
	}	
}
int main(){
	n=5;
	string s="1";
	for(int i=0;i<20;i++){
		go(s,1);
	}
}

Results:
G++ 11 5.1.0 = 7987 ms, 2044 KB
G++ 14 6.2.0 = 889 ms, 1856 KB

Thread discussing this speed difference can be found here.

Yes.

If you're going to insult me, atleast state some reasons why you think I'm 'dumb as compared to others' and a 'shitty codr'.

Let me state some dates first.
Contest where I became Div 1: Round 417, 01/June/17
Next D1 contest: Round 419, 17/June/17 (Did not participate)
IPC Camp announcement: 18/June/17
IPC Camp selections announced: 24/June/17
Next D1 contest: Round 421, 27/June/17 (Did not participate) (Moreover, it turned out to be
unrated).
Next D1 contest: Round 423, 11/July/17 (Participated)

Between the camp announcement and camp selections, there were literally 0 contests on cf.
I skipped 419 before the camp was even announced and skipped 421 after the selections were already over.

Now, Why didn't I participate in Round 419?
Yes,I was too scared to lose rating. I started college as well as CP last year in July and my target was to hit Division 1 before I started my second year and I finally did accomplish my goal.When I read Div1 A , I had 0 idea how to solve it and hence was too scared to submit anything.

Why didn't I participate in Round 421?
I was not selected for the camp initially. Around 30mins-1hour before the contest was scheduled to start, I got a call and an email saying that I was selected on the account of one of the original people not being to able to make it. I was too excited on hearing this news to participate. If you dont believe me, I can upload a pic of the date/time of the email and/or call.

Moreover, The applications considered max rating too. Me participating/not participating would have had minimal impact on the selection.

D can be done in O(N).
Code-28146537

Geometry and Number Theory By Kevin Charles Atienza | Indian Programming Camp 2016

Also, here.

Seems like the blog author might have deleted it.
It shows no blogs in his profile. http://codeforces.me/blog/adedalic
Edit: The blog is back.

That's where persistent segment tree comes in.

On the website its mentioned:
You will have to solve 8 tasks in 2 hours and 30 minutes.
but in the blog:
You will have to solve 7 tasks in 2 hours.
and also : 7 tasks of varying difficulty that need to be solved in 2 hours and 30 minutes.
I'm guessing the website is correct?

Maybe not. But IMO, topcoder is losing popularity and they have to do something about it before its too late.

Btw why cant topcoder have more problems in a round? Even 1 extra problem would help decrease the massive jumps in difficulty.

True. I'm used to using fflush(stdout); because I have this in my code:
#define endl '\n'

    while(smr.size()){
        cout << D[smr.back()] << endl;
        smr.pop_back();
    }
    fflush(stdout);

Change it to:

    while(smr.size()){
        cout << D[smr.back()] << endl;
        smr.pop_back();
        fflush(stdout);
       int x,y; cin>>x>>y;
    }

I'm guessing its because your program terminated before reaching end point.
When checking if the direction is correct/wrong and if its wrong, your position will be the same so you will have to repeat the move with the opposite direction.
If you havent done this, I guess it might be the cause of the error.

Probably due to buggy code.
I used the same logic.

Its actually very easy to generate random permutation.
Suppose N=5000.
Put all elements from 1 to 5000 in a vector.
Then use random_shuffle() on the vector and print the elements in order.

Code: 27377920, http://ideone.com/wHHPs1
It might seem that it might take too much memory but in reality it only requires NlogN memory since each element will appear in atmost logN nodes.

In each node of segment tree, store the numbers in the range start-end and sort it.
Now, when there's a query like: 1 100 50
Then split it into two ranges:
1. 1-50
2. 50-100.
In the first range find the number of elements greater than val[50](let it be x) and in the second range find the number of elements less than val[50](let it be y).
Getting this number can be done through binary search in the required nodes since the elements stored in each node are sorted.
If x==y, then position wouldnt change.

Answer by yeputons: here
Also check this: http://codeforces.me/blog/entry/21772?#comment-264557

Always use this: http://codeforces.me/problemset/customtest when you want to check execution time.

Because its generally known that upto 10^8 operations would fit in 1-2 secs.
I too used seg tree because I didnt check the constraints properly.
I dont like this question too.

Because n,m<=10^4.
Intended soln was O(N*M) bruteforce because 10^8 fits in TL.

Didnt check B's constraints and used seg tree :/

Snackdown Pre-Elimination Round lasts for 24 hours and the ranklist is based only on problems solved.

Submissions enabled there too.

I still think its a misunderstanding.
That blog just lists the general info which was already available on the codechef website.
Also I couldnt find any instance of manvscode working with codechef.

This blog was made by the contest admin himself and I dont think he would have made this if the other one was official.

This is the official one whereas the one you linked is made by some random person.
It was downvoted before this comment.

The problems are sorted by number of Successful Submissions.
'Same Snake' just happens to be least solved because of implementation I guess.

In the 4th move,
Igor will play dfd?e?.
Now Oleg is forced to put e in the 4th position.

Check if Y is a prime number by using Miller Rabin test.
If it fails, check if the sqrt of Y is prime by using the same test.
If that fails too, then the number must belong to the third case.

TFW you solve 0 problems and still get +38 rating increase.

I did it in a clean way without any case handling: Click

EDIT: Nvm , it failed systest :(

It also might be browser related. The same thing was happening to me in chrome but I swapped to Microsoft Edge for a sec and the page loaded. Not sure if coincidence or not since I didn't try again.

You neither need a BIT nor the block_cnt[SQRT_N] method which satyaki3794 mentioned.

All you need is a simple cnt[N] array which you need to update every time the size of a stable block increases or decreases by 1.

Example. If the current stable block of lenght x increases in length by one, just do ++cnt[x+1] or if it decreases by one, do --cnt[x].

The reason this works is because the left/right pointer in MO's algo moves by one unit every step and hence the size of a stable block increases or decreases by 1 every step.
Therefore if we have a stable block of size 5, then it must have existed with size 1,2,3,4 at some point of time and hence the corresponding count array had been updated.

So finally, the number of blocks of order 'k' is simply cnt[k].

You can refer to my solution which used the above method here

Logic for Div2 C please?

Logic for B & C in round 1A please?

Check here.

I used multisets so I only had to iterate through first node+neighbours.
It took 1s but TLE is still a worry.

Let there be a set of nodes which have equal and maximum weight.
For each node 'x' from the set,
Final weight of x: Same as original weight
Final weight of neighbors of x: Original weight+1
Every other node: Original weight+2

Do this for each x in the set and calculate the minimum maximum weight.

EDIT: I got a WA. The reason is that we have to consider every node rather than just the max nodes.(Imagine case where all max nodes are connected to a single smaller node)

No, this is wrong.
Take the case:
6
3 3 3 3 3 3
1 2
1 3
1 4
1 5
1 6

Answer would be m+1(4) for this.

These Bots!

I am unable to view the solutions of other contestants even though challenge phase has started.

Edit: Solutions are now visible.

For Div 2 B,
Whats the correct answer for :
5 0 4 1
5

Main confusion:
Does abs(b)<=l check happen even if b is a bad number?

Definitely not 2.
Option 2 will just encourage people to cheat which will ruin everyone's experience.

Also notice that k can be found using a formula, but such solutions could fail by accuracy, because the formula is using the square root function.

Is there any way to get the solution by formula either in c++ or python while still retaining accuracy?

Nope, if n<=m, then ans is n.

Yes. Are you trying to say that G++14 optimises it automatically?

Codechef is really slow when it comes to updating ratings.
It usually takes anytime between 4-7 days for the process to complete.

You can solve it by using sets.
Initially maintain a vector<pair<int,int>> which holds the value and its index. Insert all the indexes into a set.
Sort the vector according to the value in increasing order.
Now,we iterate through the vector.
In each step, we erase the index corresponding to that element in the set.
Then find maximum index in set and subtract it with current index. Let this value be z.
Then ans=max(ans,z).
Code