Sharing one of my related answers in Quora

People are so impatient. I mean, you need to give them some time to announce that it is unrated. Who knows, probably they cannot still access the site : P

edit: there you go

My submitted code outputs correct answer in CF but wrong answer in my machine for this test case. I tried to hack some solutions using this TC but failed :v

How to solve F for greater K? I read about Yen's algorithm for single source K-th shortest path. But this one is different.

Someone really wants to get their opinions established in D2

Binary search will not work for this problem. Try this testcase:

5 2

1 4 5 7 8

Correct ans is 4 by partitioning in the following: [1][4 5 7 8]

D was not that difficult. If you can brute force, you will easily find the pattern.

However, if you are talking about clarity in problem specification, I agree 100%

Tried some things with pen and paper, observed the pattern, coded a brute force solution and observation proved valid for all n upto 20. So, went for it : P

You can repeat the pattern 0000...001 over and over up to n length.

The number of zeros in the repeating pattern is (n-k)/2.

I am actually surprised why there has not been more solves. Makes me doubt the solution

After reading B:

Me: OK, randomized algo should work

Inner Me: But there's a possibility it will fail

Me: Very low though

Inner Me: So, you are saying you never had something happened to you that was totally unexpected?

Me: Ok Ok. I will write a dp solution.

Conclusion: Got Hacked 2 minutes before the end of the contest. Then resubmitted a randomized solution anyway because there was not enough time for debugging

for each number g you have to find 3 things:

a = how many numbers are relatively prime to g within range [1,m]

b = how many numbers will have gcd g again when paired with g within range [1,m]

c = how many numbers have gcd<g when paired with g. (This was the hardest part for me in this problem)

The rest is calculating E(g) with a bit of knowledge of probability

My code: 51649595

If its ok to discuss problems now, has anyone else faced WA on pretest 23 for problem E? I can't seem to figure out what might go wrong with the logic.

Upd: Never mind that, silliest implementation mistake. Really worth my handle name.

1741->1672

As you can see, 1 year wasted successfully.

Oh Damn! I really forgot all my maths. Thanks for clarifying.

The test case 2 of D is killing me for past 1 hour. For some reason, I can't seem to figure it out (in fact n=6, k=3 provides me with the given output). However, as there has been nobody raising that issue, the only explanation is that I have forgotten all my maths.

I cannot figure out how to make the Havel-Hakimi algorithm faster. How can I sort the degree sequences after each update operation if I use segment tree?

Thank you very much for that test case. I also made that assumption but there was no way of figuring that out from test case 4.

How to solve D?

I assumed that it is optimal to delete only one type of character. Is this assumption incorrect?

There is no need for graph. Using 1 as the first number, find the first 3 numbers with brute force. Then its easy implementation.

In case of such a scenario, I swapped Alice and Bob's info and performed my calculation in the same way. So, I think I handled that.

any idea what pretest 5 of C might be?

Instead of calculating power, I just checked how many numbers are divisible by for all numbers > gcd

Did something like sieve. Only marginally avoided TLE. Wonder what will happen after systest.

Wasted 1 hour trying to solve a harder version of Problem C. I thought classy numbers were those number which had the number of distinct non zero digits <= 3. And when TC 2 and 3 were not passing, I tried so hard debugging.

After successfully wasting 1 hour, read the question again and BAM!!

Problem A passes with randomized solution. Hunch paid off My Code

after this or after after this comment, new reply thread won't be created anymore

whoa, I totally didn't notice that numbers were given in increasing order. I overkilled my solution :')

exactly the same typo for me, too. So I wasn't the only one who failed systest with bruteforce solution

Saw some guy giving the exact same suggestion some months ago and getting some umpty number of downvotes

I know it could be simpler.... actually my approach was "this couldn't be any harder/dumber"

True.... Didn't realize some rotation produces equivalent results.

Aha, sorry for that..... Totally forgot the contest is still ongoing after that unrated announcement

Though I doubt there is another dull-headed guy like me who is gonna try writing these whole thing :v

When you don't want to spend time thinking what happens after rotating a cube and instead spend more time doing this: -_-

Server is enjoying Eid holiday

