LSTBTF - Editorial

editorial
, , , ,
53

Is my thinking procedure right? @ssjgz

54

I haven’t looked at it in detail, but I suspect (as you say) that increasing the maximum difference will suffice :slight_smile:

1 Like
55

solution updated in the original post!

1 Like
56

While I’m here, I might as well re-post mine: I was going to add an informal analysis of the expected runtime and maybe a proof that there are no N such that no N-digit numbers are beautiful, but got bored and gave up XD There’s some skeletal notes in there, as well as a few interesting factoids about some of the Worst Cases we’ll encounter for 1 \le N \le 1000000, which is how I came up with that counter-example :slight_smile: Heavily-documented code, as always :wink:

https://www.codechef.com/viewsolution/27867132

1 Like
57

I suggest you open a new thread and post all of your solutions there, It hard to keep track otherwise.
Your “heavily documented code” helps us a lot. :grin:

2 Likes
58

I’ve already dumped them all here - no need for a new thread :slight_smile:

3 Likes
59

I don’t think that these constraints allow some really bad solutions to pass, so for me, it’s OK.
The main reason why I put such a constraint into a problem is that I don’t know to want to do this task impossible for some languages (I don’t know whether sth like python will be ok to output 1e7 characters in 2 seconds). Maybe it could be done with sth like “output number of 1, number of 2, and so on in optimal answer”, but I don’t think that this way the problem becomes more interesting.
As I see, basically any solution with normal complexity passed, and those which have bad one can be easily fixed to put into TLE (if the idea behind them is correct).
Also, it is easy to prove (by construction) that the answer is never -1 for any positive integer N.
About adding testcase, I am not so familiar with that on codechef.

3 Likes
60

Solve this with similar DP. My proof: #include <bits/stdc++.h>using namespace std; typedef long long LL;typede - Pastebin.com

62

Why am i getting wrong answer as i have used same approach as yours…
solution - CodeChef: Practical coding for everyone

63

AC: CodeChef: Practical coding for everyone
add this: sume=0;

1 Like
64

oooh i was missing tht … my bad btw thanks for your reply

1 Like
65

Since the solution is allways a relatively small number the simple brute force greedy solution works.

I implemented it after did not getting the dp solutions right… one can see the fragments in my code.
https://www.codechef.com/viewsolution/27683718

66

@watcher, how did you observe that max value of cntDigits will be 27. Please shed some light

1 Like
67

You can just try every value of N up to 1’000’000, and keep track of the highest, like I did :slight_smile:

1 Like
68

I have done exactly same

69

What a way to avoid plagiarism. Copy someone’s code, introduce unnecessary variables like sid, momo, chale_chalo and you are done.

3 Likes
70

what is sid & momo tho…?

71

bro my idea is similar to yours and a used the fact that maximum count of digit 2-8 are 5
but why is my code partially correct CodeChef: Practical coding for everyone
when i precalculate 5 digits but when i precalculate upto 6 digits that its getting accepted see CodeChef: Practical coding for everyone

72

This solution fails on the testcase:

1
957520

Edit:

Actually, both of your solutions do - weak testcases causes the latter to get AC, I suppose :slight_smile:

74

oh thanks actually this is not my solution i was just going through the successful submissions and i wanted to find the idea behind this one (cause it looked simple XD),
and i tweaked it a little bit , is this one CodeChef: Practical coding for everyone getting correct??, this is the original one