include <bits/stdc++.h>

7 дней назад, # |

← Rev. 2 →

Can anyone tell me what's wrong with my solution for problem D? 267065372. It's a simple brute force solution but I still got WA on test case 2.

→ Ответить

htoshiro

7 дней назад, # ^ |

64-bit integer i assume

→ Ответить

7 дней назад, # ^ |

Are you saying that the default 32 bit int isn't big enough? If so: I resubmitted and replaced everything with long long, and it got the same WA. So the error is for another reason.

→ Ответить

cuIver0412

7 дней назад, # ^ |

-15

your code is wrong

→ Ответить

7 дней назад, # ^ |

Could you be more specific? I know that the code is wrong, but I'm trying to find where I made an error.

→ Ответить

kl0989e

7 дней назад, # ^ |

else { // not at edge, ops is less than 2
    int first = s[0] - '0';
    int last = s[s.length() - 1] - '0';
    cout << first * last << "\n";
    printed = true;
    break;
}

I think this is what causes WA, in this case n=3 and s[1]='0', so there are 4 total variants: if string s='a0b', then the variants are 10*a+c, a+c, 10*a*c, a*c. You always chose variant a*c, but if for example s=303, then your code outputs 9, but the correct answer is 6 (a+c).

→ Ответить

https://mirror.codeforces.com/contest/1986/submission/267087342

7 дней назад, # ^ |

Ah, you're totally right. Thank you for catching this!

→ Ответить

kl0989e

7 дней назад, # ^ |

You're welcome

→ Ответить

ryanbear1434

7 дней назад, # |

← Rev. 2 →

for problem A you can brute force it

→ Ответить

udta_kouwa

7 дней назад, # |

-26

E was awesome!!

→ Ответить

acodebreaker

7 дней назад, # |

why does my submission give TLE on test 3 , for problem B

→ Ответить

Abhinav_0806

7 дней назад, # ^ |

pass the matrix by reference instead of value

→ Ответить

manikiran949

7 дней назад, # ^ |

bool testCondition(vector<vector>matrix, int i, int j, int n, int m)

Use pass by reference here,

bool testCondition(vector<vector>&matrix, int i, int j, int n, int m).

→ Ответить

acodebreaker

7 дней назад, # ^ |

thanks , as a Java user i didnot checked that haha

→ Ответить

baroza

7 дней назад, # ^ |

I think the problem is that you are passing the $$$matrix$$$ array to $$$testCondition()$$$ by value, which creates a whole new $$$matrix$$$ object. What you need to do is pass it by reference, using the & operator

→ Ответить

LucasCGar

7 дней назад, # ^ |

← Rev. 2 →

Hey, every time you run testCondition() you end up copying over the entire matrix, which is slow. To avoid this you can do place a & before the matrix, so instead of passing over the entire matrix, you're just passing over the pointer to it. This changes your function from

bool testCondition(vector<vector<int>> matrix, int i, int j, int n, int m)

bool testCondition(vector<vector<int>> &matrix, int i, int j, int n, int m)

Submitted and it worked 267088502

→ Ответить

rumike

7 дней назад, # |

← Rev. 2 →

I wondering for G, the constraint on n of hard version differ from the the easy very with only 5 as muplicatif factor. As in the editorial the complexity of hard is nlogn what's the expected complexity of the easy version?

→ Ответить

heesooyaam

7 дней назад, # ^ |

I think it's about accuracy. you must write a code with good constant to pass hard version

→ Ответить

Abito

7 дней назад, # ^ |

It's a memory thing. My solution for G1 takes around 70MB so on G2 it gives MLE

→ Ответить

Noobish_Monk

6 дней назад, # ^ |

← Rev. 2 →

There are $$$O(n \sqrt n)$$$ and $$$O(n \sqrt n log \ n)$$$ solutions that pass the easy version

→ Ответить

LuckyDomino

7 дней назад, # |

Had fun! Thanks.

→ Ответить

VIVEKSHAH786

7 дней назад, # |

super fast editorial

→ Ответить

grey_is_my_life_idk

7 дней назад, # |

The problem setter is very clever i mean look at the constraints(n=20) of problem D which forces you to think a some bruteforce or some DP approach so no one will go to the logical part of that which is easy at all.

→ Ответить

AldyDPP

7 дней назад, # ^ |

