Really liked problem E, great contest.

great problems, thanks Mike and vovuh for setting div. 3s! much appreciated.

did i get bonus point by succefully hacking someones code in this div3 contest? P.S : i am new in this codeforces platform

The leaf trick for E is really neat , really liked it ... Nice contest

Can anyone tell me, in problem F's solution provided by Gassa: In the expansion part, "we can pick the side of expansion after which the value min(u,v,w) is larger, and if these are equal, pick any". I can't understand why in the case of equal, we can pick any. Wouldn't that affect afterwards?

Can someone tell me what's wrong in my code for Problem D

int test;
cin >> test;

while(test--){
    int n;
    cin >> n;

    vector < int > fact = factorize(n);
    bool isThere = false;
    for(auto i : cnt){
        if(i.second > 1){
            isThere = true;
            break;
        }
    }
    if(!isThere){
        cout << 1 << "\n";
        cout << n << "\n";
    }else{
        vector < int > ans;
        sort(all(fact), cmp);
        for(int i = 0; i < (int)fact.size(); i++){
            if(fact[i] != fact[i+1]){
                int pu = 1;
                while(i < (int)fact.size()){
                    pu *= fact[i];
                    i++;
                }
                ans.push_back(pu);
            }else{
                ans.push_back(fact[i]);
            }
        }
        cout << (int)ans.size() << "\n";
        for(auto i : ans)
            cout << i << " ";
        cout << "\n";
        cnt.clear();
    } 
}

return 0;

I have a simple approach for F:

(to avoid misunderstanding, I will count the array from index 1)

First, we will create an array $$$left$$$ and $$$right$$$ satisfy these condition:

a) $$$1 \leq left_i \leq i \leq right_i \leq n$$$

b) $$$A_i = min(A_{left_i}, A_{left_{i + 1}}, A_{left_{i + 2}}, ..., A_{right_i})$$$

c) $$$right_i - left_i$$$ is maximum.

We can build this array using deque, as I indicated in my submission.

Then, we will try to find out two index $$$x$$$ and $$$y$$$ such that $$$x \geq left_i - 1$$$ and $$$y \leq right_i + 1$$$. (why?).

To find out $$$x$$$ and $$$y$$$, we will maintain 2 more arrays: prefix maximum and suffix maximum. And the rest part could be done easily with binary search.

Finally, we can partition the initial array into 3 parts: $$$x$$$, $$$y - x - 1$$$, and $$$n - y + 1$$$.

My submission: 99517001

can anyone help me why my B question do not get accepted although my idea was same but failed particular testcase ~~~~~``

include<bits/stdc++.h>

using namespace std; typedef long long ll; typedef std::vector vi;; typedef pair<ll, ll> pi;

define ull unsigned long long

define F first

define S second

define PB push_back

define MP make_pair

define boht_tez ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

define MAXN ll(1e5 + 123)

define MAXINP ll (1e3 + 123)

define MAX_SIZE 100000000

int main() {

ifndef ONLINE_JUDGE

// for getting input from input.txt
freopen("input1.txt", "r", stdin);
// for writing output to output.txt
freopen("output2.txt", "w", stdout);

endif

ll t;
cin >> t;
while (t--) {

    ll n;
    cin >> n;
    ll a[n];
    ll b[n] = {0};
    ll mx = 0;

    for (ll i = 0; i < n; i++) {
       cin >> a[i];



       b[a[i]]++;


       mx = max(a[i], mx);
    }

    bool flag = true;
    ll g;
    for (ll i = 1; i <= mx; i++) {
       if (b[i] == 1) {

         flag = false;
         g = i;
         break;
       }

    }
    if (n == 1) {
       cout << 1 << "\n";
    }
    else if (n == 2) {
       if (a[0] == a[1]) {
         cout << -1 << "\n";
       }
       else if (a[0] > a[1]) {
         cout << 2 << "\n";
       }
       else if (a[0] < a[1]) {
         cout << 1 << "\n";
       }
    }
    else if (flag == true) {
       cout << -1 << "\n";
    }
    else {
       for (ll i = 0; i < n; i++) {
         if (a[i] == g) {
          cout << i + 1 << "\n";
          break;
         }
       }
    }

}

}

~~~~~

Anyone help me where i am getting wrong for problem F 99476252 or is my logic incorrect?

UPD: got AC (just because i wrote log() inplace of log2()).