I think so. This problem was also solved by many using randomized algorithm. However, the editorial came out and I found out there was a deterministic solution. I was quite impressed. The belief that contest problems did not intend randomized algorithm was still intact.

I was also wondering what the deterministic solution could be for this problem and I must say I am somewhat disappointed :/ I found the randomized algorithm for this problem quite early but there was always a chance for this failing so I did not submit

problem D of good bye 2016

706E (only problem I found throughout my contest life which could be solved with linked list)

Expectation(node){
   E = 0.0;
   d = 1.0/number_of_children
   for each v in node.children:
      E+= (d)*(1+Expectation(v));
   return E
}

I haven't watched it but read the whole plot of this season and now I am giving away free spoilers to people who watch it :v

you can't say only 2-3 :v your rate is (77-55)/60s which is less than (2)/2s So I am ahead of you in observing this phenomenon 8-)

Do red coders use some kind of script for hacking or something?

One refresh in my status page shows 2-3 hacks by halyavin

(please tell me your secret :v )

be a grandmaster first then open a new account and participate in div2 contest. You will be quite surprised yourself to see your performance

Usually in this type of statements, I see that the phrase "All thingys have distinct co-ordinates" is given in such cases. Like in problem F, you are told that there is no road that connects a city to itself. So if you see no such statement, you usually take the worst case interpretation. So from my point of view, I don't think there was anything wrong with the statement

some guy just opened an account and solved all 6 problems .... (I think this is a hattrick if memory serves me right) -_-

At this rate, there will be fewer div2 coders than div1 coders

how is it that so many times some unrated guy takes one of the first few places? Don't div 1 coders get tired of creating accounts? Or is it really that genius people are being born nowadays at such a high frequency :v (in which case perhaps we don't need to worry about getting conquered by robots)

I missed -121 and -179 in the past two contests :v I might be the luckiest person in codeforces right now :v

(On the other hand, these two round has given me a valuable lesson. From next round I am going to start from A instead of C/D :v )

If you use all 26 letters the complexity will be 26^4*O(*(a+b)) with some more constant

I used a complete search technique that avoids checking everything case by case. I wrote a blog about it. You can take a look at this http://codeforces.me/blog/entry/52951

a->abc b->d then a will add aef because he sees the suffix as bcd.

if you think it like this....

a->"abc"|b->"b"|a->"ade"|b->"e"|a->"abc"|b->"c".......

then there are 4 distinct characters between position 4 and 10

KAN, I wrote a blog explaining my approach. You may check it to see if it can be proved valid.

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

We posted about some potential problem for judge data of C with the test case. Then it got deleted. So we think it really does have some problem

could you please see the testcase I have given? I had a hectic day and I may be wrong :v please let me know :v I need to know i haven't lost my mind totally

adedalic Does the dataset of C has some kind of problem? My AC code performs the following: input: 4 2 11 21 output: 6

but it can be 5. The string could be like this: abcdddabefeeabcdddabef........

from 11 to 21 we can have only 5 distinct letters.

Please see to this if I have misunderstood something......

(I skipped my first code because I found this test case and submitted a new one... now I see my skipped code gets AC. This is the greatest irony)

are you talking about using ternary search to find the rectangle with maximum area? I tried it at first , but I don't think maximum area here will maximize the result

round unrated

Here's the approach Link Try to prove it yourself first. It will be fun.

Consider cases where adjacent numbers are even,even; odd,odd; even,odd; odd,even and see how the operation affects them.

how to approach D?

Unless gcd is already greater than 1, yes this is always minimal. Because by the operation mentioned in the problem, you can never introduce a new odd factor which wasn't present previously in the array (you can easily prove this by setting a-b=k*n1 and a+b=k*n2 where k is odd , figure out how n1 or n2 will look like). The best you can do is introduce an even factor, namely 2

In div2C, I think the max answer can be at most around 10^10... The max answer will be generated by a case like:

100000 99999

1 100000

1 100000

........

........

1 100000

Could you verify?

I think it should be around max(n)*max(initial_power). I dont have a proof but I generated some test cases and they gave me this idea

undoubtedly today's best performer