Oh yes I fell into that trap :( I spent a good 15-20 minutes trying to optimize iteration using bit mask meanwhile the O(n) solution is not that difficult to realize at all...

→ Ответить

hars_raj

7 дней назад, # ^ |

I wrote the logical, O(n) solution during contest but later found the bruteforce easier

→ Ответить

ambriogulaster

6 дней назад, # ^ |

same i spent 30 min for writing dp, as i am practising dp already these days , but i was not able to write correct recurssion , can anyone give solution using dp ?

`int f(int i, string s, int canSkip, int k) { // Base case if (i == s.length()) { return k + 2 == s.length() ? 1 : 1e9; }

int ans = LLONG_MAX;

// Handling two-digit numbers
if (i + 1 < s.length()) {
    int no2 = stoi(s.substr(i, 2));
    ans = min(ans, no2 * f(i + 2, s, 0, k + 1));
    ans = min(ans, no2 + f(i + 2, s, 0, k + 1));
}

// Handling single-digit numbers
int no1 = s[i] - '0';
ans = min(ans, no1 * f(i + 1, s, canSkip, k + 1));
ans = min(ans, no1 + f(i + 1, s, canSkip, k + 1));

return ans;

}

void solved() { int n; cin >> n; string s; cin >> s; cout << f(0, s, 1, 0) << endl; }`

This was my code please correct it ,not memorzied it but then its the easy part , can u just correct my recurssive code

→ Ответить

baroza

6 дней назад, # ^ |

check my submission I used easy recursion https://mirror.codeforces.com/contest/1986/submission/267070013

If you have any questions let me know

→ Ответить

Sidaksh

6 дней назад, # ^ |

← Rev. 2 →

Visit this code 267035503 i have used DP to solve this problem

→ Ответить

pcumamahesh

6 дней назад, # ^ |

Yeah, even I spent $$$40$$$ min thinking of a bitmasking approach, but I kept calculating how much time it would take. When the bitmask I ran locally took $$$15600$$$ ms for $$$t=10^4, n=20$$$ for all $$$t$$$, I decided it must be a greedy approach.

→ Ответить

sidhunishan786

6 дней назад, # ^ |

TRUE!!!!!!!!

→ Ответить

Ylandolsi

6 дней назад, # ^ |

brute force approach o(n*n) https://mirror.codeforces.com/contest/1986/submission/267238262

→ Ответить

formidablechief27

7 дней назад, # |

← Rev. 2 →

-7

Detailed Video Editorial English

C : https://youtu.be/w7yaIcNz_1w

D : https://youtu.be/UZ-zb7NZrRU

E : https://youtu.be/dCtiB_TRfms

→ Ответить

ankit_2k3

7 дней назад, # |

← Rev. 3 →

https://mirror.codeforces.com/contest/1986/submission/267100334 [My submission]

I am getting WA on 2nd test case ? Why

Edit -> Solved by another algo

→ Ответить

Lu_xZ

7 дней назад, # |

-10

Good round! I enjoyed it.

→ Ответить

LMydd0225

7 дней назад, # |

← Rev. 2 →

+65

Why the sooooooo tight memory limit in problem G? I didn't see any reason to reject solutions on the memory constant factor!! Or do you really have a meaningful $$$O(n)$$$ memory solution? Anyway, if an acceptable solution uses $$$1\cdot n\log n$$$ memory, why to reject $$$2\cdot n\log n$$$?

→ Ответить

vgoofficial

6 дней назад, # ^ |

→ Ответить

dzhi

6 дней назад, # ^ |

I actually find the time limit is super tight. With the same core idea, it takes me dozens of iterations to make my Java solution be accepted, with lots of optimizations to reduce runtime and a special handling for the scenario of test 76. A time limit of 4 second instead of 3 would be better. The tight memory limit prevent me from using more time-efficient lookup table but is relatively less critical than time limit in my case.

→ Ответить

alagorithmet

5 дней назад, # ^ |

Yeah also the same issue for me. my cpp submission was running between 3.0 and 3.1s (checked in gym clone Contest) and not being able to pass after experimenting a lot with using maps instead of vectors and vice versa, adding pragmas etc. At the end i managed to get AC by starting my sieve from 2, since i don't need the info that 1 divides every number and got AC in 2.9s.

→ Ответить

hbar2803

7 дней назад, # |

No sample code?

→ Ответить

6 дней назад, # ^ |

the algorithm is easy enough for you to implement yourself. so do it as a challenge

PS: first time 5 ac before system tests on a div3 :))

→ Ответить

sarthakcoder05

7 дней назад, # |

Can anyone please tell me why my solution 267122161 for Problem D is giving Wrong Answer on test case 2?

→ Ответить

PaJlaT228PACTBOPOB

6 дней назад, # ^ |

→ Ответить

nedwards

6 дней назад, # |

can someone explain how to solve problem B? I was really stuck in problem B, especially thinking if the a[i][j] is a corner piece, edge piece, or neither. Thanks, really appreciate it!

→ Ответить

nedwards

6 дней назад, # ^ |

are we just trying to find the minimum of maximum adjacent cells of a[i][j]?

→ Ответить

tabj84

6 дней назад, # ^ |

We have to modify the array in such a way so that there's no element greater than either of its adjacent cells, and return the total number of such modifications we might have done to form the required array. You might not have to write different code for corner/edge/center piece, you can write code such that it wouldn't matter. I think you'd gain clarity if you see someone's submission

→ Ответить

6 дней назад, # ^ |

← Rev. 2 →

for the corners just increase the size of the grid by at least 2 like if it's 5 5 you make it 7 7 and also start indexing from 1 not from 0

that way you don't have to worry about i+1 or i-1

→ Ответить

Retired_Isaunoya

6 дней назад, # |

+50

For problem F, I used a unique method yesterday to find the bridge edges in this graph (which seems to be an undirected graph). While some parts may be a bit technical, I want to record and share it with everyone.

First, I used a union-find data structure to find a valid spanning tree (assuming that edge weights are directly assigned to the child nodes). Then, for the remaining edges $$$(u_i, v_i)$$$ that are not in the tree, I increment the path $$$(u_i, v_i)$$$ by one, because this forms a cycle, and cycles do not have bridge edges. This can be achieved through the LCA (Lowest Common Ancestor) and tree difference methods.(maybe this name, sorry for my poor English.)

