Codeforces Round #980 Editorial

5 weeks ago, # |

i swear i can't figure out for the life of me why my solution to B isn't correct, and i'm not allowed to look at the failing test case either.

Spoiler

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int t; cin >> t;
	while (t--) {
		int n, k; cin >> n >> k;
		vector<int> v(n);
		for (int i = 0; i < n; i++) {
			cin >> v[i];
		}
		int ans = 0, l = 0, m = 0;
		sort(v.begin(), v.end());
		for (int j = 0; j < n; j++) {
			if (((v[j] - l) * n) + ans  < k) {
				ans += ((v[j] - l) * n);
				m++;
				n--;
				l += (v[j] - l);
			} else {
				cout << m + k << endl;
				break;
			}
		}
	}
	return 0;
}

→ Reply

xksark

5 weeks ago, # ^ |

I dont know about the formulas, but you should use long long instead of int.

→ Reply

4 weeks ago, # ^ |

thanks a lot, this was one of the two errors in my code, i just put * 1LL into the formula and it stopped overflowing. i never realized that the whole point of my formula was to keep running till we exceed k, and if k was 1e9 then it would overflow.

→ Reply

Krrishchanchal

5 weeks ago, # ^ |

← Rev. 2 →

Bro your code won't return any output if k is equal to sum of all elements of the array.

Try

3 6

1 2 3

Comment if you want me to fix it

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

that wasn't actually the error, i ran this test case before submitting. the actual error was me decrementing n within the loop while having the loop run n times, so if n was 4, it became 2 after the loop ran twice and exited. apart from this i needed to use long long too.

thanks nonetheless! lesson learnt: always dry run code in a verbose manner :)

→ Reply

Hussain_Elemam

4 weeks ago, # ^ |

← Rev. 2 →

+ almost always use long long. I had the same problem and spend about an hour before realizing it.

→ Reply

4 weeks ago, # ^ |

yeah, i think it's probably best to develop the habit of using long long for now

→ Reply

-Albatross

4 weeks ago, # ^ |

Same, I'm new to Codeforces and have been giving contests, but the solution to be just wouldn't come to my mind, I wasn't able to understand the 2nd last test case at all.

→ Reply

ibrahimwq

5 weeks ago, # |

← Rev. 3 →

+39

then $$$c_p \cdot q^{c_p} > (c_p - 1) \cdot q^{c_p - 1}$$$; otherwise, the smallest element can definitely be removed.

why?

→ Reply

r57shell

4 weeks ago, # ^ |

← Rev. 2 →

I also want to know "why?" Otherwise it's not a proof.

My way of deriving same claim

→ Reply

Noam527

4 weeks ago, # ^ |

+32

I did a similar claim, proves pretty much the same thing.

Suppose we took an optimal subset whose weights sum up to $$$S$$$, and let's fix some $$$(p, w)$$$ taken ($$$p<1$$$). Then optimality implies that the solution without this element, is not better. We can ignore the product of probabilities on both sides of the inequality and get:

$$$S - w \leq pS \to S \leq \frac{w}{1-p}$$$. If we took $$$k$$$ elements of probability $$$p$$$, with differing weights, then denote by $$$w$$$ their minimal weight. So $$$S \geq kw$$$, and $$$w$$$ can be plugged in the inequality above to get $$$k \leq \frac{1}{1-p}$$$.

The intuition behind the whole idea was easier for me to see in contest when I tried to bound the number of elements taken for $$$p = 0.5$$$, and certainly you won't take an element if it doesn't double your current sum.

→ Reply

ibrahimwq

4 weeks ago, # ^ |

thanks! it's very clear now

→ Reply

Noluck_167

5 weeks ago, # |

-20

C is a piece of dogShit,i mean why it had to be based on some crap observation.It could have been improved by giving a formal proof of why does that always work. Disappointed...

→ Reply

.-__-.

5 weeks ago, # ^ |

What's wrong with the proof provided?

