Similar names (⁠ᗒ⁠ᗩ⁠ᗕ⁠)

thanks aftors

Problem C is trash. Change my mind...

What're you talking about? Problem C is complete piece of sh*t.

as a tester, this was the best contest I have ever seen.

Hahaha as a tester I cannot say about that now, but good luck if you participate!

Haha nicely predicted.

I do agree

Same lol

Can you please tell your approach on C?

same

The contest isn't over yet.

no you need to solve A+B first

I thought of doing a segment dp like:

dp[L][R][0] — ans for [L; R]

dp[L][R][1] — ans for (L;R]

dp[L][R][2] — ans for [L;R)

dp[L][R][3] — ans for (L; R)

But had some troubles with calculating dp[L][R][0]. Other states are easy to calculate

Problem C was good and interesting? You have no taste, Bro

Me and Me... Also got TLE Btw, how to solve B? please help somebody...

it's me, huh! My final ratings will be negative. But next contest, i will gonna hit harder..

me ;(

You probably converted the number to string and left a leading zero on during the output (not converting it back to int). It would fail for 101, where you would output 01 and 100. Just my guess. You would have to delete all the leading zeroes instead of just the first one

include <bits/stdc++.h>

using namespace std;

int main(){ long long t; cin >> t; while(t--){ string str; cin >> str; int y = stoi(str); if(y%2==0){ cout << y/2 << " " << y/2 << endl; } else{

string a, b;
int cnt = 0;
for(int i=0; i<str.size(); i++){
    if((str[i]-'0')%2==0){
       a =  to_string((int(str[i]-'0')) / 2) + a;
       b = to_string((int(str[i]-'0'))/2)+b;
    }
    else{
       cnt++;
       if(cnt%2==0){
         a = to_string(int(str[i]-'0') / 2)+ a;
         b =to_string((int(str[i]-'0'))/2 + 1)+b;
       }
       else{
         a =to_string( (int(str[i]-'0'))/2 + 1)+a;
         b =to_string((int(str[i]-'0'))/2)+b;
       }
    }

}
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int q = stoi(a), w=stoi(b);
cout << q << " " << w << endl;

} } }  

see these patterns i hope this will help you
if n=6
1 12=13
2 10=12
3 8=11
4 11=15
5 9=14
6 7=13
so the ans is no.
if n=5
1 10=11
2 8=10
3 6=9
4 9=13
5 7=12
so the ans is yes

Distribute digit by digit.

Divide n into 2 numbers evenly. One number may be 1 greater than the other. Compare the 2 numbers digit by digit. The digits are either (1) same, (2) 1 vs 0, or (3) 0 vs 9. Keep track of the sum of digits of the 2 numbers so far. In case 3 above, distribute the 9 as 4 and 5 or 5 and 4 depending on the current difference of the sums of digits so far.

If n is even answer is n/2 n/2 else traverse n digit by digit and make answer

if the number is even then n/2,n/2 is the ans. if its odd then n/2,n/2+1; edge cases 1999,3999,599999 etc we can distribute it like eg for 3999 1545 2454

dp[i] = max(dp[i — 1], dp[j] — j + i) while sum(j + 1 ... i) >= 0 (j < i) using map to keep (sum[i], dp[i] — i) increase.

C is just bad, like B, just intuition is needed...

even though huge no of submissions

yeah me

Yes, i did the classic dp like LIS but get WA on test 5 don't know why

I was given some pattern in this comment you can see that

Approach for C

how to solve C

It's normal for a new account to solve only the first (or even zero) problem is the first contest. You just need to take more contests to get familar with the process of CF contests.

Observe that the answer is equal to the number of adjacent points which moves toward each other.

We may check every two points $$$x_l,x_r$$$ and count the number of subsets in which $$$x_l$$$ and $$$x_r$$$ are adjacent and move toward each other, which is equal to $$$2$$$ to the power of $$$(L_{l,r}+R_{l,r})$$$, where:

$$$L_{l,r}$$$ represents the number of points satisfying $$$x_r-x_l<x_l-x_p$$$;

$$$R_{l,r}$$$ represents the number of points satisfying $$$x_r-x_l\le x_p-x_r$$$.

for a fixed $$$l$$$, $$$f(i)=L_{l,i}$$$ is monotonic. Similar for $$$R$$$.

The code for the solution above is very easy to implement.

I didnt use DP. I just iterated over every pair $$$(i,j)$$$ and found the number of subsets of points such that $$$i$$$ and $$$j$$$ meet each other. The idea and code are both simple.

#include <atcoder/modint>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace atcoder;
using namespace __gnu_pbds;
using namespace std;
using mint = modint1000000007;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define endl '\n'
typedef vector<int> vi;

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int N;
  cin >> N;
  vi vec(N);
  for (int &i : vec)
    cin >> i;

  ordered_set<int> s;
  for (int i : vec)
    s.insert(i);

  mint ans = 0;
  mint two = 2;

  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      int d = vec[j] - vec[i];

      int t1 = s.order_of_key(vec[i] - d);
      int t2 = N - s.order_of_key(vec[j] + d);

      ans += two.pow(t1 + t2);
    }
  }

  cout << ans.val() << endl;

  return 0;
}