Here is the submission. 267081057

However, after careful consideration, I realized that we can use a hashing and xor approach. Each time we cover a path, we assign a random value in the range $$$[0, 2^{64})$$$. Due to the properties of xor, the values will cancel out above the LCA, which is equivalent to checking if the path has been covered. Finally, we just need to calculate the subtree sizes in the tree and update the answer accordingly. This method eliminates the need to find the LCA.

Here is the submission. 267125590

→ Ответить

Tezcatlipoca

6 дней назад, # ^ |

Why not use Tarjan's algorithm?

→ Ответить

Retired_Isaunoya

6 дней назад, # ^ |

It can solve the problems more than find bridges.And this method is interesting.

→ Ответить

sahilf637

6 дней назад, # ^ |

damn!!!

→ Ответить

TheScrasse

6 дней назад, # ^ |

An alternative way to avoid LCA is finding a DFS tree instead of a spanning tree, in such a way that all the extra edges go from a node to one of its ancestors.

→ Ответить

dirty_fingers

4 дня назад, # ^ |

Your both solutions are very interesting. Thank you.

→ Ответить

the_last_smilodon

6 дней назад, # |

Very interesting problemset .

→ Ответить

SonuGupta001

6 дней назад, # |

my lazy brain could only thought of the dp solution for the problem E. Am I too dumb to realise the claver and O(N) soln of author ??

→ Ответить

6 дней назад, # ^ |

i use dp to tackle the case of odd numbers :))

didn't wanna use prefix/suffix sums cause i don't wanna go that way

→ Ответить

6 дней назад, # ^ |

can you explain a little bit your dp code ?

→ Ответить

AMBUJ_2003

5 дней назад, # ^ |

Can you explain how you used DP for that? I am unsure how to use a prefix/suffix array to find which odd index to remove. Can anyone explain how to do it optimally

→ Ответить

5 дней назад, # ^ |

this is my code: 267060049

→ Ответить

5 дней назад, # ^ |

for clarification!! (cause most are confused by the dp)

here i define "legal" as a legitimate way to insert elements into the array, which means that an element cant be used twice.

dp[i][0] is the optimal cost if we chose vv1[i] dp[i][1] is the optimal cost if we chose vv2[i]

this is to make sure all moves are legal, cause vv1 and vv2 are seperated.

→ Ответить

demitronization

6 дней назад, # |

Man, I overthinked a lot on D and at last ended up doing it with DP, i got tle because i was using n^4 * t, but just with a simple change (removing prev index and using a bool at its place, as partition can be either of size 2 or 1 I was able to Pass it)

Code here


ll rec(int i, int prev, int left, int canskip, string &s, vector<vector<vector<vector<ll>>>> &dp)
{
    ll n = s.length();
    if (left == 0)
    {
        ll val = stoll(s.substr(i, n - i));

        return val;
    }

    if (dp[i][prev][left][canskip] != -1)
    {
        return dp[i][prev][left][canskip];
    }

    if (i >= s.length())
    {
        return 1e9;
    }
    ll add = 1e18, mul = 1e18;

    if (prev)
    {
        add = stoll(s.substr(i-1, 2)) + rec(i + 1, 0, left - 1, canskip, s, dp);
        mul = stoll(s.substr(i-1,2)) * rec(i + 1, 0, left - 1, canskip, s, dp);
    }
    else
    {
        add = stoll(s.substr(i,1)) + rec(i + 1, prev, left - 1, canskip, s, dp);
        mul = stoll(s.substr(i,1)) * rec(i + 1, prev, left - 1, canskip, s, dp);
    }
    ll dont = 1e9;
    if (canskip)
    {
        dont = rec(i + 1, 1, left, 0, s, dp);
    }

    return dp[i][prev][left][canskip] = min(add, min(mul, dont));
}

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

    gin(t);
    while (t--)
    {
        gin(n);
        string s;
        cin >> s;
        vector<vector<vector<vector<ll>>>> dp(n + 1, vector<vector<vector<ll>>>(3, vector<vector<ll>>(n + 1, vector<ll>(3, -1))));
        cout << rec(0, 0, n - 2, 1, s, dp) << endl;
        // Always check if the input is 2n
    }
    // cout<<fixed<<setprecision(10);
    // cerr<<1000*((double)clock())/(double)CLOCKS_PER_SEC;
}

→ Ответить

6 дней назад, # ^ |

what is prev ?? I feel it's the same as can skip

→ Ответить

6 дней назад, # ^ |

← Rev. 2 →

ok I got it I think you can also convert canskip to third value to ensure that we don't take 2 NEIGHBOURING numbers twice which will make it 3 states only and also we don't need left because you can check at the end if canskip is used or not

→ Ответить

demitronization

6 дней назад, # ^ |

ah yes sure i can also remove canskip and just make it a 2*n dp, prev here is a bool which checks if we are making this partition as a 2 sized partition or not and as we can do that once i used canskip for that, but it's redundant as you said

→ Ответить

pokorj54

6 дней назад, # |