→ Reply

Noobish_Monk

5 weeks ago, # ^ |

Another solution is to sort the arrays by comparing pairs $$$(min(a_{i,1}, a_{i,2}), max(a_{i,1},a_{i,2}))$$$. We can observe that if we move the array with minimal element to the left (and among these with the least maximum), the number of inversions cannot increase, so that's optimal order

→ Reply

dsarules

5 weeks ago, # ^ |

← Rev. 2 →

lol yeah that was my method

→ Reply

ravi_sumit33

4 weeks ago, # ^ |

I did the same but received WA: 286985983. I reverted the order of checking (first max and then min as opposed to first min and then max) and it got AC : 287000832. Still unable to understand why that happened.

→ Reply

ravi_sumit33

4 weeks ago, # ^ |

← Rev. 3 →

A grave mistake in my first submission. I modeled <= comparison in the custom comparator of sort function instead of <. Basically, at the end of the custom comparator, I should have returned false instead of true. Correct submission: 287210506

→ Reply

4 weeks ago, # ^ |

It has more to do with your lambda and how the sorting is handled using std::sort. I don't know exactly why but I think I read somewhere that it is usually recommended to do a "stable sort" with std::sort, as such I simply changed the "true" to "false" when the arrays are same, which makes it a stable sort, and thus got AC, 287213481.

→ Reply

the_siddh

4 weeks ago, # ^ |

-8

can you check my solution for div2 C . why it is giving me wrong answer 286973745 plz check it.

→ Reply

shivamgupta15347

4 weeks ago, # ^ |

Even this works...

→ Reply

IF-THEN

4 weeks ago, # ^ |

I solved this problem by just randomly trying different methods of sorting the arrays..
sort ascending by first then by second
or vice versa
or by min in pair .. etc
and then one of them by luck was successful

I didn't like the problem because I couldn't reason about it in any way but this shows that one can learn sth from this problem, like what is an exchange argument

→ Reply

FIN3R

7 days ago, # ^ |

Informal proof why sorting by sum works

→ Reply

Rohak

4 weeks ago, # |

Ormlis In D2C, how can we solve the problem for arrays of sizes three or more? I tried to solve it by comparing inversions of ab and ba for sorting but it seems this condition is not transitive and thus doesn't work for arrays of twos either, so I had to use some other min/max technique, which doesn't seem to generalise for sizes more than 2.

→ Reply

Meatherm

4 weeks ago, # ^ |

It will be quite more difficult because we can't use exchange argument anymore

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

Would you have any method for solving it?

→ Reply

mees

4 weeks ago, # ^ |

For lists of size four or more, this problem is known to be NP-complete, as you can read in, for example, "A Note on the Complexity of One-Sided Crossing Minimization of Trees" by Alexander Dobler. For lists of size 3, this problem is conjectured but not proven to be NP-complete.

→ Reply

Rohak

4 weeks ago, # ^ |

Would you be aware of any source where I can read about the conjecture for lists of size three? I couldn't find any articles or papers on this topic myself so I need a little a help, thanks!

→ Reply

Tschech

4 weeks ago, # ^ |

The original proof is here though: https://link.springer.com/chapter/10.1007/3-540-45848-4_10

→ Reply

_l_l_

4 weeks ago, # |

+16

got IGM but still cannot solve A during contest, isn't weird?

→ Reply

_l_l_

4 weeks ago, # ^ |

← Rev. 2 →

+21

A simpler solution for 1E:

When you choose a node as the root node, our answer is at least $$$\sum_{i=1}^n \frac12 s_i(s_i-1)$$$, where $$$s_i$$$ is the number of children of node $$$i$$$.

However, such a construction may not be able to satisfy some edges that pass through both the son and father at the same time. Let's consider the contribution of this situation to increasing the answer.

We set a dp state $$$f_i$$$ to represent the number of residual paths that can be uploaded through the parent when the node $$$i$$$ calculates the necessary contribution internally (i.e., the above equation).