So, I assume you used 0-based indexing when you said that?

not needed ... keep the last string as it is... then greedily check the max prefix you can keep from bottom to top

to calculate number of ways to split the substring(l,r) you have to choose the leftmost splitter i starting from l until it violates the conditions mentioned or reach r. after choosing leftmost splitter i you have to find number of ways to split substring (i+1,r) and add it with the result

You went to my account? o.O

I understood the cycle part during contest... however didn't get the part about even number of 1's ... please explain why even number of 1 won't work

So I was trying to access the problem for practice and suddenly this happened. Some kind of bug or hidden feature? o.O

Yes, thank you. I was not confused about what I had to print as my answer. It was just a stupid typecasting error.... And after seeing the test, I thought without counting the number of zeroes, that this number is greater than 10^18. I came back as soon as I realized my stupidity to delete the comment , but you had already replied :v Thanks anyway.

Did you understand test 100? o.O It didn't made sense to me.

ok, can someone explain test 100 to me for problem D? 2 10000000000000000000000000

Answer: 33554432

But how? As I see it, there is only one possible way to write this number in base 2 :O o.O

Plz someone explain

I did some calculation with double to check overflow... Maybe I got caught in there for some tricky case.

Well, I got caught in test 100 :v :v So ignore me :v

I kept a double counterpart to detect overflow....

beginning of j-th part can be used to uniquely identify the base power... I think your states are redundant

I passed with dp solution. You may have a problem with the 0's

2 if you involve binary search (provided you have a fast net too) :v

Wouldn't that output just the occurence of a particular number in the segment? But I thought he asked for the maximum frequency of all possible numbers in that segment..

There's a guy at the end of this video. And the voice sounded exactly similar like this :v

Jeez, Thanks man... Thats some observation

log(10^7)*log(10^7)*n is getting AC. However, I had to do a little optimization like getting rid of long long .

could you explain this part of your code?

fr(n) {
            int p = 1, j;
            for (j = m; j <= a[i]; j *= 2) {
                p *= 2;
            }
            c += max(p / 2, p - j + a[i]);
        }

i know here you are finding for each tangerine how many people can get an amount m. I had to spend almost 3 hours to figure out an appropriate way to do this. Check my submission 23315399 (the howmany(wholesize,piece) function). I knew there must be a more concise approach to calculate this.

anyone else solved div2 A using bigmod? :v

Wow!! Cool name

let n=max(a,b,c)

now depending on his arrival and leave time, there can be seven possiblities for number of breakfast, dinner and supper available. they are:

b=n,d=n,s=n b=n,d=n,s=n-1 b=n,d=n-1,s=n b=n-1,d=n,s=n b=n,d=n-1,s=n-1 b=n-1,d=n,s=n-1 b=n-1,d=n-1,s=n

for each of these cases , find the minimum number of foods he can miss

I initialized ans=-1 :'(

"current incorrect version of problem E?" You mean E has problems too? o.O

I have a confusion. Isn't dp[011] also not dependent on dp[101]? you have 3rd and 1st video in the cache and then 3rd video is removed by the second video if second one is called? I am sorry I know I probably dont understand the state transitions clearly. Could you clear that up for me?

I just want to make something sure about problem E. a)Swapping two rectangles like the red and green one is not allowed, right?

b)And if such an operation were allowed, would there be an efficient method to solve this problem?

update: solved it. So, I am clear about (a). So if anyone could tell me about (b)...

well try to upsolve the rest 3 as well. It won't help unless you gradually develop some new techniques, will it ? :/

you mean you get fun by solving 0 problem?

tweety himself was producing a very nice sine curve, but he just had to break it :v

I followed exactly your method and managed to pass pretests. Must be some small bug in your code. And I think my solution may also fail in main test. I can't shake off the feeling I missed some corner case :/

I managed to pass pretest with union find — disjoint set.... but I think there may be some corner cases that I haven't handled

"we made some new problems to complete the set to fulfill the requirements of the regular round"

"the requirements of the regular round"

"regular round"

(there, tried to make that as dramatic as possible)

Wow!! You made all three of them Headquarters. Mike has got competitions