Either codeforces has a bigger stack or I suspect weak tests for problem F. My recursive DFS got AC and locally I am able to segfault it with giving it a path on 10^5 vertices.

→ Ответить

_Kee

6 дней назад, # ^ |

Codeforces actually gives you large stack space (256MB) for C++. See the --stack=268435456 flag given in the compiler options.

→ Ответить

mahadevpnair10

6 дней назад, # |

← Rev. 3 →

→ Ответить

ShauryaH4X

6 дней назад, # ^ |

n-2 operands are to be used, you used 4 operands

→ Ответить

6 дней назад, # |

-12

the Editorial Is not listed within the contest

→ Ответить

navyaoberoi

6 дней назад, # |

problem c has a similar idea to this

→ Ответить

codeWithDarshan

6 дней назад, # |

Can someone explain problem G

→ Ответить

tabj84

6 дней назад, # |

C has been hacked? How?

→ Ответить

Alsahy

6 дней назад, # |

Fast Editorial!

→ Ответить

DuongForeverAlone

6 дней назад, # |

What is actually the "count array" in G2?

→ Ответить

alagorithmet

6 дней назад, # ^ |

← Rev. 5 →

since no one replied let me try...

for A/B, C/D...; count array keeps track of D-s of C-s which is divisible by B. here B is the fixed b_i in the editorial; A=a_i, C=a_j, D=b_j. then to calculate their contribution to the answer you go through divisors x_1, x_2, x_3... of A and sum all count[x_1]+count[x_2]+... for the final answer. because for each B; you search for C which is divisable by B such that D from C divides A.

lets say you have 6 at index 7, 14 at index 3, 19 at index 7 and 21 at index 9(by taking gcd-s this will become 7/3). so actually you have 6/7, 14/3, 19/7 and 7/3.

as said in the editorial you iterate through b_i-s, so actually you iterate through denominators {7,3,7,3} and let's say you are at the first 7.

(so the input corresponding to 6/7)

you wanna check how many other fractions exist which have a number divisible by 7 in nominator and number which divides 6 in denominator. to do that you go through all the elements whose nominator is divisable by 7 i.e. {14/3,7/3}. then for each element you mark their denominator with count array, so in this case you process count[3]++ two times so you get count[3] = 2. count[x] = 0 for every x except 3.

as a next step (the part with "Now, for a fixed b_i" in the editorial); you go through all nominators which have 7 in denominator so through {6/7, 19/7}. for every such element go through their divisors; so for 6; you go through 1,2,3,6; and you update your answer with count[1]+count[2]+count[3]+count[6].

check my submission which passed in 2999ms (シ_ _)シ check unordered_map <int,int> count in my code 267200592

→ Ответить

cockatooo

5 дней назад, # ^ |

check out my latest comment below

→ Ответить

sohailkazi

6 дней назад, # |

← Rev. 2 →

In problem E, why is it advantageous to consider only the odd indices for removal if $$$m$$$ is odd?

Edit: I get it now. Choosing even indices makes the answer worse because you are now pairing up non-adjacent elements, which makes the answer larger.

→ Ответить

Naman1213

6 дней назад, # ^ |

yeah, This was the only observation I missed during contest, literally did everything else.

→ Ответить

sohailkazi

6 дней назад, # ^ |

Same. My Idea was that it was optimal to remove either the very first element or the very last element, but by the time I realised middle elements could also be removed for an optimal answer, it was too late.

→ Ответить

Anas986

6 дней назад, # ^ |

Was going through the comments, was pretty sure someone might've asked the same question. Thanks for explaining it as well.

→ Ответить

krissny

6 дней назад, # |

Why my problem B solution is still in queue☠️, Although I remember that it was accepted last night

→ Ответить

6 дней назад, # ^ |

system test going on The submissions are being judged again with more test cases(all the hacks are included in the new set)

→ Ответить

chauhan_09

6 дней назад, # ^ |

So, the Solutions will now also run for the Successful Hack Test Case for all Participants? Does that mean if I got an AC now my solution was not hackable in the hacking phase?

→ Ответить

6 дней назад, # ^ |

Yes. Thats the whole point for open hacking phase. If you get AC now that means no successful hack could have been used to hack your submission

→ Ответить

6 дней назад, # |

in problem E I'm sorting the array and matching each element with the closest one but this greedy is giving wrong at test 10 my answer is 15 but the correct is 14 is this approach really wrong ???

→ Ответить

6 дней назад, # ^ |

It would be better to include your submission in the comment. I guess this test case will help you explain. Assume n as 5 and k as 1 elements are 1,8,3,20,19. sort it you get 1,3,8,19,20 by your approach you will pair 1 and 3 then 8 and 19 but optimal pairing is 1 and 3 then 19 and 20. You may fix this but this method would still give tle.

→ Ответить

6 дней назад, # ^ |

Yes because I have to exclude one element if the size is odd I'm trying to come with an approach to exclude that one element in O(1) instead of the O(n) am I close ?

→ Ответить

6 дней назад, # ^ |

You are actually calculating it in O(n2). (Excluding every element and trying to get the number of operations). Your approach seems incorrect or very high complexity. If possible include your submission

→ Ответить

6 дней назад, # ^ |

