How to get (> 10) points on problem A?

I have a feature idea (Not related to Chat-GPT)

I was giving virtuals for a few weeks now. Around 25% of the contests, I face some problems which I have mind-solved before or maybe read it. It's very frustrating when it is one of the hard ones.

So maybe some marker, which would help to mark the problems as mind-solved or read? It would also be very useful to avoid problems while practicing.

It can be solved using greedy.

Claim 1: It is optimal to use the computer as soon as we can.

Claim 2: It is not optimal to just let a contestant sit idly. Our priority would be to minimize this as much as possible after ensuring the first claim.

Let's say, some contestant just finished solving some task using the computer at $$$X$$$ time unit. Now find the minimum $$$i$$$, such that some contestant can finish solving a problem at $$$(X+i)$$$ time unit using the computer. If you can't find any, no more problems can be solved.

Also, define $$$F_j$$$ = the time unit when $$$j$$$ th contestant gets free

There could be more than one contestant, who can finish solving a problem at $$$(X+i)$$$ time unit. Among them, we pick someone such that his idleness period is minimized. More formally, among them, $$$j$$$ th contestant,

$$$~~~~~~~~~~G_j=X+i-F_j-\text{time required to solve the problem}$$$

Pick the contestant with minimum $$$G_j$$$.

If again, more than one contestant has the same $$$G_j$$$ pick the one who has the minimum $$$F_j$$$.

I don't know if there is such a magic number. CF rewards fast-solving highly, which I think helped lot in acquiring subtasks quickly. In the case of problem-solving ability, from my experience ~1800-1900 should be more than enough. You just need a good strategy and a good day.

I would like to share two wonderful underrated blogs written by E869120. Without that, probably I wouldn't able to get silver :)

In this blog, he discussed about the strategies which I think played the most important role. Regarding skill, he mentioned it's (should) enough to be around the purple-yellow range to get a silver.

About improving skills on codeforces, there is another blog by him.

For further practicing OI problems, OI Checklist probably has the best collection of problems.

Codeforces Version of the Discord Nitro Scam.

I solved it with randomization.

The key idea was to use the same seed while using mt19937 function for both encode and decode.

For N = 3, we need to send two bits, let's call them b1 and b2 respectively.

We will send a boolean vector sized 250, each of the indexes could represent one of the following things:

1. it could be b1
2. it could be b2
3. it could be some random bit

vector < ll > v(250, -1);
    vector < ll > b1, b2;
    mt19937 rng(K);
    for(ll i = 0; i < 250; i++){
        if(rng()%3 == 1 && (!i || v[i - 1] == -1) ){
            mx--;
            v[i] = rng()%2;  // random bits
        }else{
            if(rng()%2) b1.pb(i);
            else b2.pb(i);
        }
    }
    for(auto u : b1) v[u] = (1 << 0) & X;
    for(auto u : b2) v[u] = (X >> 1) & 1;
    for(auto u : v) send(u);

We could simulate the same while decoding. So while decoding,

If i_th number is a random bit, we would know what is the actual value of that bit and what we recieved. If they differ, then we would know for sure that i-1 th & i+1 th number is exactly what we sent (Those indexes would represent b1 or b2).

So, if the number of changes while sending the bits are frequent then we can easily figure out X.

Otherwise, we can assume the most of the bits we sent have sent aren't changed that much. So in this case, we can naively depend on the occcurences of 0 or 1 in the indexes of b1 for figuring out first bit, and the same for the 2nd one.

Full code: https://ideone.com/diqCci

