You don't need a dp array for it, you can pass a boolean strict variable and return directly when the strict is false, it saves a lot of recursive calls. Sharing my submission for ref https://atcoder.jp/contests/arc173/submissions/51142683

There's too much code to debug but I noticed you're keeping hi as 1e13, that's not sufficient, you need to keep hi as 1e18

How did you solve A if you didn't use digit dp + binary search?

Write a function which given a number K, let's you know how many numbers <= K exist which are Neq numbers. You can use digit dp for it.

Next, use binary search on this function to find the smallest number which gives K as the answer.

Hashmap's amortized complexity is O(1) but due to collision its worst-case complexity is O(n). The tests for this question are designed in such a way that hashing will result in a lot of collisions, therefore, searching will be an expensive operation.

It isn't wrong. It's just inefficient. Replace the freq check with length check and it will produce the exact same output with less iterations.

You're checking if current digit's freq is greater than 10 or not, it could be possible that it is repeated only once, in this case you will check for all substrings (not just 100). You need a length check instead of individual digit's freq check.

How did you write in white font?

Well you cracked the logic right? The only thing that you lost is rating. As long as that's not a concern, this shouldn't bother you. If it is a concern, you'll remember it the next time you see a similar question. Win-win for you, cheers!

As a competitive programmer, you're expected to think about the worst case complexity while writing logic. And the testers seem to have the same opinion too. There are questions where you get TLE because you used cin cout without the fast I/O modifications, or because you forgot to pass vector as a reference to a function. You're expected to know this in cp. You might find the information on GFG and LC but you actually get to see its impact when you're solving such questions.

Lol... competitive programming is meant to increase understanding of data structures. You should learn from this incident the difference between ordered map and unordered map.

Because first is just appending a char at the same address, whereas the second one is actually concatenating 2 strings and storing the entire result at the address.

Why ask to signup first? How is signing up going to benefit the user?

Chance to leave pupil

Go in reverse. Think about how many rotations are required to move n back to the last index. Now look at the array till n-1 index only and do the same thing.

This is great! Helped me find why my D submission was failing. Just one line change and AC :_)

My bad. Edited the comment

Sort the array. Take the sum of all elements except the last one. For one football, this sum should be greater than the largest element. Else the count is the difference between those 2.

My bad, dk why I typed fibonacci. Corrected it.

Store the factorials numbers <=1e12 in an array (I think the count of them is 13 or 14)