https://ideone.com/xHwj6U this is O(n^2 logn) I know but am I even on the right way like can I optimize this ? or my whole approach has to be changed ?

→ Ответить

6 дней назад, # ^ |

I suggest you to read the editorial. You may try grouping elements based on ai%k (Obviously two numbers with different remainders can't be paired). If more than one group has odd number of elemnts then return -1 or proceed with your original approach for each group (here you wont have to check if the numbers can be paired or not cause it will always be possible to pair numbers in the same group) for even size groups just pair b1 and b2 b3 and b4 and so on. For one odd size group if it exists you have to find that one element which you need to exclude.

→ Ответить

rohajrohit

6 дней назад, # |

If anyone searching for dp solution for problem D. Here is my solution that got accepted:

ll dp[21][21][101];
ll helper(ll i, ll cnt, string s,string a1){
    ll n=s.size();
    if(a1.size()>2){
        return 1e9;
    }
    else{
         if(cnt>n-2 || i>n){
        return 1e9;
    }
        ll y=stoi(a1);
        //debug(a1);
        if(cnt==n-2 && i==n){
        return stoi(a1);
    }
    if(dp[i][cnt][y]!=-1){
        return dp[i][cnt][y];
    }
    ll a=INF,b=INF,c=INF;
    string x="";
    if(cnt<n-2 )a=stoi(a1)+helper(i+1,cnt+1,s,x+s[i]);
    if(cnt<n-2 )b=stoi(a1)*helper(i+1,cnt+1,s,x+s[i]);
    c=helper(i+1,cnt,s,a1+s[i]);
    return dp[i][cnt][y]=min({a,b,c});
    }
}
void solve()
{
    ll n;
    cin>>n;
    string s;
    cin>>s;
    string a="";
    a+=s[0];
    memset(dp,-1,sizeof(dp));
    //<vector<vector<ll>>>v(n+1,vector<vector<ll>>(n,vector<ll>()))
    //debug(help("2+3+3+11"));
    //map1[a]=1;
    ll ans=helper(1,0,s,a);
    //debug(map1);
    print(ans);
}

→ Ответить

a.rjput

6 дней назад, # ^ |

can you brief about your DP solution? what are the params of the recursive function and the recursive function?

→ Ответить

rohajrohit

5 дней назад, # ^ |

dp[i][j][k] represent minimum value till the ith index and operation used is j and the integer value of previous string is k . Actually since we have to do exactly (n-2) operation, the previous string's size can go to max 2 and that we can store by assigning maximum value of k =100.

→ Ответить

keshavb02

6 дней назад, # |

I think in Problem-D solution the case where a "0"(zero) exists the answer must be zero, is missing a case where n==3 because you will see p0q, which will not lead to zero, it will lead to min(p*10+q,p+q,p*10*q). Else everything is fine

→ Ответить

RohitRKS

6 дней назад, # |

For Problem D : Simple DP solution in O(N)

Hint 1

Hint 2

Code for Reference

→ Ответить

Amit9

6 дней назад, # ^ |

← Rev. 5 →

Can you please review this code and help me debug.

CODE

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll MOD = 1e9 + 7;

ll f(int i, bool taken, string& s, vector<vector<ll>>& dp){
    int n = s.length();
    //Base cases
    if (i <= 0) return (s[0] - '0');

    if(dp[i][taken] != -1) return dp[i][taken];

    //Doing stuffs on index
    ll val = (s[i] - '0');
    ll pair = LLONG_MAX;
    if(!taken && i > 0 && i < n - 1) pair = stoll(s.substr(i - 1, 2));

    if(taken){
        return dp[i][taken] = min(val + f(i - 1, false, s, dp), val * f(i - 1, false, s, dp)); //If pair of digit already taken, go digit by digit
    }
    else return dp[i][taken] = min({val + f(i - 1, false, s, dp), val * f(i - 1, false, s, dp), //else we have one more option to take a pair
                                    pair + f(i - 2, true, s, dp), pair * f(i - 2, true, s, dp)});
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;

        if(n == 2){
            cout << stoll(s) << endl;
            continue;
        }

        bool flag = false;
        if(n == 3){
            if(s[0] == '0' || s[2] == '0'){
                cout << 0 << endl;
                continue;
            }
        }
        else{
            for(int i = 0; i < n; i++){
                if(s[i] == '0'){
                    cout << 0 << endl;
                    flag = true;
                    break;
                }
            }
        }
        if(flag) continue;

        vector<vector<ll>> dp(n, vector<ll> (2, -1));

        cout << f(n - 1, false, s, dp) << endl;
    }

    return 0;

}

Update : Final AC code:)

Spoiler

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll MOD = 1e9 + 7;

ll f(int i, bool taken, string& s, vector<vector<ll>>& dp){
    int n = s.length();
    //Base cases
    if(i == 1 && taken == false){
        return stoll(s.substr(i - 1, 2));
    }
    if(i == 0) return (s[0] - '0');

    if(dp[i][taken] != -1) return dp[i][taken];

    //Doing stuffs on index
    ll val = (s[i] - '0');
    ll pair = stoll(s.substr(i - 1, 2));

    if(taken){
        return dp[i][taken] = min(val + f(i - 1, true, s, dp), val * f(i - 1, true, s, dp)); //If pair of digit already taken, go digit by digit
    }
    else return dp[i][taken] = min({val + f(i - 1, false, s, dp), val * f(i - 1, false, s, dp), //else we have one more option to take a pair
                                    pair + f(i - 2, true, s, dp), pair * f(i - 2, true, s, dp)});
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;

        if(n == 2){
            cout << stoll(s) << endl;
            continue;
        }

        vector<vector<ll>> dp(n, vector<ll> (2, -1));

        cout << f(n - 1, false, s, dp) << endl;
    }

    return 0;
}

