I got stuck on problem 66 "Diophantine equation" for a very long time two years ago, because I thought you could solve it without googling for anything, as almost all of the first project euler problems. Definitely couldn't :/. Good topic.

First of all, if k <= n the solution is easy, so everything I will say is for k > n.

If you perform an even number of operations on an element you are guaranteed to decrease some value from it, since for each number you add you subtract a bigger number right after, so if you are trying to increase a value (and therefore made an odd number of operations) it's really only the last number you add that is the "deciding factor".

Knowing that, you should try to have the smallest number of your array, let's call it a(0), be added by K and a(1) by K-1, a(2) by K-2, ..., a(n) by K-n.

If (K-n) is an even number you can do it, because for each of the operations before getting to k-n you can just do an even number of operations on each element you change and you are going to end with all elements being ready for an addition.

Also, performing an addition and right after a subtraction, is going to result in decreasing the element by one, so you just have to add each (K-i) to each a(i) and then remove (K-n)/2, in total, from the elements of the resulting array, distributing it the best way to get the biggest minimum value.

If (K-n) is odd you won't be able to increase every element of the array, because to do that you need an odd number of operations on each element, but at least one element will necessarily have an even number of operations on it, so the best you can do is make this element the biggest one, a(n), and not add anything to it (instead of decreasing it) then you can add each value from k-n+1 to k to each element from a(0) to a(n-1) and you are gonna have an even number of operations left. Then again, you will remove (K-n+1)/2 from the resulting array in the best way possible.

If you want to solve D2 you do the same thing, but with some tricks to make it all faster, I can describe them if you want.

D could also be: print(negative integer)

Interesting, this is way easier, but I thought using randomness in the beginning wouldn't work, especially with small permutations, so once I realized the problem of picking 1 as your first number I followed the approach of comparing the first and second elements with each of the next elements until I got a gcd different than 1, since both can't be 1. Then you apply the normal strategy with the remaining elements and since you eliminated one number for every two operations I'm pretty sure this should work, although I haven't been able to get AC yet.

Sleepforces

I forgot my notebook and my school's computers don't have any IDEs nor compilers in them.

Gonna use an online compiler. Let's see how it goes

Haha, hadn't realized, I copied the wrong number

I did something similar (after the contest) but didn't use dp at all.

I iterated through all values up to 3*10^5 keeping track of all currently active sets (sets that go through that point) and then for each point I would, with a heap, find the index of the set with the highest index and apply the same formula as you (3 ^ (ind[x] — 1) * 2 ^ (n — ind[x])).

My solution: 998244353 *176949836 (oops)

(The heap implementation isn't the best and also it's a min heap, when I actually needed a max heap, but I was to lazy to get a max heap, so instead I just did some changes in other places of the code so that it worked with a min heap)

I spent the entirety of the round trying to solve D with XOR instead of OR -> -108

One of my most embarassing moments ever on a codeforces contest. And here I thought I had already taught myself well enough not to rush through statements. Such a simple problem, had I just read it right :/

If you use pypy, python is enough to solve most, if not all problems on codeforces. I've used mostly python so far (even though I know c++) and it has never failed me. You should only perhaps start worrying about moving to a different language way further down the road.

As for the speed of your code, it seems good. Maybe a faster approach could be to do w & 1 instead of w % 2, but I think pratically it will rarely make a difference.

In my opinion that's the best way a problem A/B can be. Still challenging, so you have to think to come up with a solution and beginners can develop their problem solving skills further than just improving implementation skills, but with a simple solution, so any beginner can solve it.

I would say the first 3 problems could all potentially be solved by someone who doesn't have a lot of experience with cp, but "beginner" includes a wide range of very different people.

Anyways, problems don't hurt, just go ahead and face them.. If you try and find them to be too tough for your level of experience just move on and go back to them another day or perhaps read the editorial once it's available.

You can't register within 5 minutes of the start of the contest. If you miss the normal registration period you have to wait until they start allowing "extra registration" with is usually 10 minutes after the contest has already started

dlt

Not sure I'm gonna be capable of providing a better explanation or solution than the editorial, but here is what I did:

1) I sorted all the segments by their left coordinates (their starts)

2) On the sorted sequence, I grouped all the consecutive segments of the same color

So using this as an example, after my grouping we would have the following array: {{1,3}, {2}, {5}, {4}}

3) I looped through every group of segments and for each segment calculated the smallest distance from it to another segment of a different color, for this I checked two things:

First: The distance of the end of the segment to the start of the first segment on the next group (the segment of a different color with the closest start)

Second: The distance of the start of the segment to the end of the segment of a different color of a previous group (previous group = starts before the current one) with the furthest end

To do the second part you have to always keep track of the furthest end so far, which is easy, but for each segment you want to compare it with another segment of a different color, so you have to keep track of the segment with furthest end so far and the segment with the furthest end that doesn't have the same color as that one, doing that you are good and can always apply the method above to calculate the answer for any segment.

