Today's Internet is not smooth

When 3 divides 6 it changes N to N/k which is 2 and N-K,i.e., 2-3 is equal to -1 and not 1. :)

for k=3

n = 6

1> 6%3==0: n = 6/3=2

2> 2%3!=0: n = 2-3=-1

it's wrong

Hmm, everyone is pointing out wrongly... If you choose $$$K = 3$$$, performing one operation results in $$$2$$$, which is less than K, so you don't have to consider operations one more time :)

I solved E doing dpl[n + 1] and dpr[n + 1] — the max days we can work in 0...i for dpl and i...n dpr. So i will be in the answer if dp[i] + dp[n — i — 1] < k and dp[i] + dp[n — i — 1] + 1 == k and
s[i] == '0'.Sorry for my poor English.

Code:

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k, c;
    string s;
    cin >> n >> k >> c >> s;
    int dpl[n + 1], dpr[n + 1];
    dpl[0] = 0;
    dpr[0] = 0;
    int last = -10000000;
    for (int i = 1; i <= n; ++i) {
        if (s[i - 1] == 'x') dpl[i] = dpl[i - 1];
        else if (last + c < i) {
            last = i;
            dpl[i] = dpl[i - 1] + 1;
        }
        else dpl[i] = dpl[i - 1];
    }
    last = -10000000;
    for (int i = 1; i <= n; ++i) {
        if (s[n - i] == 'x') dpr[i] = dpr[i - 1];
        else if (last + c < i) {
            last = i;
            dpr[i] = dpr[i - 1] + 1;
        }
        else dpr[i] = dpr[i - 1];
    }
    //for (int i = 0; i <= n; ++i) cout << dpr[i] << " ";
    for (int i = 0; i < n; ++i) {
        int left = i;
        int right = n - i - 1;
        if (s[i] == 'o' && dpl[left] + dpr[right] < k && dpl[left] + dpr[right] + 1 >= k) cout << i + 1 << endl;
    }
    return 0;
}

You need an else block for when indices.size()!=1: In this case, the best strategy (i.e. causes the least forced days) is to work on the earliest day $$$d^*$$$ inside indices{}, because if a future day is forced when using $$$d^*$$$ then it is also forced for any other $$$d$$$ inside indices{}, but not necessarily the other way around. After you select $$$d^*$$$, you should increment the index appropriately.

For instance suppose you have 4 o's in a row, where the first and second have maxwork=2, and the third and fourth have maxwork=1. Then assume you work on the day with the first o. This might disqualify the 3rd o, making the 4th o forced. So you need a condition similar to your index=c+1+index1, except assuming you work on the earliest day $$$d^*$$$.

I think something like "oooxo" with k=2, c=2 should exhibit this problem- you'll have maxwork = 2, 2, 1, 1, etc.

Mine to compare (btw linear time with a stack instead of a set is possible) https://atcoder.jp/contests/abc161/submissions/11538625

Maybe the hardest thing to encounter

Can anyone check why this fails in one test case? https://atcoder.jp/contests/abc161/submissions/17260017

D is bruteforce recursion, and I feel F is also much easier this time.

D is not hard, just dfs.

With D a brute force works, just maintain the lunlun numbers as an array, and increment i times. That is fairly simple compared to F.

Submission

Solution to $$$F$$$:

If $$$N=2$$$, the answer is $$$1$$$.

Otherwise, let's define the function $$$f(x, y)$$$ like this:

bool f(long long x, long long y)
{
    while(x%y==0)
    {
        x/=y;
    }
    return x%y==1;
}

Now for all $$$i$$$ $$$(i>1)$$$ which is the factor of $$$N$$$, add $$$f(N, i)$$$. Let's define this sum as $$$S$$$, and the number of factors of (N-1) as $$$T$$$. The answer is $$$S + T$$$.

$$$n$$$ can be of the form $$$k^p$$$ or $$$k^p(km+1)$$$. So we can loop over $$$\sqrt{n}$$$ values to check such $$$k$$$. Here

https://stackoverflow.com/questions/2722302/can-compiler-optimization-introduce-bugs

it should be ceil(sum/(4.0*(double)m)). you are meant to round it up to fit the requirement

you are dividing sum by 4*m and both of them are int, so there division gave you a rounded down int. suppose sum/(4*m) is 96.5, your code will convert it to 96 and then include all the 96s in the array which shouldn't be include as 96<96.5 . use double while dividing and then use ceil function.

Line 23: if(v[i]>=sum/(4*m)), this does integer division as both sum and m are integers.

The correct way would have been to store it in a double and then compare.

Cast integers to doubles where you are doing division and comparison

Change if(v[i]>=sum/(4*m)) to if(4*m*v[i]>=sum) .

if i is a factor then n/i is also a factor.U missed to check for n/i in the first for loop.

You are printing twice when n=2

Can you explain please what dp[12][N][2][2] in your code means?

Wow, Thank you!

Same here. D was a bit tough for me while F was much easier. It took me 25 minutes to solve D with BS+digitdp and just 7 minutes in F.

Never mind, I figured it out. When the last digit is 9, the queue puts in a 0, bc (9 + 1) % 10 = 0

I solved it using bfs. Here is my solution

I used simple BFS.