Can anybody explain why my solution https://codeforces.net/contest/1454/submission/99483191 for D is giving TLE

can someone explain problem 2 in detail??

Can anyone familiar with C++ please explain this, In the editorial of Problem C, std::unique returns a forward iterator to the end of the modified vector right? Are we typecasting that to an int here ?

is E solvable for more than n edges?

Why system testing happens in Contests having open hacking phase , meaning it shows Accepted then what is the need of system testing

my solution for question 2 is same as written in tutorial, but it was hacked , Why :( solution link https://codeforces.net/contest/1454/submission/99428157

My solution for $$$E$$$ to find all nodes which belongs to cycle or not:
Use bridge finding algorithm, and if an edge is not a bridge then two nodes connecting this edge will be in cycle, so mark them. code.
PS : Simple dfs would have worked, but almost always i end up in an infinite loop, when writing dfs code to find nodes that are in cycle.

Can somebody help me understand how this submission got hacked? Is it some Java stuff?

Anyone use random shuffle to solve A?

problem C got weak testcases. Someone from the Egyptian Olympiad in Informatics(so I know him) passed problem C with a wrong solution so I hacked him. Surprisingly after system testing, I found that this is the only case that made him fail and if I didn't hack him, he was going to pass system testing. Oh, and also I found out that around 12 people also failed on the case(My case: Case#7). So around 12 people were going to also unfairly pass.

can anyone pls tell me at which test case my code is failing.

link of my solution : https://codeforces.net/contest/1454/submission/99488821

I solved F using segment trees and binary search in O(nlog² n). Submission.

#include <bits/stdc++.h>
#define int long long
using namespace std;

int range_max(int t[], int l, int r, int n) {  // max on interval [l, r)
    int res = 0;
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if(l & 1) res = max(res, t[l++]);
        if(r & 1) res = max(res, t[--r]);
    }
    return res;
}
int range_min(int t[], int l, int r, int n) {  // min on interval [l, r)
    int res = INT32_MAX;
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if(l & 1) res = min(res, t[l++]);
        if(r & 1) res = min(res, t[--r]);
    }
    return res;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;    cin >> t;
    while(t--)
    {
        int n;    cin >> n;
        int mintree[2 * n], maxtree[2 * n];
        for(int i = 0; i < n; i++)
        {
            cin >> mintree[n + i];
            maxtree[n + i] = mintree[n + i];
        }
        for(int i = n - 1; i > 0; i--)
        maxtree[i] = max(maxtree[i << 1], maxtree[i << 1 | 1]),
        mintree[i] = min(mintree[i << 1], mintree[i << 1 | 1]);

        int i;
        for(i = 0; i < n; i++)
        {
            int a, b, c;
            a = range_max(maxtree, 0, i + 1, n);
            int beg = i + 1, end = n - 2, mid;
            while(beg <= end)
            {
                mid = beg + end >> 1;
                b = range_min(mintree, i + 1, mid + 1, n);
                if(b == a)
                {
                    c = range_max(maxtree, mid + 1, n, n);
                    if(c == a)
                    {
                        cout << "YES\n";
                        cout << i + 1 << ' ' << mid - i << ' ' << n - mid - 1 << '\n';
                        goto end;
                    }
                    else if(c < a)
                        end = mid - 1;
                    else
                        beg = mid + 1;
                }
                else if( b < a)
                    end = mid - 1;
                else
                    beg = mid + 1;
            }
        }
        end:
        if(i == n)    cout << "NO\n";
    }
}

How to approach E if there were more than N edges ?

Can someone explain why my submission is showing wrong answer on test case 4 even though it is right? https://codeforces.net/contest/1454/submission/99475597