Just iterate on all subsets of them (by iterating from 0 to 2¹⁴) and then subtract the factorials number from n (let's call the resulting number as temp). After each subset, count the number of set bits in temp. This will be the number of powers of 2 required. Do this for all and keep track of min so far. Submission https://codeforces.me/contest/1646/submission/148374185

I did it without recursion

How many of you logged in at the usual time?

It's easy to prove why sorting is needed.

Let's say you have an array [x, x², x³, x⁴]. Optimally it's easy to see that all pairs will be used but let's say you decided to pair x² and x³ together. Now x and x⁴ can't be paired together so you lost one pair.

You can create such test cases easily. One such example is [4, 2, 1, 8, 2, 16]

Because for each valid query you have k different choices and these choices are independent to the ones that selected so far.

The editorial explains it in quite detail. Try to trace out on paper/whiteboard where you're unclear (I did and it helped me a lot!). If you still have doubts, I can help you resolve them.

Let's say after i'th query you get all rows (column can be anything) in the query. This would mean that whatever colours were present in all the cells before, are updated (possibly to the same colour but updated for sure) so any query that was processed before i'th query is no longer relevant to the final state. If however, we do process them in reverse order, it will update colour of some cell which shouldn't have been the case. Same goes for queries covering all columns instead of rows hence we have to check for both.

I appreciate all the work that all problem setters and editorialists put in creating problems and writing editorials, but I want to know why there's a delay of almost a day between contest ending and editorials getting out? The excitement and the curiosity fade away (at least for me) due to such a long delay...

There are 2 ways to do this. First is to build a graph of which numbers you can reach from a given number and then BFS from 1 to each number to find the shortest distance or use brute force DP. I thought of both but decided to use 2nd approach. My submission https://codeforces.me/contest/1633/submission/144766502

I calculated the steps for all numbers less than 1000 and print the max. This is required as the given constraints for k (<=1e6) is not suitable for knapsack.

There's a much tighter bound, use steps * 12. You can reach any number less than 1000 in less than or equal to 12 steps.

I thought of BFS too but implemented array of sets approach along with DP. My submission https://codeforces.me/contest/1633/submission/144766502

knapsack

calculate the number of operations required to convert ai to bi and then knapsack.

You can have a boolean array and mark the presence of a number as you process the array. Now move the pointer until you find the first absent number. O(n)

Does anyone else think Problem C statement is unnecessarily complicated?

If the current element is in its correct place, do nothing
Else, check if there is room to swap it to its left or its right. If no, print NO
If it didn't print NO for any of the elements, print YES

When you wait for 5 minutes just to see the verdict as Wrong Answer on pretest 2 :_(

Way too long..

Last problem has 2 subtasks, if you solve just the easy one, you'll get max 1750 pts, if you solve both, easy and hard subtask, you get max 1750 + 1750 = 3500 pts. Also, avoid caps please :)

I see you're a man of tradition

People can face issues while downloading the large input file (like slow net, power cut, system crashed, etc). Password was introduced so that the timer will start after the user has finished downloading the input.

You don't need to install anything on MacOS. You just open the file normally and enter the password in the prompt.

FST in B cos INF was not large enough :_(

Not everyone is a CM bro, I think you meant read all the problems :P

If Google can do it, I don't think the reason FB isn't doing it is cos it's hard

The downside of giving an easy A is you get a long queue...

speedforces!

May you get the most downvotes anyone has ever received!

I compressed elements to 0 to n-1 and checked if a[i] — a[i-1] == 1.

Dude, you don't ask for help during a contest!!

Yeah, I got it as well. It's a stupid question. Finally figured out the problem.

I personally think the post should be upvoted/downvoted after the contest has ended depending on the quality of problems and/or any issues faced...

We will find out soon enough..

Place your code in spoiler. It's eating up too much space.

Found the mistake in my solution. Missed sorting. Just adding that and submitting again gave me an AC :(

It's not O(n). Rewrite the eqn as aj = (i+j)/ai

Now, as aj is an integer, i+j must be a multiple of ai, you need to check only ai blocks in each case. Since ai is distinct, this is similar to prime sieve in terms of time complexity.

My logic for C, take the sum of differences of all pairs and subtract the difference of adjacent elements from it and print the answer with a negative sign. Why is this failing?

I wasted 90 min because of that lol

Anyone in Div 2 feeling like they accidentally participated in Div 1?

It means the problem has an easy version and a hard version. Solving just the easy version would give you a max 1500 score, solving both would give you a max 2250 score.

I use it to get a rough estimate of how many problems will I be able to solve..

I kicked myself for spending 1 hour on C :(

This is the intended solution.

Notice that when you swap a pair, you have to swap some more pairs to make the configuration solved. If you swap ai with bi, you have to see where bi is present in a[]. Keep on swapping such pairs until you get ai in b[]. All these pairs form a cycle together which says that if you swap any one of these, you have to swap all of these to keep the configuration solved. There are only 2 states possible for a cycle, straight or upside-down. Count the number of cycles and print 2^cycles.

No, you just find histograms that are higher than both the neighbours and reduce them to until its height is equal to the highest of their neighbours

Submission

The person who explained B's sample test cases

Well, good luck with IOI!

This is a relatively easy problem for practicing max flow, you should take this as an opportunity to learn it.

-_-

D :_(

I disagree. I don't see why this should not be asked before a contest.

Damn, I actually constructed the array by using set and vector. Didn't see this observation!!

I think A was difficult than usual. I submitted A in 18 minutes still had a decent rank for a while.

You don't talk about stuff like race or religion on a cp website.

Why is this comment getting upvoted?

I gave up after solving 2 problems as I wasn't feeling well, but now that I read problems C and D, I find D more straightforward to think (and implement) than C. Maybe that could be because I have implemented upwards propagation before.

Did you get AC without sorting?

So how should system tests be designed such that when a code passed pretests but fails system tests, people don't say that the pretests are weak?

I'm going through your playlist and haven't finished it yet so don't know if this type of bugaboo is covered, but I found it interesting. Bugaboo

Great job creating this playlist though!

To everyone who's downvoting, atleast let me know what's the point of having system tests?

Your contribution is mainly memes, not anything useful like helping someone out or sharing something useful. I might have a negative contribution but at least the intent was to help the community.

Follow your own advice

Pretests exist to check for corner cases and smaller-sized inputs, that's it. I didn't imply anything about scamming people, think carefully before you accuse someone of something.

If you put every possible combination in pretests, what's even the point of having system tests?

true

This isn't related to your question but you can do this in 1D dp as well

int minimumXORSum(vector<int>& a, vector<int>& b) {
        int n = a.size();
        vector<int> dp(1<<n, 1e9);
        dp[0]=0;
        for(int mask=0; mask<(1<<n); mask++){
            int i = __builtin_popcount(mask);
            for(int j=0; j<n; j++){
                if ((1<<j)&mask){
                    dp[mask] = min(dp[mask], dp[mask^(1<<j)] + (a[i-1]^b[j]));
                }
            }
        }
        return dp[(1<<n)-1];
}

Usually, you use 2D DP in bitmask where the sequence of selection is important (like in TSP)

DP is overkill for this. The highest number that's not possible is 1099, which is less than 1111, so you basically need to check if the number is of form 11x+111y. This can be written in a simple for loop with max 10 iterations for a number. My submission

if (n>1099){
	cout<<"YES\n";
	return;
}
for(ll i=0; i*111<=n; i++){
	if ((n-(111*i))%11==0) {
		cout<<"YES\n";
		return;
	}
}
cout<<"NO\n";

I wasn't able to solve it either, but I think it's a theorem that one should certainly be aware of, (like people know about Extended Euclidean algorithm). Anyways, as the editorial has mentioned, this theorem was not the only method to solve it, the other one was pure observation, and looking at the constraints (only 10^4 test cases), it hinted that some kind of brute-forcing was required. I think this perfectly fits Div2 B difficulty.

It's an interesting theorem that has a rather remarkable statement, after a certain number, every number can be written in the form of ax + by (given a, b are coprime).

You mean bugaboo statements?

Friendly advice to cin cout users. Use

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

I suffered a lot because of this in the last contest.

Not sure what you intend to imply when you share about the google interview. In interviews, the constraints are different, even if you're able to solve a problem in optimal complexity, you might be asked to solve it using a different DS or less memory or anything else. Just cos you were asked to not use global variables doesn't mean it's a bad thing, the interviewer wanted to see if you can solve it without using global variables, that's it.

You mean to say the reason it's TLE has got nothing to do with the logic?? It was due to slow I/O?? I'll cry the whole night today :(

My submission?

https://codeforces.me/contest/1529/submission/117252283

I did exactly the same, still I'm getting TLE!! :(

Why is a simple DFS getting TLE on Div2 C??

This helps a lot. Thanks!

How do you know Edmond-Karp won't work for a question?

You can download the test cases from the website and debug your code.