Transfer as follows:

$$$f_u = \sum_{v\in son_u} \max(1 - [u\text{ is root}], f_v - (s_u - 1))$$$

After calculating $$$f_ {root}$$$, we must pair the extra paths pairwise, and when we choose the node with the highest degree as the root, we can prove that there must be a match to make the scheme valid:

[tbd, prove is hard]

So we can calculate $$$f_ {root}$$$ and add $$$\lceil\frac{f_{root}}2\rceil$$$ to the equation at the beginning.

using translator.

287001804

code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
long long dp[MAXN]; vector<int> G[MAXN];
long long ans = 0;
void dfs(int u, int f) {
	int d = 0; for (int v : G[u]) if (v != f) dfs(v, u), d++;
	dp[u] = 0; for (int v : G[u]) if (v != f) dp[u] += max((u == f ? 0ll : 1ll), dp[v] - (d - 1));
	ans += 1ll * d * (d - 1) / 2;
}
int main() {
	int t; scanf("%d", &t); while (t--) {
		int n; scanf("%d", &n);
		for (int i = 1; i <= n; i++) G[i].clear();
		for (int i = 1; i < n; i++) {
			int u, v; scanf("%d %d", &u, &v);
			G[u].push_back(v); G[v].push_back(u);
		}
		int rt = 1; for (int i = 2; i <= n; i++) if (G[i].size() > G[rt].size()) rt = i;
		ans = 0; dfs(rt, rt);
		printf("%lld\n", ans + (dp[rt] + 1) / 2);
	}	
}

→ Reply

milind0110

4 weeks ago, # |

+11

Is there a reason the submissions and testcases are still locked?

→ Reply

milind0110

4 weeks ago, # ^ |

← Rev. 2 →

Just a FYI the source code was visible for few mins I think after the contest ended. I'm not sure was it intended or was it some kind of bug.

→ Reply

PROELECTRO444

4 weeks ago, # |

+67

Samples on D1C are useless

→ Reply

bawali_coder

4 weeks ago, # |

B : can anyone tell me what is wrong with my solution , I can't figure it out, frustrated !

I used the same logic

Spoiler

ll solve(std::vector<ll> a, ll n, ll k) {
  ll ans = 0;

  std::sort(a.begin(), a.end());
  int ptr = 0;

  ll x = std::min(a[ptr] * n, k);
  ans += x;
  k -= x;
  ptr = ptr + 1;

  if (k > 0)
    ans = ans + 1;

  for (ll i = 1; i < n; i++) {
    a[i] -= a[0];
  }
  a[0] = 0;

  //std::cout << ans << std::endl;

  while (k > 0 && ptr < n) {
    ll x = std::min(a[ptr], k);
    a[ptr] -= x;
    k -= x;
    ans += x;
    if (a[ptr] == 0 && k > 0)
      ans = ans + 1;

    ptr++;
  }

  return ans;
}

→ Reply

TCL

4 weeks ago, # |

I thouth Convex Hull Trick would work on 1D because they seems simular. But it didn't so I'm sad.

→ Reply

anmolagrawal67415

4 weeks ago, # |