Alternative solution for F. Lets iterate through all values, and try to make each value minimum of second block. If we are trying to make $$$a_i$$$ minimum, we should find first value left to i, such that $$$a_k<a_i$$$, first value after i, such that $$$a_j<a_i$$$. Now we know, that second block lies somewhere in $$$(k, j)$$$ (otherwise, it`s minimum will be less then $$$a_i$$$). Lets just check second blocks $$$(k+2, j - 1), (k+2,j-2), (k + 1, j - 1), (k + 1, j - 2)$$$. Why check this values? Sometimes it might be, that array looks like $$$a_k, a_i, a_i, .... $$$, and we want prefix to have $$$a_i$$$ in it, same thing with suffix. We can try using segment tree. $$$O(n \log n)$$$.

https://codeforc.es/contest/1454/submission/99479843

I came up with simple approach in F.
First we will build min and max sparse table so that we can get min and max values in O(1).
Its easy to observe that as we increase length of a segment, maximum value increases , and minimum value decreases.

Using this observation : For every possible X from 1 to n-2, we will find lower bound(l) and upper bound(u) of possible value of Y. This can be done using binary search. The third segment ,if possible, will lie in between (l+1) to (u), and this can also be found using binary search.
If at any point we are able to find first, second and third segment, We will print it. Else No possible answer is there.
Using this approach, we can further extend the problem to calculate all possible X,Y,Z which satisfy the given conditions.
Time Complexity -> O(nlogn). Submission link -> https://codeforces.net/contest/1454/submission/99541373

deleted

In F solution by gassa why u=min(x[lo-2],a[lo-1]) i.e why x[lo-2] is here?

Question D is very good

Can someone explain problem D for me? I am having a hard time understanding the explanation

When we do cnt * (n-cnt), arent we counting some edges multiple times? Lets say we have two vertices on the cycle each with a tree of size k. Then for both vertices we do k*(n-k). So, arent the paths between both trees counted twice? Can you please correct me where I am going wrong.

can anybody tell me what's wrong with my code problem C got WA, D got TLE sorry for bad quality because I coded those in a rush

UPD: i knew my problem D code was wrong because i didn't check all primes possible but why was that TLE'ed

C: 99488693 D: 99475141

Can someone explain why did this solution TLE's? My Solution

Interesting fact: author's solution problem D have time complexity $$$O(\sqrt{t\cdot N})$$$, where $$$N$$$ is sum $$$n$$$ for all test cases ($$$N <= 10^{10}$$$).

Proof:

can someone explain to me the problem 3? i don't get the editorial.

also, i have a different approach of the problem, i don't know why it doesn't work.

the main idea of my solution is that for each element, we split the integers according to the element and and get the minimum size of the splitted integers.

so in the last test
11
2 2 1 2 3 2 1 2 3 1 2

if i split the 3, i get
2 2 1 2
2 1 2
1 2

which is equal to 3

Can someone explain to me how the proposed solution for D didn't send TLE when in the worst case scenario you'd have to check if the numbers are divisible by any of all values up to 10^5? And here I was thinking of how to optimize it to reduce it to sqrt(10^5) and only checking with prime numbers using a sieve lol.

For reference, using the method above, it takes way more than 10 seconds when testing the number 9999999769, which could perfectly fit into a test case.

This is my first time competing in codeforces, which probably explains my confusion. Anyways, any help with my doubt is appreciated :)

Hi all. in problem d i have made certain observation.

1. if the number is prime we cant do much we print the number itself

2. if the number is not prime then i observed and did this

-> count all the prime factors and the frequency. The maximum frequency will be the length.

-> what i observed is only 2 3 5 and other prime numbers are the only prime factors of a number. for example 65=5*13 8=2*2*2 and so on

now what i did in my code. first i checked whether a number is prime or not if it is then i did step 1 and if not i count all the 2s 3s 5s and other prime numbers if any

after all the counting if the max freq is 1 then printing the number itself ,if not then printing the minimum prime factor according the max frequency

now my problem is that my code is giving TLE like hell because my code for checking prime number is inefficient

so i want to know if my concept and approach is correct at all and if so how to optimize my code?

RESOLVED

In problem A, I wrote

for (int i = 0; i < n; i++)
         {
            cout << (i + 2) % n << " ";  
         }

instead of

		for (int i = 0; i < n; ++i) {
			cout << (i + 1) % n + 1 << " ";
		}

as shown in the editorial, but get output : 0 1 \n 2 3 4 0 1 for the input: 2 2 5 I think the codes are implementing the same thing. I have looked through c++ reference for the error, and searched "Modulo error" to find the reason, but I don't get anything useful. Can I have any hint or any keyword to search on Google about why this is happening?

Thanks!

For E Is there proof that it will have always 1 cycle?

The O(n) solution of promble F is very valuble.

Here is my solution .I improve it from the O(nlogn) solution.

let L be the left point, R be the right point. we can find that when L is increasing R decrease. also we can find that for one L there is only one R may be the answer.(there can be several but they are all the same.)

let lmax[L] be the maximum value from 1 to L, rmax[R] be the maximum value from R to n.(lmax[L]==rmax[R])

if there is k that (rmax[k]==rmax[R] && L<k && k<R && a[k]<rmax[R]) then the min value from L+1 to R-1 must smaller than rmax[R].we can skip all those R and go left.this can be checked in O(1) after some caculation outside the loop.

finally it will look like this .....a[L]......a[k]==a[k+1]==...==a[R-1]==rmax[R]....

a[k] is the last left number equals to rmax[R].

let just save the L and R and calculate it later.

here is a small problem, this is ok for lmax[L]==rmax[R] < MAX, I don't know if it also work when lmax[L]==MAX. so I take the part (lmax[L]==rmax[R]==MAX) out and solve it individually.

when calculate L[i] and R[i], we can go backward, so we can update the min value from L+1 to R-1 in O(1) , becuase we are adding number to the set.

I think the method that add a number to the set and get MAX or MIN instead of erase from the set is pretty important.

here is my code I not really good at it so is a bit long

but there is another approach without any graph algorithms that works very well for such kind of graphs

vovuh Is the leaf trick that you mentioned in the editorial of problem E, a particularly classic known idea / algorithm ?

I am applying seg tree+ 2 pointers in problem F ,but it gives WA on test case 2 (case 721) . Could anyone pls help me ? Here's my code :

99797628

Can somebody please help me with my code, its for problem E, I keep getting MLE and i just cant understand why? 100473133

In problem E, why does a normal BFS/DFS lead to MLE on test 2?

The memory limit seems to be sufficient.
I even tried declaring global arrays and with a maximum size of 100 to at least pass test 2, it still resulted in MLE. vovuh can you explain please?

PS: Solved it finally but had to rewrite from scratch (without using any boiler plate code). Not getting what's the problem with the previous one. Will using one/two extra vectors of $$$O(n)$$$ size make any difference?

I have solved F with segment trees and the two-pointer algorithm. So I have a start(== 0) and end(== N-1) variable. I have segment trees to query maximum from ([0, start], [end, N-1]) and minimum from ([start+1, end-1]). Now my segments are [0, start], [start+1, end-1] and [end, N-1]. My aim is to increase max1([0, start]) and max2([end, N]) as gradually as possible. Now in our while loop if max1 == max2 == min(from [start+1, end-1]) then we have found a solution otherwise we have to update start and end.

So if(max1 < max2) or (max1 > max2) I will start++ or end-- accordingly. But if max1 == max2 then I will compare A[start+1] and A[end-1] and if they too turn out to be equal then I will compare A[start+2] and A[end-2]. So even if I have a case where start+1 and end-1 point to equal elements I will make sure that the increase in [0, start] and [end, N-1] is gradual. 142372335 ~~~~~ Your code here... ~~~~~

ll N;
    cin >> N;
    vector<ll> A(N);
    for (ll i = 0; i < N; i++)
        cin >> A[i];
    vector<ll> segmentMin(4 * N, LONG_LONG_MAX), segmentMax(4 * N, LONG_LONG_MIN);
    buildMin(0, 0, N - 1, A, segmentMin);
    buildMax(0, 0, N - 1, A, segmentMax);
    bool possible = false;
    ll start = 0, end = N - 1;
    while (start + 1 < end)
    {
        ll max1 = queryMax(0, 0, N - 1, 0, start, segmentMax);
        ll max2 = queryMax(0, 0, N - 1, end, N - 1, segmentMax);
        ll min1 = queryMin(0, 0, N - 1, start + 1, end - 1, segmentMin);
        if (max1 == max2 && max1 == min1)
        {
            possible = true;
            break;
        }
        if (max1 < max2)
            start++;
        else if (max1 > max2)
            end--;
        // max1 == max2
        else
        {
            // we want to slowly increase max1 and max2
            if (A[start + 1] < A[end - 1])
                start++;
            else if (A[start + 1] > A[end - 1])
                end--;
            // ultimate slow increaser
            else if (start + 2 <= end - 2 && A[start + 2] < A[end - 2])
                start++;
            else
                end--;
        }
    }
    if (possible == false)
    {
        cout << "NO\n";
        continue;
    }
    cout << "YES\n";
    cout << start + 1 << " " << end - start - 1 << " " << N - end << "\n";

problem c

10

1 5 2 5 6 5 10 10 7 1 2

how is this going to be 1 !?????????????????????

I wasted 2 hour and it seems that I can't even get what the problem want