→ Ответить

6 дней назад, # ^ |

do you have dp for E

→ Ответить

Ylandolsi

6 дней назад, # ^ |

u doing dp[i-1]* val

but if if u have ( a1 + a2 + a3 * a4 )

a4 will be multiplied by a3 only , but in ur code u r checking multiplied by the prefix

how this leads to the correct answer ?

→ Ответить

Ylandolsi

6 дней назад, # ^ |

i think i got, bcz we only do the multiplication if a[i] == 1

so only this case will be covered and this is what we want

→ Ответить

ConnorChang

6 дней назад, # |

Why did i get a run time error for C? 267036690

→ Ответить

6 дней назад, # ^ |

maybe cause of the overflow of upper and lower?

→ Ответить

ConnorChang

6 дней назад, # ^ |

upper and lower are always between 0 and n, and they are both long long

→ Ответить

Rifat02

6 дней назад, # ^ |

← Rev. 2 →

it is possible to upper is less than zero( upper < 0) underflow and lower is greater than n-1 ( lower >= n) overflow But your code is right and i got ac without any change check it https://mirror.codeforces.com/contest/1986/submission/267226535

→ Ответить

Xiao_2710

6 дней назад, # |

The cheating is going out of hand,I refuse to believe that more than 6k did D.

→ Ответить

6 дней назад, # ^ |

but considering that only 25% of people got A also got D, i'd say it's pretty reasonable (and also, this is div3, second easiest division)

→ Ответить

Xiao_2710

6 дней назад, # ^ |

I'll say around 500-800 people cheated there way to D.It's kinda disheartening,my positive delta keeps shrinking even with similar ranks, and negative delta keeps on increasing. In the last div2,I did first 2 in 17mins,got a rank of 5700, and a delta of -5,even when my rating was just 1203, we are now expecting pupils to do div2 C too now,to just remain a pupil?

→ Ответить

6 дней назад, # ^ |

im afraid so :). even when i do C on a div2 (as a pupil), the rating bump is almost nonexistent.

→ Ответить

Code1000101

6 дней назад, # |

Man dropped editorial as soon as the contest ends. Nice work.

→ Ответить

yuaksoinocenow

6 дней назад, # |

F was amazing! Please add more graph problems in Div3

→ Ответить

benjaminnn

6 дней назад, # |

← Rev. 3 →

Can the F one be done using DSU?

→ Ответить

navyaoberoi

6 дней назад, # |

why did i get runtime error for problem d? Please help me out 267184148

→ Ответить

Mr.BruceWayne

6 дней назад, # |

74TrAkToR There is a mistake in the Problem-D editorial.

You mentioned If there is at least one 0 , the answer is 0 . We can simply place all signs as ×.

This is not true even for a given test casen=3 and s='901' whose answer will be a 9 and not a zero.

→ Ответить

nootnoot1729

6 дней назад, # ^ |

-6

yes if number of operations are 1 or n=3 then the answer would be zero only if the 0 is at the ends of number.

→ Ответить

lptd

6 дней назад, # ^ |

-6

If all numbers are 1, the answer is 1. We can simply place all signs as ×.
This is incorrect as well. Simple test case would be s = "111" and the answer should be 1 * 11 = 11

→ Ответить

Mr.BruceWayne

6 дней назад, # ^ |

← Rev. 3 →

Yes

→ Ответить

MisterReaper

6 дней назад, # ^ |

First, let's iterate through the position $$$i$$$ , such that we do not place a mathematical sign between the $$$i$$$ -th and $$$(i+1)$$$ -th elements.
Next, we have the following task — we have $$$n−1$$$ numbers and we need to place a + or × sign between each pair of neighboring numbers to minimize the result.

You did this process after you had $$$n-1$$$ numbers.

→ Ответить

chessworm

6 дней назад, # |

I think in D if all numbers are 1 then answer should be 11 not 1 because we will need to concatenate two numbers.

→ Ответить

devansh_khandelwal

6 дней назад, # ^ |

If all numbers after the concatenation are 1, then the answer will be 1. We can't consider this before the concatenation.

→ Ответить

ASHWANTH_K

6 дней назад, # |

← Rev. 2 →

why such tight memory constraints on G? why cannt they give more memory???? I got G1 accepted, and G2 was MLE on 43rd testcase... sad life...

→ Ответить

A_xor_A

6 дней назад, # |

← Rev. 3 →

Problem 1986D - Mathematical Problem solution:

Key observation: As we can use only n-2 sign (+, x), so there must be at least one two-digit number. Then just find the minimum answer as asked.