Here's my binary search approach for Div2 B:

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define sort(nums) sort(begin(nums), end(nums))
typedef vector<ll> vll;
int ret;
bool can(int mid,vll& a,int k){
    int cnt=0,tot=0;
    for(int i=0;i<a.size();i++){
        if(a[i]<mid){
            cnt+=a[i]+1;
            tot+=a[i];
        }
        else{
            cnt+=min(mid,k-tot);
            tot+=mid;
        }
        if(tot>=k){
            ret=min(ret,cnt);
            return true;
        }
    }
    return false;
}
int main() {
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        vll a(n);
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        ret=INT_MAX;
        sort(a);
        int l=0,r=a[n-1];
        while(l<=r){
            int mid=l+(r-l)/2;
            if(can(mid,a,k)){
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        cout<<ret<<endl;
    }
    return 0;
}

→ Reply

Yugandhar_Master

4 weeks ago, # |

I didn't understand D1C from the tutorial, can someone explain it in more detail

→ Reply

nathanballman

3 weeks ago, # ^ |

A bit late, but here. Consider a cycle of length k in one of the two graphs. Enumerate the vertices along the cycle as the official solution does. So the first vertex gets label 0, second 1, and so on to k-1 which is connected to label 0. Imagine that the cycle branches at the node labeled 5.

Because the graph is strongly connected if that edge is incident to vertex "e" then there must be a path from e to the node labeled 6 that does not use any edge more than once.

(why? we have used only 5->e and by definition there must be a path between any two vertices. Any path from e->...->6 that includes 5->e can be done without it because it must include e->6 after it (e->...->5->e->...->6)).

e->...->6 must have a length of a multiple of k because then we would have a cycle of length not a multiple of k.

(why? We can go from 5->6 in 1 move, or we can go from 5->e->6 in |e->...->6|+1 moves. We know we have a cycle of length k through 5->6 so |0->...->5| = 5 and |6->...->0| = k-5-1 so |0->...->5|+|5->e->...->6|+|6->0| = lk. then (5)+|5->e->...->6|+(k-5-1)=lk then |5->e->...->6|=(l-1)k+1)

So every path must conserve this coloring property and this is the only property required. (proof: collapse every node of the same color into a single node and conserve edges the only cycles remaining are of length k, longer cycles just represent going around this graph more than once).

Now we can just add edges from k -> k+1 as needed to solve the problem.

→ Reply

Yugandhar_Master

3 weeks ago, # ^ |

Thanks it helps

→ Reply

papa-ka-para

3 weeks ago, # ^ |

I feel so dumb. :( .

→ Reply

Yugandhar_Master

3 weeks ago, # ^ |

Why?

→ Reply

Bnahmad23

4 weeks ago, # |

I had different solutions for both div2 C and D

for C it's a completely different one, I used the following sort

sort(id,id+n,[](int lt,int rt){
            pair <int,int> lM = {max(a[lt].first,a[lt].second),min(a[lt].first,a[lt].second)};
            pair <int,int> rM = {max(a[rt].first,a[rt].second),min(a[rt].first,a[rt].second)};
            return lM < rM || (lM == rM && a[lt] < a[rt]);
        });

for D, Instead of building a graph I used a minimum segment tree to build the distance array so let's say we got d[i] = get(i,n), then we update seg(b[i],min(d[b[i]],d[i]+a[i]))

→ Reply

adepteXiao

4 weeks ago, # ^ |

Yes, task D2D has a solution with a Segment Tree, some participants of the olympiad and rounds wrote it, but it seems to me that the solution with Dijkstra looks more concise :)

→ Reply

verstrapp_1

4 weeks ago, # |

For Div2 C, I initially tried to sort any tuples by the following condition. Consider the two possible arrangements [tup1[0],tup1[1],tup2[0],tup2[1]],[tup2[0],tup2[1],tup1[0],tup1[1]] and in whichever arrangement the number of inversions is less I put that first. I got wrong answer on testcase 1123.I saw @Dominater069 also try to do the same initially. Can someone please explain why this solution is wrong?

→ Reply

4 weeks ago, # ^ |

I had done the same thing initially. I suggest you read the following if you are not aware of transitive conditions for sorting.

Exchange argument: Suppose there is a correct arrangement of the arrays. The editorial proposes a solution that says the arrangement created by sorting based on sum. We now only have to prove that any optimal arrangement can be transformed into the exact arrangement based on ascending sum, without worsening the answer.

Transitivity: Now the condition of sum is transitive, i.e. sum(a) < sum(b) and sum(b) < sum(c) means sum(a) < sum(c). Now, if the correct arrangement has a pair of indices which doesn't follow this sum order, then we can argue that there is at least one adjacent pair such that they are out of order. The proof is simple. Assume there are non-zero number of elements between the closest pair of out of order pair, hence all the elements in between them are individually in correct order with either of them. Pick a random element x in between them. a < x and also x < b, so it must be that a < b, but we just assumed a > b. Hence the closest pair cannot have correct order elements in between them.Now when we flip the order of the two adjacent arrays, their ordering doesn't matter to the rest of array, but only on the relative order of the two adjacent elements which we show can be flipped without worsening the solution. We can keep arguing and flipping adjacent pairs until there is no pair out of order. Hence we can transform the correct arrangement to our preferred arrangement without worsening the answer.

Since sorting by (min, max), (max, min) or sum are all transitive conditions, all of them have a similar exchange argument and are all correct.

TL; DR: The count of inverse for ab and ba is not transitive and it cannot be guaranteed that the optimal answer will have adjacent out of order pairs (ordering based on Inv(ab) < Inv(ba)), if they are not adjacent then swapping them affects all the elements in between and thus it cannot be guaranteed to not worsen the answer.

→ Reply

verstrapp_1

4 weeks ago, # ^ |

Such a nice explanation! I didn't actually think about how sorting works!. Thanks a lot. Here is a testcase for anyone else who will read this in future after having made the same mistake as me. [[3,3],[4,1],[2,2]]

→ Reply

SuperMo

3 weeks ago, # ^ |

← Rev. 2 →

silly question please forgive and answer : how exactly did we show that swapping the 2 adjacent out of order pair will not increase the inversion between them ? is it just be trying some cases ? it's clear that it will not affect the left or the right part of the array but what about the 2 pairs them self ?

→ Reply

3 weeks ago, # ^ |

yes it's casework only, and can be proven by brute forcing all possible cases. There is no general theorem regarding this, for example the order by summation heuristics becomes untrue for sizes starting from 3.

→ Reply

JustInCase

4 weeks ago, # |

← Rev. 3 →

I feel like the test cases on D1C are quite weak because I just accepted it with a simple $$$O(K^2)$$$ brute force that checks if the two pairs of counting arrays are equal for any cyclic shift.

On the other hand, I assume it will be hard to generate such a test case if people construct the adjacency matrices and run DFSs differently because this will introduce some randomness in the resulting counting arrays, although that is not the case since most people just run DFS starting from vertex 1 (that is what I did in my accepted submission 287195742).

Was there an attempt to create some test cases against such an obvious brute force?

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

+21

Uphacked. Also, I think it's not hard to prepare a few of such cases with different "shifting" of the node numbers so that these "lucky" codes cannot pass. Since its average number of iterations would be something like $$$\cfrac{K^2}{4}$$$, it's very unlikely for them to run in the TL even for like 2 of such cases.

→ Reply

ankitranjan10may

4 weeks ago, # |

// this is code
#include<iostream>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n,k;
        cin >> n >> k;
        int arr[n];
        
        for(int i=0;i<n;i++)
        {
            cin >> arr[i];
        }
        
        int temp =0;
        
        if(k%n==0)
        {
            temp = k/n;
        }else
        {
            temp = k/n + 1;
        }
        int count =0;
        for(int i=0;i<n;i++)
        {
            if(arr[i]<temp)
            {
                count++;
            }
        }
        
        int ans = count + k;
        cout << ans << endl;
    }
    return 0;
}

