Also thought of it, but couldn't code it in time. The basic idea is that you have n-1 operations at most, but n elements in the array. Hence, no matter what operation, it is guaranteed you get two elements which are divisible by the operation number. I couldn't really prove that this will extend from any operation to all operations, so a proof of that will be nice.

Thank you! Which algorithms do D problems usually end up being? Most of the times, I just solve ABC in Div2 :(

Congratulations! Can you tell me how to reach candidate master from expert? I notice that the difficulty jump from expert to candidate master is large.

Just to make sure my A doesn't fail, can someone verify this logic:

If string is "()" it is impossible.

If string is alternating for example: ")()()()" then you can use "(((...)))"

Otherwise you can use "()()()()()..."

Here is the code.

Do you have competitive math backgrounds? If so, what?

No, because if there is a cycle, then you:

a) have one of the potions in the cycle which is trivial or

b) don't have any of the potions. In that case, you will eventually revisit a node. Since a revisit is only possible due to a cycle, you will realize that the node came via a cycle and then can just buy the cheapest potion in that cycle.

No, take inspiration from Duolingo. We need a small green owl who will take your family hostage if you don't do your daily 3500 rated problem.

If you are interested in the range update method of solving the problem but you need an easy way to do this, I recommend the square root algorithm. It's more suited for beginners, and it is what I used in the contest.

This is the first testcase:

5 1 2 3 4 5 3 3 2 4 3 4 5 1 4 4 1 3

The first number is n, so there are n — 1 edges with follow. Let us start with the first edge. "1 2" means an edge is drawn between vertices 1 and 2 (depicted by a line connected 1 and 2). We do the same for edges "3 4", "5 3", and "3 2".

Besides F, D was the only graph problem...

I loved the round! I hope you all get your delta increases!

Praying for your speedy recover :D I hope your teeth are cured!

Thank you! I am right now reading about the suffix array so I can understand your post.

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

Sorry, I forgot to mention that, the length of T is 10^5 at most.

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

Here is my guess, since there is no statement in the problem which says: "the sum of all n over all test cases is less than 10^7," it is right to assume that there can be 1000 test cases where n = 10^7.

To initialize your dp array of size n + 1, it takes O(n) time. And there are t test cases. Since you are making a new array each test case, the total amount of time to make your dp array is O(n * t). n is at most 10^7 and t is at most 1000, so multiplied this is 10^10. Those many operations will certainly time out.

Maybe you should collect as much health as possible, return to the source node, and then go to the end node and see if you end up with a positive number?

Thank you! Here is so more info:

I forgot to mention that yes, I am IOI eligible.

I am 1050 rating on codeforces, so I usually try 1200~1300/B~C problems to challenge myself.

I sometimes use stopstalk.com or Dr. Mostafa Saad Ibrahim's practice problems spreadsheet (https://docs.google.com/spreadsheets/d/1-n9Fnvhsnvsqh-IerE_yyIshw5RUNer_7EjwF_GW-TA/edit#gid=0) to choose problems.

Hi! I am very interested. I know I am not very good at CP but I am willing to put in the effort to do this.

I am currently in USACO Silver and my best score on a contest was 404. Is that too high? I do usually get 0s on a silver contest.

Here is my repository: https://github.com/Glastr1er/atharvd-CPTutoring

Here is a hint: break up the Fn by Fn+1 rectangle into a Fn by Fn square and a Fn by Fn-1 rectangle. Keep breaking the rectangle until you break up the larger rectangle entirely into squares.

I absolutely love this tool! I am indebted to you forever.

The USACO is just not as famous as the AMC.

12835 users (it's important to understand the difference between users and actual people; one person can have two accounts) logged into the contest in the 4 day span in January in the entire world. 4773 people took the USACO in the USA.

In the entire world, last year, we had 71143 students take the AMC8 (and we know there are no duplicates, since the AMC8 is properly proctored). 68214 people took the AMC8 in the USA.

To be perfectly honest, less people care about USACO than AMC tests.

Clearly this binary search implementation is meant for finding the maximum value of x, what about finding the minimum?

Can someone explain to me how pow(a, b) uses floating-point numbers?

You can check other people's solutions if you've locked your own problem? This feature should be banned!

You have to wait for the winter holidays to come around to change your handle.

I have never seen someone actively tell they are cheating.

MikeMirzayanov

Yeah, pretty sure my friend wasn't thinking straight when they said it was straight-forward implementation. I'm guessing there might be a binary search way to do it too.

Of course, it was after the contest window closed.

Here's why I thought P2 was a graph problem. If I reversed the edges (signs), then I could use DFS from every vat of food to calculate the initial cost. But anyways.

I also thought P1 was a graph problem, but someone told me it wasn't (and I, unfortunately, believed them). Of course, I just don't know what to do with it :(

USACO Jan 2023 Silver P1 was not related any way to a functional graph. The graph problem this month was problem 2.

Let me explain why. What is the definition of a functional graph? Quoting the Usaco Guide, "in a functional graph, each node has exactly one out-edge. This is also commonly referred to as a successor graph."

So if string A was "ABC" and string B was "DEF" then our graph would look like:

A -> D

B -> E

C -> F

which is not a functional graph because nodes D, E, and F, do not have one out-edge.

I also tanked the USACO silver contest, hopefully we can improve together!

I know some people used a seg tree over a difference array, but did anyone else have the same idea but do it with a fenwick tree? https://codeforces.me/contest/1791/submission/192095662

Here's my advice. If you're moving to another continent, your decision should not be based solely off of Codeforces.

I wonder how much worse ChatGPT's going to make things :P

How do you take 40 minutes for A? Literally just brute force.

I'm so sorry, I should have specified that this observation comes from the December contest, not the January one. I have not taken the January Contest yet.

I can only speak for silver, but who has noticed that the people writing the contests are different than last year? Perhaps this explains the variability in the problems and why they are more ad-hoc.

How to spend the weekend is up to you. A lot of people here on Codeforces like to do contests. There's no point doing competitive programming if you don't enjoy it.

For further information about this, read the Competitive Programmer's Handbook.

Sum query over a range takes $$$O(\sqrt n)$$$ time.

I submitted, it got accepted both times. The only thing I can think of is this, locally, the MOD variable keeps getting reinitialised for every test case, but globally, it is set once.

The one with MOD inside got 1794ms The one with MOD outside got 1294ms

Wait, upper_bound() exists? I only learnt the latter form. What is the first function useful for?

Sir, do you know how long it would take to input the entire array?

It would be much appreciated if you tried and exploded your computer!

Can you imagine how few people would be under grandmaster then?

The problemset should should have a tag for permutations, to practice for these kinds of problems.

I wish we were allowed to downvote more than once for such comments.

Benq > tourist in rankings

Who would like to bet that Benq will overtake tourist sometime in 2023?

Goodbye 2022 :)

Did anyone else miss A because they sorted array b?

Not sure why people cheat. Sure, get to LGM, be hired by Google, and then be fired after everyone realizes you can't code a union find.

Yes, I increased my rating, but not to LGM. And I like purple more than cyan.

C was interesting. At first it looked like another mathematical array problem, but the solution turned out to be simple.

Get to USACO gold :)

In problem B, it says an array A is a palindrome if A[i] = A[n — i — 1] for all values i from 1 — n. However it should be A[i] = A[n — i + 1].

Thank you :)

Can someone give me a hint on problem D?

Thanks in advance.