int k;
   cin>>k;
   if(k<=12){
      cout<<k;
      return;
   }
   priority_queue<ll,vector<ll>,greater<ll>> pq;
   for(int i=1;i<=9;i++)
   pq.push(i);
   
   int cnt=0;
   ll ans;
   while(true){
      ll num=pq.top();
      pq.pop();
      cnt++;
      
      if(cnt==k){
         ans=num;
         break;
      }
      
      int ld=num%10;
      ll num1=num*10+ld;
      pq.push(num1);
      
      if(ld!=0){
         num1=num*10+ld-1;
         pq.push(num1);
      }
      if(ld!=9){
         num1=num*10+ld+1;
         pq.push(num1);
      }
   }
   cout<<ans;

I did it using simple bfs.

link to submission

You can solve with bruteforce, just store Lunlun numbers in an array.

Then check the last digit of i'th entry, let it be x. Then for next position, you can have digit -> x-1, x and x + 1.

For example: Initial array : [1, 2, 3, 4, 5, 6, 7, 8, 9]

Consider you are at 1 -> 10 , 11, 12. Then increase the pointer after you try all consecutive of current entry.

Now do same for 2-> 21, 22, 23.

and keep adding them in the array. You can implement it recursively as well as iteratively.

Iterative

BFS can solve the problem.

int n,cnt;
void solve(){
	cin>>n;
	queue<string> q;
	rep(i,1,10)q.push(to_string(i));
	while(1){
		int m = q.size();
		for(int i=0;i<m;i++){
			string s = q.front();
			q.pop();
			if(++cnt==n){
				cout<<s;
				return ; 
			}
			if(s.back()=='0')q.push(s+'0'),q.push(s+'1');
			else if(s.back()=='9')q.push(s+'8'),q.push(s+'9');
			else q.push(s+(char)(s.back()-1)),q.push(s+s.back()),q.push(s+(char)(s.back()+1));
		}
	}
}

Try making req into a double: double req=(double)(tot)/(4*m);

For small k and big n the loop will run n/k times, wich then is to slow. You can speed this up by using mod operations.

If you were to generate all numbers, it'd be something like this:

vector<long long> num;
void brute(int i, int last, long long cur){
    if(i == 0) return;
    num.push_back(cur);
    if(last > 0) brute(i-1, last-1, cur * 10 + last - 1);
    if(last < 9) brute(i-1, last+1, cur * 10 + last + 1);
    brute(i-1, last, cur * 10 + last);
}

Where $$$i$$$ is the maximum number of digits, $$$last$$$ is the last digit you used and $$$cur$$$ is your current number.

Then, you can use nth_element or sort to get $$$k-1$$$ smallest.

But why does this work? Well since there are only 3 transitions, complexity would be $$$O(3^D)$$$ where D is the maximum number of digits. Turns out answer will have not more than 12 digits so you can just brute force it =p.

You can approach that problem by using backtracking. Let's say you have a lunlun number x, you can find another lunlun number by taking the last digit of x which is d = (x%10) and appending d, d+1, d-1 to x. Then you keep doing the same on the new lun lun number. Also you have to keep in mind that initially you have start with all the single digit numbers. You can imagine the tree as 0 at the top and the root node, the from that emerges 9 branches to 1, 2, 3, 4, 5, 6, 7, 8, 9. Then from each one of them will emerge at most 3 branch. Like from 2 we will have 21, 22, 23. And so on.

Let's define dpl[i] as the max number of days that we can work in first i days, and define dpr[j] as the max number of days that we can work in last j day. The size of both arrays is n + 1. We can precalculate dpl and dpr greedy, base: dpl[0] = 0, dpr[0] = 0, last = -inf. Then iterate from left to right, keeping last as last day when he worked. Same for dpr.

If day i is in the answer, then s[i] == 'o'(Im counting days from 0 to n — 1) and dpl[i] + dpr[n — i — 1] < k and dpl[i] + dpr[n — i — 1] + 1 == k(may be its useless condition). Time complexy: O(n) Code:

https://atcoder.jp/contests/abc161/submissions/11534466

Or if someone just translates the existing one to English.

This problem can be solved efficiently using Queue.

Prepare one Queue and Enqueue 1, 2, ..., 9 in order. Then do the following K times:

• Dequeue the Queue. Let x be the extracted element.

• Let d = x mod 10.

• if d = 0. Enqueue 10x, 10x+1.

• if d = 9. Enqueue 10x + 8, 10x + 9;

• else Enqueue 10x + d-1, 10x + d, 10x + d + 1.

Kth extracted element will be the answer.

The same idea:

int n,cnt;
void solve(){
	cin>>n;
	queue<ll> q;
	rep(i,1,10)q.push(i);
	while(1){
		int m = q.size();
		for(int i=0;i<m;i++){
			ll s = q.front();
			q.pop();
			if(++cnt==n){
				cout<<s;
				return ; 
			}
			if(s%10==0)q.push(s*10),q.push(s*10+1);
			else if(s%10==9)q.push(s*10+8),q.push(s*10+9);
			else q.push(s*10+(s%10)-1),q.push(s*10+s%10),q.push(s*10+(s%10)+1);
		}
	}
}

https://mirror.codeforces.com/blog/entry/75551?#comment-597715 Great explanation ...

Find the earliest and latest day of the $$$i$$$-th working day. If for some $$$i$$$ they are the same, this is a day bound to work.

You can greedily iterate the days to find the earliest days. Also, reversely iterating the days gives the latest days.

use long long for i instead of int

if(a[i]>=(sum/(4*m)))

Instead of dividing on the right you better multiplicate on the left side, to avoid rounding issues.