anyone, can you find where will it fails.

→ Reply

ibrahimwq

4 weeks ago, # |

← Rev. 2 →

isn't constant C in problem 1D just $$$200000 + 1$$$, not $$$200000 \times \left( \frac{100}{99} \right)$$$

UPD: I think my claim is wrong, but it gets AC with $$$C = 200000$$$

→ Reply

LinkWish

4 weeks ago, # |

Use brute force with O(K^2) time complexity to check the cyclic shift in Div.1 C can be accepted. Can it be proved right or just there isn't any hack yet.

→ Reply

LinkWish

4 weeks ago, # ^ |

submission

→ Reply

wdnmdwrnmmp

4 weeks ago, # |

← Rev. 2 →

Hacks to D1C have got Unexpected verdict. Ormlis can you check the validator?

link

→ Reply

Ormlis

4 weeks ago, # ^ |

Yes, sorry about this. It seems we didn't have good tests against cyclic shift checking in O(k^2), and you hacked one of the solutions, that was marked correct in polygon.

→ Reply

r57shell

4 weeks ago, # |

← Rev. 3 →

2023D - Many Games There is statement $$$W\cdot (100 - p_i) > 200000$$$. It's not a simple one.

Analysis

Denote $$$L = 200000$$$. We said we assume sum of $$$w_i$$$ is greater than $$$C$$$. This means $$$W + w_i > C$$$. So we have:

$$$ W + w_i > C \\ W > C - w_i \\ W \cdot (100 - p_i) > (C - w_i) \cdot (100 - p_i) $$$

To prove the claim, it's enough to show that

$$$ (C - w_i) \cdot (100 - p_i) \geq L $$$

With constraints:

$$$ 1 \leq p_i \leq 99 $$$ $$$ w_i\cdot p_i \leq L $$$

Idea is: for any fixed $$$C$$$ we will find minimum of $$$(C - w_i)\cdot(100-p_i)$$$. To do so, assume $$$C$$$ and $$$p_i$$$ are known, and find $$$w_i$$$ for which the function reach minimum. In this case $$$100-pi$$$ is just constant, so $$$w_i$$$ should be maximum. But we have constraint, thus $$$w_i = \frac{L}{p_i}$$$.

Next, assume $$$p_i$$$ is variable, and find the best value for $$$p_i$$$.

$$$ (C - \frac{L}{p_i})\cdot(100 - p_i) \rightarrow min \\ C\cdot 100 - C\cdot p_i - 100\cdot\frac{L}{p_i} + L \rightarrow min \\ C\cdot p_i + 100\cdot\frac{L}{p_i} \rightarrow max \\ \text{Let }\; f(x) = C\cdot x + 100\cdot\frac{L}{x} \\ f'(x) = C - \frac{100\cdot L}{x^2} = 0 \\ C = \frac{100\cdot L}{x^2} \\ x^2 = \frac{100\cdot L}{C} \\ x = \sqrt{\frac{100 \cdot L}{C}} $$$

We want when $$$1 \leq x \leq 99$$$ because only in this case extremum point to lie within the range. Otherwise we only need to check $$$x = 1$$$ and $$$x = 99$$$ points. Because only them can be minimum.

$$$ \sqrt{\frac{100 \cdot L}{C}} \geq 1 \\ \frac{100 \cdot L}{C} \geq 1 \\ 100 \cdot L \geq {C} \\ \sqrt{\frac{100 \cdot L}{C}} \leq 99 \\ \frac{100 \cdot L}{C} \leq 99^2 \\ \frac{100 \cdot L}{99^2} \leq C \\ \text{So we have range:}\; \frac{100 \cdot L}{99^2} \leq C \leq 100 \cdot L $$$

Outside this range only probability 1 and 99 matters. Substitute $$$p_i = x$$$:

$$$ C \cdot \sqrt{\frac{100 \cdot L}{C}}+100 \cdot \frac{L}{\sqrt{\frac{100 \cdot L}{C}}} = 2\sqrt{100 \cdot L \cdot C} $$$

So, the value for this extremum point when $$$p_i$$$ satisfy constraints is:

$$$ C\cdot 100 + L - 2\sqrt{100 \cdot L \cdot C} $$$

For all $$$C$$$ we also need to check for $$$p_i = 1$$$: (we still use $$$w_i = \frac{L}{p_i}$$$)

$$$ (C - w_i)\cdot(100 - p_i) \geq L \\ (C - L)\cdot(100 - 1) \geq L \\ C - L \geq \frac{L}{99} \\ C \geq \frac{L}{99} + L = L\cdot\frac{100}{99} $$$