-Time Complexity O(n ^ 2)

        int n; 
	string s;
	cin >> n >> s;
	int ans = INT_MAX;
	for(int i = 1; i<n; i++){
		int num = stoi(s.substr(i-1, 2)); 
		for(int j = 0; j<n; j++){
			if(j==i-1 || j==i) continue;
			int cur = s[j]-'0';
			num = min(num*cur, num + cur);
		}
		ans = min(ans, num);
	}
	cout << ans << '\n';

→ Ответить

Defenser

6 дней назад, # ^ |

Solution is the same, just brute force without heuristics.

→ Ответить

A_xor_A

6 дней назад, # ^ |

I didn't able to guess it at the contest time! Sad Life!

→ Ответить

45_fortyfive

6 дней назад, # ^ |

I don't think the reasoning is correct, although the algorithm will yield correct outputs accidentally.

The algorithm reorders the numbers, it can never search the possibility of 1 + 2 * 34, since 34 goes first.
The algorithm does not respect the order of operations, it can only search (12 + 3) * 4 but not 12 + 3 * 4.

However, the algorithm yields correct outputs since it follows the correct reasoning by accident.

If there are 0, num will be 0.
If there are 1, num will be unchanged.
Otherwise, num += cur.

→ Ответить

A_xor_A

6 дней назад, # ^ |

In case of minimization, it's always correct. Because the intuition behind is that You never want to multiply number that gives greater result than just adding those two numbers. And that's what asked in the problem statement.

→ Ответить

sumitpatel

6 дней назад, # |

can tell me anyone what is wrong in my code 267195219 // i have basically find every 2 digit pair and min number towards left and towrards right and then left — central — right 4 cases * * + * * + + + it is frustrating

→ Ответить

m.amanullah7

6 дней назад, # |

Why this contest is showing in unrated?

→ Ответить

iiiaaabbuuu

6 дней назад, # |

Can anyone tell me what's wrong with my solution for problem D? 267205625 It's a simple brute force solution but I still got WA on test case 2.

→ Ответить

Muhammad_Tahasan_Yo_Yo

6 дней назад, # |

Clean and fast Editorial

→ Ответить

__Martian

6 дней назад, # |

Can someone explain for F. How to Find if a edge is a bridge or not.

→ Ответить

kl0989e

6 дней назад, # ^ |

Good site to learn about bridges.

→ Ответить

Amit9

6 дней назад, # |

← Rev. 8 →

Can anyone please review my Dp soln and tell what is wrong here, either any logical error or overflow. The output seems like it is an overflow, if it is then how should i avoid it?

CODE

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll MOD = 1e9 + 7;

ll f(int i, bool taken, string& s, vector<vector<ll>>& dp){
    int n = s.length();
    //Base cases
    if (i <= 0) return (s[0] - '0');

    if(dp[i][taken] != -1) return dp[i][taken];

    //Doing stuffs on index
    ll val = (s[i] - '0');
    ll pair = LLONG_MAX;
    if(!taken && i > 0 && i < n - 1) pair = stoll(s.substr(i - 1, 2));

    if(taken){
        return dp[i][taken] = min(val + f(i - 1, false, s, dp), val * f(i - 1, false, s, dp)); //If pair of digit already taken, go digit by digit
    }
    else return dp[i][taken] = min({val + f(i - 1, false, s, dp), val * f(i - 1, false, s, dp), //else we have one more option to take a pair
                                    pair + f(i - 2, true, s, dp), pair * f(i - 2, true, s, dp)});
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;

        if(n == 2){
            cout << stoll(s) << endl;
            continue;
        }

        vector<vector<ll>> dp(n, vector<ll> (2, -1));

        cout << f(n - 1, false, s, dp) << endl;
    }

    return 0;

}

Update-1: The Base case was wrong and in if(taken){} there should be "true" in further recursive calls. Base case:

 if(i == 1 && taken == false){
        return stoll(s.substr(i - 1, 2));
    }
    if(i == 0) return (s[0] - '0');

This helped in avoiding overflow and correct output on many test cases but for few test case the answer was wrong.

Update-2: Final Accepted code :)

Code

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll MOD = 1e9 + 7;

ll f(int i, bool taken, string& s, vector<vector<ll>>& dp){
    int n = s.length();
    //Base cases
    if(i == 1 && taken == false){
        return stoll(s.substr(i - 1, 2));
    }
    if(i == 0) return (s[0] - '0');

    if(dp[i][taken] != -1) return dp[i][taken];

    //Doing stuffs on index
    ll val = (s[i] - '0');
    ll pair = INT_MAX;
    if(!taken && i > 0 && i < n) pair = stoll(s.substr(i - 1, 2));


    if(taken){
        return dp[i][taken] = min(val + f(i - 1, true, s, dp), val * f(i - 1, true, s, dp)); //If pair of digit already taken, go digit by digit
    }
    else return dp[i][taken] = min({val + f(i - 1, false, s, dp), val * f(i - 1, false, s, dp), //else we have one more option to take a pair
                                    pair + f(i - 2, true, s, dp), pair * f(i - 2, true, s, dp)});
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;

        if(n == 2){
            cout << stoll(s) << endl;
            continue;
        }

        vector<vector<ll>> dp(n, vector<ll> (2, -1));

        cout << f(n - 1, false, s, dp) << endl;
    }

    return 0;
}

→ Ответить