In my opinion your solution seems a little bit more complicated than necessary and than the one given in the editorial.

I did something similar, but instead of doing

p = n, n-1, ..., n/2+1, 1, 2, n/2

I just did

p = n, n-1, 1, 2, ..., n-2

That way it's easier to implement and this works for both even and odd values of n, so you don't need to handle those cases separately

Solution: 175582981

Anyways, it really doesn't matter much...

I don't think it's the same. You don't need any previous background to start playing chess and it's a fun game that a very big amount of people learn at a young age. On top of that, the amount of reading and topics you have to learn at the beginning is fairly small, most of what constitutes the early improvement is pattern recognition.

To even begin touching cp, you have to first know how to code and without high school or at least middle school math you won't get very far. To even become a pupil you already need to know a lot of math and programming concepts (from the perspective of a twelve year old, you don't actually need to know that much from the perspective of a high school student). Very few people learn to code from a very young age and it would be impossible for someone who isn't simply a genius to learn high school math before the age of 10. So I think the odds of anyone becoming a grandmaster in cp at the age of twelve is super small.

Feel free to disagree.

Just complementing, recursion is a good path, but also not the only one

I wrote a dp solution using python and so far so good, don't really see how it could be hacked...

Same for me here, but with F. Got my submission accepted after the contest had already finished. It was tense.

Thanks! But unfortunately tomorrow is actually my first day back at school and the contests happen during school hours (11h30am — I'm Brazilian). Quite unlucky of me

Edit: I only have math at the time of the contest, I'm tempted to skip, we'll see...

Lost blue today :/ (again) In fact, I'm down to the exact rating you had before this round. How things change...

Well, you are not wrong, I guess it's mostly about knowing RMQ, but I'm not sure how easy of a concept it really is. I didn't know about it's existance until around a week ago, you can get pretty far with little theoretical knowledge.

I don't know if he cheated or not and I don't have telegram, but this guy really sucks at cheating... He is a newbie and only solved A and B in this contest. Also, he used his own (somewhat strange) template, the one he's been using for a long time, so it's unlikely that he "directly copied" anything.

Yeah, if you (siddhantchimankar) wanna see your actual performances I recommend the carrot extension

Not really, correct me if I'm wrong, but I think D is pratically impossible if you are not familiar with RMQs and this is not a basic concept, there are a few nice ideas involved in it and it isn't super simple to implement. I would say D is pretty much just about knowing the concept.

But I agree that it's a pretty easy problem if you have some familiarity with RMQs

If your rating is below CM you won't even be able to register to a div 1 contest and if your rating is equal or above CM you obviously can't register to div 2 contests given that you are a div 1 contestant.

Edit: Sorry, I think that CM's actually can participate in div 2s, but not when there is a div 1 round going on at the same time.

So was I.

Exact same thing! Dropped 116 rating points.

Another one bites the dust...

I feel you. It's funny we fell down to very close ratings too. Better luck to us on #809 I guess. The journey back to expert begins!

Well, that definitely didn't go very well... I'm lucky I won't drop to Pupil after this round.

Guess these will be my last words as an expert in the foreseeable future :/

Same! I also just recently got it, we are living on the edge here. Good luck!

Personally I don't think I would ever directly land in the xor thing. The human and logical approach to get to the solution and possibly to that xor realization would be to look for blocks/groups of elements that have some relation with each other or certain relevant behaviour, that's a common and effective idea that you can train yourself to pay attention to in some problems and can become better in finding/identifying.

For example, one group you might find is that all the elements with odd positions can only change the elements with even positions and vice-versa. But a more important one in this problem are the groups of ones and zeroes for example, you might realize that you can expand and contract those as much as you want, from there you start to get somewhere.

Try this test:

Input:
1
5
2 0 0 0 0

Output:
5

It doesn't change that much storing the position that each element of the final string is equivalent to in the original string (as you are doing) and just constructing the final string, because in both instances you are storing the equivalent of the final string's length in elements, which can be up to 10^5 * 2^40 (n duplicated c times) a.k.a: way too much.

So your guess is correct, the position array is getting too big.

Same for me :/

After the contest I continued to try and solve D and was surprisingly able to come up with a constructive solution that works, but it was hell to make. As a new expert who hasn't solved that many Ds before I was very pleased to read the editorial and realize that what I did wasn't the expected smart solution.

Here is my code (it isn't pretty, but I will never touch it again): 164362277

I believe you are mixing rating points with contest points. The -75 you are referring to is how much your rating changed after the contest. Rating changes are based on your overall performance/rank on the contests. Your performance/rank in contests with ICPC rules, such as this, are based first on how many problems you solved and then on how fast you solved them. An incorrect submission adds 10 minutes to how much time you took to solve a problem, what makes your performance worse, but doesn't quite directly influences your rating change like this. You could have had zero incorrect submissions and yet a negative rating change, because although you didn't get anything wrong you had a bad performance, or you could have had 100 incorrect submissions and yet a positive rating change, because you had a good performance.

Finally my first unrated round... (It is)