And for all $$$C$$$ we also need to check for $$$p_i = 99$$$:

$$$ (C - w_i)\cdot(100 - p_i) \geq L \\ (C - \frac{L}{99})\cdot(100 - 99) \geq L \\ C - \frac{L}{99} \geq L \\ C \geq \frac{L}{99} + L = L\cdot\frac{100}{99} $$$

So, for given $$$L$$$, we need to have $$$C \geq L \cdot \frac{100}{99}$$$ to meet requirements above, and also since $$$L \cdot \frac{100}{99} \geq L \cdot \frac{100}{99^2}$$$ for cases when $$$C \leq 100\cdot L$$$ we need to make sure:

$$$ C\cdot 100 + L - 2\sqrt{100 \cdot L \cdot C} \geq L \\ C\cdot 100 \geq 2\sqrt{100 \cdot L \cdot C} \\ C^2\cdot 100^2 \geq 4\cdot 100 \cdot L \cdot C \\ C \geq \frac{L}{25} $$$

But $$$L \cdot \frac{100}{99} \geq \frac{L}{25}$$$, so we need only one requirement $$$C \geq L \cdot \frac{100}{99}$$$. For $$$L = 200000$$$ we get $$$C \geq 200000 \cdot \frac{100}{99}$$$.

A little note: extremum point happens to be the maximum. But I don't know how easy to show that it's maximum, so easier to show that it is never less than "endpoints" ($$$p_i = 1$$$ and $$$p_i = 99$$$).

→ Reply

LipArcanjo

4 weeks ago, # ^ |

About your analysis and your commentary about checking if something is minimum/maximum, you only need to check if $$$f"(x)$$$ is greater/lower then 0 at the points where $$$f'(x)$$$ equal $$$0$$$. This makes your analysis easier, as $$$f"(x)$$$ only assumes the sign required to be maximum overall $$$x > 0$$$. From this you only needs to compute $$$f(1)$$$ and $$$f(99)$$$ to check the inequality, removing the need to verify points with $$$f'(x)$$$ equal $$$0$$$ for $$$x > 0$$$.

→ Reply

lhlephuocdao

4 weeks ago, # |

In 2023B Skipping tutorial above, can anyone help me explain why we are allowed to do this "Now we are allowed to visit each problem as many times as we want"?

→ Reply

4 weeks ago, # ^ |

It's because we defined the subproblem as we can move on to each problem, no matter if we already solved them or not.

→ Reply

lhlephuocdao

4 weeks ago, # ^ |

Thanks for your answer. But could you let me know why " no matter if we already solved them or not." In the problem description, we can not visit the problem which was previously submitted or skipped

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

What you are mentioning is the constraint on the main problem, while this sentence is based on the subproblem that we just newly defined. We first solve the subproblem without the constraint, and then verify that the subproblem indeed solves the original problem.

Once we solve the subproblem where we can visit the same vertex multiple times using shortest distance algorithms, we also know that it guarantees that each vertex is visited at most once (because visiting a vertex multiple times never helps with improving the shortest distance), so we see that it indeed does not matter if we're trying to visit the same vertex multiple times or not. Therefore, going back to the main problem, if we reach to a certain problem $$$i$$$ with the least penalty possible, we can then solve all unvisited problems with index $$$\le i$$$, receiving the prefix sum of the scores minus the penalty as the total score.

→ Reply

lhlephuocdao

4 weeks ago, # ^ |

I got it. Thank you so much

→ Reply

the_last_smilodon

4 weeks ago, # |

How do you generate such graphs for problem div1C ,or do you just originate all cyles from the same node.

→ Reply

BetaHarshith

4 weeks ago, # |

Can someone pls tell why i got runtime error in pretest 4 for Div2 C , i sorted the array based on sum of elements
https://codeforces.net/contest/2024/submission/286970228

→ Reply