jayeshtotlani2

6 дней назад, # |

Can anyone tell me whats wrong with my prefix and suffix handling in problem in case of odd length 267095361

→ Ответить

hudsongeovane

6 дней назад, # |

Can someone explain me F better? I can find the bridges, but can't go any further. Run a single dfs in each bridge will get TLE. I didnt get the size of subtree part.

→ Ответить

hudsongeovane

6 дней назад, # ^ |

Ok, I managed to understand that. If I have an edge (u,v) that is a bridge, then when I pass from u to v in the dfs, I cannot go back to u anymore, so the number of nodes visited after v is the number of vertices in the other component after a disconnection.

→ Ответить

Zerocks

6 дней назад, # ^ |

Lets say you found the bridges between i and j. But we also need to find the sizes of the components i and j which we can be done efficiently by maintaining a subtree size where every subtree size of a node can be calculated during the dfs traversal. This way we dont need to calculate subtree size individually for each bridge.

After that the size of component i will be subtree[i] and j will be n-subtree[i] or subtree[j]. Now we just need to minimize the ans which is (subtree[i]*(subtree[i]-1))/2 + (subtree[j]*(subtree[j]-1))/2.

My submission : 267232116

→ Ответить

6 дней назад, # |

In problem E any one can help on how to approach the idea of excluding one element using DP

→ Ответить

shorya1835

6 дней назад, # |

Changing map to a sorted vector of elements + binary search works in G2, the time complexity is the same but i can't figure out why it removes the MLE i get with map, since intuitively, i am storing count in map and elements in vector, the storage in map is more sparse, is this happening because in testcase 43 the array values are such that, it leads to lower count values in map and thus, reducing the advantage of sparseness?

Map submission

Vector submission

→ Ответить

lxcxz

6 дней назад, # |

why show node for us? still have questions

→ Ответить

ayus34513

5 дней назад, # |

Can anyone pls provide cpp code for E problem , doing the same thing but got tle

→ Ответить

/* https://mirror.codeforces.com/contest/1986/submission/267290277

5 дней назад, # ^ |

you can filter search the submissions section

→ Ответить

oldisgold

5 дней назад, # |

can anyone help me ?I am getting TLE in test case 27. Thanks in advance/* ~~~~~

include <bits/stdc++.h>

using namespace std;

define pi (3.141592653589)

define mod 1000000007

define ll long long int

define all(c) c.begin(), c.end()

define min3(a, b, c) min(c, min(a, b))

define rfl(i, a, n) for (int i = n — 1; i >= a; i--)

define fl(i, a, n) for (ll i = a; i < n; i++)

define ct(x) cout << x << endl

define rd(a, n) fl(i, 0, n) cin >> a[i]

define wrt(a, n) fl(i, 0, n) cout << a[i] <<

define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

// char Array to int Using atoi() like string s // C++ string to int Using stoi() like char str[50]

int main() { fast int t = 1; cin >> t; while (t--) {

ll i,
    j, k, n;
cin >> n >> k;
ll arr[n+5];
rd(arr, n);
unordered_map<ll, vector<ll>> mp;
sort(arr, arr + n);

fl(i, 0, n) mp[arr[i] % k].push_back(arr[i]);

ll ans = 0;
ll odd = n % 2;

ll oc = 0;
for (auto it : mp)
    if (it.second.size() % 2)
        oc++;

if (n % 2 < oc)
{
    cout << -1 << endl;

continue; } for (auto &it : mp) { int sz = it.second.size(); if (sz % 2 == 1) {

ll s = 0;

            vector<ll> pref(it.second.size() + 5, 0);
            for (int i = 0; i < it.second.size(); i++)
            {
                if (i % 2)
                    s += (it.second[i] - it.second[i - 1]) / k;
                pref[i] = s;
            }
            // cout<<endl;

            s = 0;
            ll temp = 1e18;
            for (int i = sz - 1; i >= 0; i--)
            {
                if ((i % 2))
                {
                    s += (it.second[i + 1] - it.second[i]) / k;

                    // pref[i]=s;
                }
                else
                {

                    temp = min(temp, pref[i] + s);
                }
            }

            ans += temp;
        }


    else
    {

        for (int i = 1; i < sz; i += 2)
        {
            ans += abs(it.second[i] - it.second[i - 1]) / k;
        }
    }
}

cout << ans << endl;
}
return 0;

} ~~~~~

→ Ответить

5 дней назад, # ^ |

maybe the unordered map. it's been mentioned before that unordered_map can run in O(1), but in worst case O(n^2). this can be used in hacks.

→ Ответить

5 дней назад, # ^ |

my solution got AC with the same algorithm, and i used map.

→ Ответить

rather_rohit

5 дней назад, # |

can anyone tell the problem with my code on D 267075434 it was wrong on test case 4 https://mirror.codeforces.com/contest/1986/submission/267075434

→ Ответить

5 дней назад, # ^ |

i'm not too sure, but it seems like tha algorithm is wrong

using your algorithm (sorry if i'm wrong, that'd be embarrsaing) and the test 1117

the smallest 2 digit number is 11 the optimal cost if u use 11 is 11 x 1 + 7 = 18

but the optimal cost is 1 x 1 x 17 = 17

→ Ответить