I missed the part where the function is convex :( Nevertheless thanks a lot!

How to solve day2 problem 3?

Sorry, missed a condition while adding the edges. Now it should make sense.

(Condition wouldn't have mattered for the answer but it should help to get a perspective)

First, we can do casework for the answers 0 or 1.

Otherwise, We will use binary lifting until we are on an event $$$i$$$ such that, $$$R_s \lt L_i$$$, and if we move one more edge this condition would be broken. Let's say we have moved $$$k$$$ edges using the Binary Lifting.

From such $$$i$$$, if we move another time to its left (using the directed edge). We should come to the event $$$x$$$ such that, $$$L_x \lt = R_s \lt = R_x$$$. If we can't move or don't get such event $$$x$$$, then there is no answer. Otherwise, our answer would be $$$k + 2$$$.

The key is to iterate from the $$$e$$$ to $$$s$$$.

Let's say you are on the event $$$i$$$, you could have joined the event $$$i$$$ from any event $$$j'$$$ such that $$$L_i \lt = R_{j'} \lt = R_i$$$. Let's say among all such $$$j'$$$, $$$j$$$ has the smallest $$$L_j$$$. We will add an edge from $$$i$$$ to $$$j$$$ if $$$L_j \lt L_i$$$.

I suppose with this graph, the rest is pretty straightforward binary-lifting with one or two casework.

They already did, https://contest.boi2022.uni-luebeck.de/ranking/

Yeah, I am sorry. Fixed

Team Bangladesh hasn't been confirmed, yet someone added me to the list. Can you remove it?

I also used to face the following problem. To overcome, first, I worked on my typing speed on Keybr. Then whenever I tried to implement a problem, I gave myself some time (depending on the size of implementation) to think how to code from beginning to end, each process (literally everything), how am I going to implement. After that, it was a just a matter of fast-typing as I already know, what I am going to do exactly. I don't know exactly what is causing you this problems, but for me it gave a drastic improvement in case of implementing! Hope it helps!

Wow! The solution for C is really cool! I got a kinda brute-force solution in O(2^log10(n)). Fixing which digits are going to add in such way that, it would create a carry. Then just checking how many pairs satisfy that kind of fix carried addition. Here is my submission link Link !

Yeah, Sad :(

Can you explain your sliding-window method? What constant subarray size are you taking?

Well, I didn't enjoy most of the story of Mondstadt (first part) and yes, the game was kind of boring till AR 25. But once you passed that, not only the story gets interesting but also you can focus on certain things like character building, elemental reactions, fighting different bosses, and clearing domains. And I don't like anime that much, so anime characters were never been an attraction for me. As a f2p, the game has treated quite well. But in the end, it all comes down to the taste, but I could recommend playing like till AR25.

Genshin Impact. It's a really cool game, I think you can give it a try.

As far as I know, they don't use this kinda stuffs. I am contacting them, as soon as they reach me, they would reply to you in this comment!

Edit: They didn't save their codes, so they can't get access to them right now. After this session's USACO problem page opens, they would get the codes. Moreover sorry for the misinformation, one of my friends got all ac by doing Dijkstra, but the other two got 12 test-cases out of 13.

For Problem 2, my friends qwerty190 osmium Freaksus got AC by doing Dijkstra, even there were n^2 edges. I am so confused why those solutions got passed.

Well, I didn't mean to memorize a solution. I meant to feel it. If you can feel a solution by heart, you will never forget i. If you can't apply the idea to some other problem, that means you never felt the idea you used in the first place.

P.S: Memorization is one of the things I hate the most.

If you can solve a problem by yourself, try to never forget the idea you used to solve that. Overwise if you can't solve a problem, look through the editorial or some other's solution, try to feel the solution. So that in the future when you are encountering a similiar problem, you can think like the author did in that other problem :D

No. Don't focus on Algorithms, focus on improving the thinking skill.

competitive programmer's handbook is recommended! By the way, I would suggest solving problems rather than reading too much books :D

It was a tragic year for so many people. But for doing CP, I guess it is the best year so far. Show me a better year for doing CP than 2020 :Thinking:

I think everyone had a period when they did a lot of silly mistakes. Well, I don't think the rate of making silly mistakes would ever be zero. The best you can do is learn from them, just try to remember the case where you did a silly mistake. So, whenever you are facing the same type of case again, you can recover from it quickly with your past experience. I hope this helps :D

I am not talking about the difficulty parameters of div3. I am talking about the fact you mentioned: "You can't look through the internet during the contest". There is no rule against using google/prewritten code in codeforces. You may even consider "googling" a special skill for CP :D

Who has forbidden you to look on the internet? During the contest?

Will any type of editorial would be given for the qualification rounds? If yes, where we may get it?

I just got a mail from the email I used to participate in the qualification round 1. Should I have to sign up again? I am a bit confused.

I see

Can you explain the Dijkstra solution? I used 2 pointers to solve it. But now, after hearing it can be solved by Dijkstra, I am really curious to know the Dijkstra solution :D

Thanks a lot! Your solution gave me a new way of thinking :D

Is it okay, if we discuss the problem of day-1 now? If yes, then can anyone please explain the solution of E for 100?

Thanks a lot for your concern :D

I can't enter the webpage.

The low scores for problems B-C-D-E-F-G should not suggest that they are easier than usual.

If it doesn't mean B-C-D-E-F-G will be easier, then why the score distribution is like this? Someone could solve A, C, D, and most probably would be behind a guy who only solved A, B, C. Here B & D are playing the deciding factor. How even this is fair if B & D has a normal round's difficulty? I am sorry, but I couldn't get the explanation for the unusual distribution.

How to solve E :|

I see! It's really nice! Thanks!

May I know how did you calculate the expected rank? It would be great if you share the formula or some generator for that!

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

Oooh... I see that fact! Now everything makes sense! Thank a lot for the explanation!

The example of (you,red) and (you,purple×10) does makes sense. But I can't figure out the fact of the expected place. In that div2 round about 600 purple registered for the contest, obviously all of them didn't participate, still, if we consider all of them did then my rank is expected to be in the top 600? And in that div1 round, I should be in the last 75 as my rating, but I placed higher than my expected place! So if we think about the expected place, then shouldn't I get a negative delta on the div2 and a positive delta in the div1?

I can't find a difference between today's F and 1188 — Fast Queries . Really disappointed with today's contest :(

For n= 32, here is a picture

My approach to A goes like this, first initialize ans = n, now answer would be the smallest number between 1 and n-1, which returns 1. Now let's set a cursor named cur. Which starts in some position (let's name it x). Now we will do a binary search on [1,n-1]. If in the ith step, we do cur = cur+mid, then in the next step we will do cur = cur-mid and vice-versa. This will surely lead us to the answer. Now the fact comes, what if cur cross the bound! So we need to choose the position x cleverly. It's not hard to understand the fact that the bigger the value of C is, the bigger the moves are. So the worst case is C=N. Now we can simulate this case with a binary search to choose the position x for cur. The interesting fact about this approach is mid becomes too large or too small to intersect with previous queries! I hope this clears the doubt!

If you look carefully in my code. I have not used priority queue! I just declared it as I was trying different methods. I tried 2-3 times with priority_queue before this and seems like implementing with it kinda impossible for me! To find the right sub-sequence, I am taking a number fully, (like if there is 3 1's, I will take all the three), then let's say before the first 1, there was 2 zeroes. So I will take them too. Now If all the 2's exists after the last 1, I will continue to the two and will take a prefix = ( 3 (one) + 2 (zero's before one) ). If not then I will take the number of 2 after the last 1 as suffix! And will move to two as 0 prefix. If get clear on this part, it would become really easy for you to do the rest!

Anytime Bro!

I never said we need to take the LIS. We need to take fulled connected increasing sub-sequence! In your case we if we sort the array, it would be [ 0 1 2 3 ] and the original array is [ 0 2 1 3 ]. We have take a the maximum sized subarray from the sorted array which also have to be a sub-sequence of the main array. We can't take [0 2 3] as it isn't a sub-array of the sorted array. We can take [0 1] or [2,3] ! Hope this helps you to clear the fact!

Let's say we have an array [3,10,10,1,3,7,7,0] . We can map it to [3,5,5,2,3,4,4,1] so the coding part become easier. Now let's sort it [1,2,3,3,4,4,5,5]. Now we need to find the longest sub-sequence in the original array, which is also a sub-array for the the sorted array (If you subtract it's length from n, you will get the answer) . You can see here a interesting fact that [3,5] or [2,3,4,4] can't be a answer because it is a sub-sequence for the original array but not a sub array for the original one. So it's clear that there there has to be body , prefix, suffix . Body has to contain all the all element fully (It means if there are 5 4's , it has to contain all the 5 4's.) and prefix would be the maximum you can take legally before body's first element (simply the amount of (body's first element)-1 equals element before the body starts) and suffix would be the maximum you can take after body's last element(simply the amount of (body's last element)+1 equals element after the body ends). This is the basic idea. But there is a case, you also need to focus on. You need to check all the possible sub-sequences containing only two different elements. I got AC doing this 84144777. Please let me know, if you have any further doubts. Happy Coding :D

I actually got a idea by myself and it took 5 WA to get the AC. Thanks a lot for the help and sorry I thought first to try my idea then yours.As It took me 28 hours to get AC, so I was late in reply.

The part of idea is clear for me. Can you please explain a bit about the implementation? I am finding it hard to understand.

If you observe carefully, you will see there will be some cycles forming of same size. So we will check each size possible of the necklace. let's say we want to check if necklace size of x is possible or not. Let's say g = gcd(x, k). After g beards in the necklace, the letter has to be the same. So there will be g cycles. x sized necklace will consist g cycles of (x/g) size. Now we need to check if we can get g cycles of (x/g) size. This gcd idea can be a bit hazy, if you are finding it hard to understand, I will highly recommend you to draw some pictures and the thing... It really helps get a concept clearly :D And then let me know if you have further doubts. Happy Coding :D

I believe I have a really nice solution (as well as clean) for the problem E -> 84022899

You can see that I got the expert tag from a newbie tag in just 2 months. I believe the thing helped me a lot is to try to solve a problem by my own idea then look at the editorial and see how others solve the problem.. I spent time until I can feel their idea in my heart. Interesting fact is now I can think a lot deeper and getting more solution approach than 2 months past me [ Sometimes I can't believe that I didn't a idea for a simple problem two months ago]. I hope this way of learning could you to think deeper and to get variety ideas :)

Maybe you are right, it would super hard for me to be in the top 1000. I am still a beginner, I need to improve myself a lot. If I don't do different types of contest, how would I improve! I would definitely going to aim the top 1000, so that I can do my best and most importantly improve myself!

Oooh... I understood the fact.

I am agreeing for some people there performance improves if they solve some problems before a contest but there is also another type of people who prefers a cool mind before a contest.So if the contest is rescheduled, then both type of would get the chance to prepare themselves to the fullest as well as participating in this round...

Google jam round 2 is just after this round. 4500 participates has qualified for this code jam round and most of them wouldn't prefer to give two contests in a row... So wouldn't it be great if the contest is rescheduled to 18th May? So that more people could participate.

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

500 — 1000 — 1500 — 2000 — 2500 — 3000
After a long time, the score distribution is an arithmetic sequence! Really looking forward to this round!

I got it! Thanks a lot!

What if 7 3 3 4 4 4 4 4 . If I am not wrong according to your algorithm, the answer should be: 1 2 1 2 1 2 1 . But here t[n] is not equal to t[1] and they are also adjacent, then how they got same the colors?

Thanks

I am new in programming.Can you give me link of tutorial of this?