Can you please explain your dp approach for D . I tried doing this by dp but failed and my obervation skills suck , hence wasnt able to do the question the other way too.

Wouldn't this be $$$n^3$$$ ? Each of your $$$O(n^2)$$$ values take some $$$O(n)$$$ time unless there is a trick I am missing.

had a similar observation but could not come up with the implementation ;(

I have a simpler approach, iterate over i,j (i<j), for every i,j find out a,b such that a<=i,j<b and if every element between [a,b) is not present in a subsequence (except i,j) then $$$a_i$$$ moves towards $$$a_j$$$ and vice versa. Also, $$$b-a$$$ should be minimum so that we exclude minimum elements. Now add $$$2^{n-(b-a)}$$$ to the answer.

Code: 192957360

Let's assign directions to the dots in some subset, they will look like:

(RR...RRLL...LL)|(RR...RRLL...LL)|......|(RR...RRLL...LL)

So the number of distinct endpoints is the number of "LR" adjacent pairs + 1 (to account for the first block). So we can iterate on every pair $$$(i,j)$$$ and count in how many subsets they can exist as an adjacent LR pair.

Based on $$$x[j]-x[i]$$$, we can know how many dots before $$$i$$$ can be directly before $$$i$$$ in a subset and how many dots after $$$j$$$ can be directly after $$$j$$$ in a subset. If $$$[l, i-1]$$$ is the left range and $$$[j+1, r]$$$ is the right range, then the left subset counts can be $$$2^{l-1}$$$, $$$2^l$$$, ..., $$$2^{i-2}$$$, and the right subset counts can be $$$2^{n-r}$$$, $$$2^{n-r+1}$$$, ..., $$$2^{n-j-1}$$$.

So, add $$$(2^{l-1}+2^l+...+2^{i-2})\cdot (2^{n-r}+2^{n-r+1}+...+2^{n-j-1})$$$ to $$$ans$$$. Make sure to initiate $$$ans$$$ with $$$2^n-n-1$$$ to account for the first block in all the subsets.

Submission

you can solve B with binary search

if n%20==19 what should you do next?

Since the guy with more elo literally posted the same answer as mine and my comment is being ignored because of it, I might as well just remove it.

$$$B$$$ can be implemented simpler. Iterate over digits. If digit is even, split it equally for both answers. If digit $$$x$$$ is odd, add $$$x / 2$$$ to first answer, $$$x / 2 + 1$$$ to second answer and then swap them.

At the end remove leading zeros.

Example: 16934 -> 1**** + 0**** -> 13*** + 03*** -> 035** + 134** -> 1342* + 0351* -> 13422 + 03512

C is super easy to guess

Cheating is happening too much nowadays..

i guess it is for both B and C, B was much harder than c

I am also feeling this

I think , There were not much difference between level of B and C .

maybe 1999 3999 59999 ....etc any such

i think it could be 100,1000,10000 etc