Amazing and nifty tool to create your own infinite penchick race!

I think the following adjustments would make it more accurate:

1) filter to those who have participated in at least six contests, because otherwise their rating would be downwardly biased due to the CF base rating of 1400 being credited over six rounds, and

2) filter to those who joined at least once over the past six months

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

Looks like recent Div 2 demotions in the current contest are considered “out of contest” even if their rating is 2100 by the start of the contest. Any reason why?

https://mirror.codeforces.com/contestRegistrants/1934/page/2?order=BY_RATING_DESC

Atcoder is starting an hour later than the usual time this Sunday.

This is the start time of Atcoder (9PM Japan time, 1PM UTC): https://www.timeanddate.com/worldclock/fixedtime.html?iso=20230312T2100&p1=248

There appears to be a conflict with Atcoder Regular Contest 158. Pushing back the start of the round by 30 minutes will avoid the conflict.

Link to round: https://atcoder.jp/contests/arc158

I think current performance over time (as per cfpredictor) makes more sense

"I woke up today trying to log into Codeforces but the site was mister"

???

I'm curious what's test 2 here that's causing WA.

https://pastebin.com/41BJXM9H

I had a pattern-matching closed form

a, b = input().split()
a = int(a)
b = int(b)

if b == 1:
	print(a)
else:
	chopped_even = bin(b+1)[3:]
	len_even = len(chopped_even)
	best_even = ((a-int(chopped_even, 2))//(2**len_even))*2

	chopped_odd = bin(b)[2:]
	len_odd = len(chopped_odd)
	best_odd = ((a - b) // (2**len_odd))*2 + 1

	print(best_even if best_even > best_odd else best_odd)

Yeah, due to the dynamics of the round the faster you do A-E the more time you could put on F. But it's also not impossible to do F quickly if you see a bunch of clever stuff.

also this round is good for the majority of people (who normally solve the first two in a regular round then that's all). Here there's a better differentiation between a 1700 (who'll get 4-5) and a 1300 (who'll get 2-3). In many other rounds both the 1700 and the 1300 will get 2 problems and it's up to speed. So I think the speed aspect is much smaller here for most of the people, except for the tippy top.

imho F is an amazing problem. you could start with a really naive soution (that TLE's) then slowly prune the stuff you have to test.

[deleted]

Bronze right now is at 135.76 points; do you think appeals would change it significantly?

https://en.wikipedia.org/wiki/1972_Olympic_Men%27s_Basketball_Final

Simple solution for 90 points.

It's easy to see that at most 500 items are non-lollipops. So query the first min(n, 500) items to find at least one lollipop (this is the one with largest answer sum).

Then to locate all the non-lollipop boxes we could binary search prefixes; it takes at most 500*log_2(200K) ~ 8.5K. (you could save a bit, not sure how many by memoizing queries)

Afterwards just search each of the non-lollipop one by one for the diamond (there's at most 500 of them); the diamond is the one with both 0 result.

Whoops I made this error. At my initial code I checked only 450 boxes to find the minimal, as 450^2 > 2*10^5, but I forgot that this is not necessarily the only layer.

1, 2, 5, 26, 440, 199526 requires 473.

What are the chances of 144.99 reaching bronze cutoff?

I think that this was meant for Problem B. For Problem C, if you brute force through all possible number of items, the algorithm will become O(n^2) and thus TLE.

1500 rooms makes O((nm)^2) possible. In fact it allows O(2^n*m). Is there an intuitive yet slow solution that is worse than O(mn)?

I used DP on the minimum amount of time it takes to complete each row and ending in the . left staircase or the right staircase, but there are several annoying things to watch out for, namely the stopping floor (you don't need to continue the dp after this if there's no more lights at higher floors), and the case where there's only one floor.

Failed Test 64 :-(

http://mirror.codeforces.com/contest/796/submission/26274847

Why?

I agree that there is no ambiguity in the word "while". When solving the problem, I treated it as a while() loop, which means that when the condition is not obeyed, we stop.

The crux here is to notice that all we need is the sum of (signed) distances of the cokes that we include to our desired amount is zero.

Then do we something like Knapsack's DP, except we notice that an optimal solution could be arranged so that we never stray beyond [0, 1000], supposing that we start at the desired amount and then add/subtract the distances from there.

To make it run faster, we implement it using BFS (store the reachable ones in an array that indicated how many steps needed)

how about if the number (either the upper or the lower number) could be up to a billion?

i did casework based on the index of the last '(', and then got a binomial formula. My code is here: http://mirror.codeforces.com/contest/785/submission/25528358

does anyone know how to do the binomial thingies more elegantly, as these take quite a long time to implement. I tried checking others' solutions but I think that most didn't use explicit binomial formulas.

Problem C has funny test data.

I passed the pretests but got TLE-hacked. :-(

The algorithm I used is speed through the first m days, and then manually implement the rest. I barely passed the pretests with a 499ms running time, but then failed with a hack.

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

Add me please!

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

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

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

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

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

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

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

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

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

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

Isn't shortcut already of the third type?

anyone was able to calculate the averages?

Thanks for your clarification. I get it already!

Hmmm... how do you know for sure?

If you query 0S and answer is "YES", how are you sure that the suffix is 0S, or the 0S just appeared somewhere in front?

Please correct me if I'm wrong — as you can see, I'm just blue and you're red

To elaborate more: Suppose you have a 16-string, and you know that the longest consecutive sequence of zeroes is of length 3, and the suffix is 000101. Now we have to construct the first 10. Logically, we get that the last 7 are 1000101.

How do we construct the first 10, then? The first algo that comes to my mind is to check 01000101, and if this does not work, we assume that the last 8 are 11000101. The harder part, though, is if this works, i.e. 01000101 returns "YES". The problem here is that the 16-string 0100010111000101 also has the substring "01000101". Maybe the algo I'm thinking isn't the correct / the one that vlad8 had in mind, though.

Thanks for the clarification, but I still don't understand how to

"It just remains to extend our string on the left side".

how do you extend our string on the left side (given that we have the right side prefix).

For example, if we know that our last 450 characters (different example!) are 00..00 (150) and 11...11 (300). A natural way to figure out the 452th-to-the-last character is by testing 1100..00 [150] 11..11 [300]. But you don't know if this is referring to the last 452 characters or just another continguous substring of 452 characters that happen to be the same (not necessarily at the end).

At least, we reduced the problem to "given a 1000-length string with suffix x with length k, find the remaining 1000-k letters with around 1000-k moves (you don't have much allowance here, sadly, maybe give or take one or two)"

Essentially, I'm still confused on how to do the last step (after the two binary searches) — finding the remaining after knowing the suffix as well as the length of the longest string of consecutive zeroes.

The problem is that there is a roughly 1/4 chance for there to be a 000000000000 in S. (just a rough estimate)

and the judges would obviously guard against such a solution by using a trivial 00.000 testcase.

Yes, I agree that his solution will have a problem in this case.

Also, I don't find it clear how is this done:

"But that is simple, given that we know the number of characters needed."

Do you have an AC code for this? It'll really help. Thanks again!

Does anyone have the correct codes for this contest?

Thanks a lot!

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

How do we know that this greedy solution works?

How do you hack this?

I don't quite understand your explanation. Would you mind giving a code that does this?

Why do we have "xor of distinct elements from l to i is just query(l , i)"?

-

Help debug — https://ideone.com/oOKjFC. For "gap"

It says that it terminated with a nonzero exist code, which means that in one of my inputs, my s is larger than my t, but I don't see this happening...

Gah... cin and cout in Div 2 D

Well I guess lesson learned: Be wary if they put such an easy problem as a Div 2 D. It literally took me 3 minutes to think of. This means that there's a trap.

ROFL... https://en.wikipedia.org/wiki/Abdel_Fattah_el-Sisi

I think that it consistently gives lower ratings because it interprets newcomers as having "0" rating instead of "1500" rating.

Hahaha almost thought of convex hulls and stuff until I realized "hey could I find a pattern". and I noticed it was something like linear (clearly it must) and then I remembered of 90 and 270 degrees.

Basically if we have an n-gon composed of 90 degrees and 270 degrees suppose there are a 90 degrees and b 270 degrees. Total angle is 180(n-2). Then 90a+270b=180n-360... a+b=n. Solving we get b=(n-4)/2.

Yay

My solution is simply (N-4)/2. Consider 90 degree and 270 degree angles.

What's the scoring distribution for the division 2 contest?

Thanks for your answer! Your English is not bad at all!

Hmmm what's wrong here? It failed at the aaaaaaa... case, where the answer is the number of a's, but my answered was one less.

codeforces.com/contest/625/submission/15869860

hmmm I don't see what is wrong with the code here: http://mirror.codeforces.com/contest/615/submission/15249100

Hmmm what's wrong with the code here?

http://mirror.codeforces.com/contest/615/submission/15249100

How do I change my color if I already changed my handle? When I changed my handle I did not see any option to change color also

May I know when will the rating changes be shown?