vovuh's blog

By vovuh, history, 7 months ago, In English

1454A - Special Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1454B - Unique Bid Auction

Idea: MikeMirzayanov

Tutorial
Solution

1454C - Sequence Transformation

Idea: MikeMirzayanov

Tutorial
Solution

1454D - Number into Sequence

Idea: MikeMirzayanov

Tutorial
Solution

1454E - Number of Simple Paths

Idea: vovuh

Tutorial
Solution

1454F - Array Partition

Idea: MikeMirzayanov

Tutorial
Solution
Solution (Gassa)
 
 
 
 
  • Vote: I like it
  • +134
  • Vote: I do not like it

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Great contest! :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the contest as always.

»
7 months ago, # |
  Vote: I like it +39 Vote: I do not like it

Really liked problem E, great contest.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    No. Bonus point can only be earned in regular Div.1 and Div.2 Round, or some Div.1+Div.2 Round like Global Round.

»
7 months ago, # |
  Vote: I like it +40 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    Can you pls explain how would you implement the straight-forward solution which is: "just extract and mark all cycle vertices and run dfs from every vertex of a cycle"? Thanks

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Start a dfs from any vertex and maintain prev of each element i.e the node before that node in the dfs tree. Now when you come across a visited vertex $$$v$$$ from the vertex $$$u$$$, then this means this vertex $$$v$$$ is part of a cycle and the cycle is $$$v, prev[v], prev[prev[v]], ... , u$$$.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        won't going to prev everytime take you to the root ? i guess you need to find the first common ancestor of u and v

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you explain which vertices are the cycle vertices?And what does it mean by "trees hanged on cycle vertices". I am not clearly understanding the solution to E.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Since the graph is connected and number of vertices is equal of number of edges, there will a only one cycle. Now you can notice other vertices will form a trees with cycles vertices as roots. (Try drawing some pictures)

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Consider storing the graph as vector <set <int> >, each vertex having a set of edges to adjacent vertices. Then we can efficiently remove an edge from the graph, by just removing it from the sets at both ends. In fact, here is a solution that does just that: 99510704

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        https://codeforces.com/contest/1454/submission/99432026 can you tell why this was giving tle its O(n) solution for problem B

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I also got TLE with the same logic. It seems declaring an array of length 200005 is not expected.

          I even got TLE for C as well with O(n) solution.

          Please let me know if you have found the exact reason.

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            declare your array globally or declare your array with number of elements because in every test case array is initialising with 0 and if test case is 1000 then 2*100000*1000 will be 200000000 will give tle

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks it got accepted. I wish I knew this before the contest :(.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 6   Vote: I like it +3 Vote: I do not like it

      I implemented it but can't find my mistake

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you tell your aprroach for problem f??

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain leaf trick bit more i didnt get that??

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      since the graph contains n edges that means it is a tree with one extra edge. This one extra edge will create some cycle in the tree. Now any note the following point 1) Any node in this cycle is of atleast degree 2 2) observe leaf trick -> we are picking the leaf nodes one by one and removing them and the edge between it and it's parent after processing. And after this removal either the parent node could either be of degree 1 (a new leaf), or (some node with more descendents present which would eventually be removed by the leaf trick). Or this parent node could be in the cycle. after removal of all the children nodes only nodes present in the cycle will be left in the queue.

»
7 months ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

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?

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    We can prove that if there is an answer, this approach won't lose it.

    Assume the maximum on left segment is $$$u$$$, the minimum on middle segment is $$$v$$$, the maximum on right segment is $$$w$$$ and there exists a partition makes $$$u = v = w = x$$$.

    For all the second segments that satisfy the condition, there is a biggest one include all the others, let it be $$$[L, R]$$$. (Easy to see if another segment $$$[L', R']$$$ also makes $$$u = v = w = x$$$ and neither of them includes the other, $$$[min(L, L'), max(R, R')]$$$ will be the one includes them both.)

    Because after every move $$$min(u, v, w)$$$ will only be smaller or stay the same, and $$$[L, R]$$$ is the biggest segment makes $$$u = v = w = x$$$. So for a partition $$$[l, r]$$$, if $$$l < L$$$ or $$$r > R$$$, $$$min(u, v, w) < x$$$. (Otherwise $$$[l, R]$$$ also satisfy the condition and it's bigger than $$$[L, R]$$$.)

    Initially, $$$[l, r]$$$ is included by $$$[L, R]$$$. When will we lose the answer? Only when $$$l = L$$$ and we make $$$l$$$ decrease or vice versa. But if we do so, $$$min(u, v, w)$$$ will be smaller than $$$x$$$ as we mentioned above, but in the other choice $$$min(u, v, w) >= x$$$, so the algorithm will pick the other and will not lose the answer.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

amazing! that's so cool! thanks!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

My Code
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Becoz of you We were not anywhere .Now we know where we stand Thankyou

»
7 months ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Very nice approach. Saved me the effort of learning RMQ.

»
7 months ago, # |
  Vote: I like it -47 Vote: I do not like it

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;
         }
       }
    }

}

}

~~~~~

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    u know right, You will get downvoted for pasting code rather than posting the submission link?

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      sorry this was first time i tried to interact in editorials...next time i will keep in mind ..my bad

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was this round rated?

»
7 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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()).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i*i <= n causes integer overflow and leads to increased iterations of the for loop. Changing int to long long should work.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain problem 2 in detail??

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have to print the index of the minimum element of all the elements that occur only once in the given array. Hope this makes it clearer.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I was asking for explaining the editorial for problem 2. sorry for bad English.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Its actually storing the count of input elements in 'cnt' vector and index of these elements in 'idx' vector. After this, it checks in the cnt vector for the element having the count value as 1. Since we are starting the search from 1, we will always find the minimum unique element first.

        For ex: 2 2 3 1

        in the above example,

        cnt[1] = 1, cnt[2] = 2, cnt[3] = 1

        idx[1] = 4, idx[2] = 2, idx[3] = 3

        Since the count of 1 is 1, therefore the answer is index of element 1 i.e. 4

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the approach of problem B without using map!

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use an array to store counts of all elements , now iterate through elements , for elements whose counts are 1 , find the minimum element and print its indices

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    We are getting the size of the array after modification, i. e. removing consecutive duplicates. As vector iterator is a random access iterator, so we can just subtract vector::begin(), to get the total number of elements from the beginning of vector to the end of the modified vector

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

is E solvable for more than n edges?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It is rejudged with hack cases. If someone's solution gets hacked, the author decides if he wants to include the hack case (i think) and everyone's code is tested again.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In task C:

res[a[0]] -= 1;

res[a[n — 1]] -= 1;

why do we have to do this?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because if you are at the first or at the last index you dont need to remove the segments from both the sides.

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe you get TLE because for each test you are resetting arrays flag and ind to 0. Thus the time complexity is $$$O(4 * 10 ^ 9) = ~4s$$$.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      if i use vector insted of array ,i got ac?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No it's not that. Just at the first for don't go through all the elements. Go through the first n+1 and it will be fine.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it
          for(int i=0;i<200005;i++)
          flag[i]=0,ind[i]=0;
          
          for(int i=0;i<n;i++)
          cin>>m,flag[m]++,ind[m]=i+1;
          int x=-1;
          for(int i=1;i<=n;i++)
          {
              if(flag[i]==1) {x=ind[i]; break;}
          }

          this loop is also go through (n+1)

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes but if n is a small number then you go through positions that you don't need to use. So if you change 200005 to n+1 it should be fine. PS: If you want you can make flag and ind vectors and assign them to the size of n.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Because you fill arrays with zeros from 0 to $$$2*10^5$$$ for each test, so it becomes $$$4*10^9$$$ in total. You can just change your “for” from 0 to n.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      https://codeforces.com/contest/1454/submission/99432026 can you tell why this is giving tle for b??

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        You are creating a map of size 10^5 for every test case. There can be 10^4 test cases so number of operations could be 10^9

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          so creating map will add to complexity??

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            You are initializing an array of size 200005 every time. The time complexity of array initializing is O(N). Thats why you were getting TLE.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        given, test case loop 2 * 1e4 ans all test case contain array of 2*1e5 then total time complexity 4*1e9 which gives TLE

        you can use vectora(n+1) insted of arr[200005] :)

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Nice! mine

    Java
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Change the size of your cnt array from 200001 to n+1. Because if number of test cases is 20000, total no. of operations will be 4∗10^9 which will result in TLE

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Anyone use random shuffle to solve A?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes you

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    did random shuffle passed test cases

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Random shuffle till find a valid solution passed.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        This solution is not wrong. We only need a few random shuffles to get the correct solution.

        What the problem asks (find a permutation such that P_i != i for all i) is basically to find a derangement of the permutation.

        More about derangement can be found here.

        The probability of getting a derangement from all permutations of length N is !N / N!. The value of !N / N! approaches to 1 / e = 37%

        Let's say we want to do random shuffle X number of times such that the probability of getting a derangement is at least 99%.

        Then, (0.37)(1 — (1 — 0.37)^X) / (1 — (1 — 0.37)) >= 0.99 This gives us X >= 10, so doing 10 random shuffles already gives us 99% chance of getting a valid derangement.

        We can increase X to 50 to increase the odds. We can also just random shuffle until we find a valid solution like you did, which can be expected to use at most 50 shuffles.

        This gives us a O(50TN) solution which gives accepted.

        An example demonstration of using 50 random shuffles here

»
7 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    what is your test case??

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      My testcase was a randomly generated array of length $$$2*10^5$$$. The elements in the array were from $$$10^5$$$ to $$$2*10^5$$$. A lot of people have done the mistake of doing a frequency array of size $$$10^5$$$ or $$$10^4$$$. Now you wonder, why they did the frequency array so small that would give runtime error or wrong answer? Here is my answer:

      1)Some people didn't notice the mistake. They were gonna pass unfairly.

      2)Other people who didn't use memset or a fast method of memory allocation in each testcase, the person got TLE with $$$2*10^5$$$. So the person decreased the allocation to $$$10^4$$$ surprisingly, it passed system testing and was going to pass all system testing.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    A stress test was missing in the pretests... An array of largest size with all elements equal was an easy hack for my solution (TLE but could be easily fixed if I TLEd a pretest). Was pretty happy that I did ABCDF then got hacked on C :/

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone good at math tell me the chances of getting a good permutation in a shuffle or if a randomized approach to first question would work?

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    If you don't know about derangement: https://en.wikipedia.org/wiki/Derangement.

    Total permutations possible = n! (quite trivial)
    Total permutations such that no a[i] = i for all i := 1 to n = D(n), here D(n) is the count of derangements possible for a sequence of size n.

    So the probability of finding some permutation = D(n)/n!.

    Extras : The recurrence relation for D(n) is as follows :
    D(n) = (n — 1)(D(n — 1) + D(n — 2))
    Base Conditions : D(0) = 1, D(1) = 0.

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

Code
»
7 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    that problem has no known polynomial time solution. try googling

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    The return; statement should be inside if(cnt==-1||cnt==1){...}

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you test it on your computer for test 4, where it is showing wrong answer? proJESUS

    1 9876543210

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

%%%%%%%%%%great

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's the limit for using Sieve of Eratosthenes to find primes? Certainly not

$$$10^{10}$$$

because I was getting TLE. When is it useful to use Sieve instead of direct factorization like in the given solution for D?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use Sieve to determine if a number is a prime number only if you have Q queries each asking the same question every-time. O(Qsqrt(N)). But using Sieve you can do it in O(Q + N).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.com/contest/1454/submission/99541373

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    That is exactly what I've done but I used seg trees for min and max xD but it worked. And yep, I agree that the idea of that solution so simple. I got the idea in only 10 minutes(and 30 minutes implementing and debugging due to the fact that I don't have a segment tree template :c).

»
7 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Why in my code it is giving wrong at test 4...! Please can anyone suggest...i will be very thankful to you.

bool check(ll n){ for(ll i=2;i*i<=n;i++){ if(n%i==0) return false; } return true; } void solve(){ ll n; cin>>n; if(check(n)) {cout<<1<<endl; cout<<n;} else{ vectorv; if(n%2==0){ while((n/2)%2==0){

v.pb(2);
            n=n/2;

        }
        v.pb(n);
    }
    else{
        for(ll i=3;i<=sqrt(n);i+=2){
            if(n%i==0){
            while((n/i)%i==0){

                v.pb(i);
                n=n/i;

            }

        }
        else
        continue;
        }

        v.pb(n);
    }

    cout<<v.size()<<endl;
    for(auto p:v)
    cout<<p<<" ";
}



cout<<endl;

}

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You should paste the link or put your long code into the spoiler

    Like this
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The maximum on the updated left segment, [0..lo - 1), is just stored in x[lo - 2].
    The middle segment just got a[lo - 1] added to it, so it can contribute to the minimum on the middle segment.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone tell why my code giving wrong on test4?

99543593

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is clearly stated that wrong answer Jury answer is better: 2 vs 1 on test 4 in details

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes i noticed that but can you suggest how to manage that case..

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Try dry running on similar and small test case and see where you are going wrong and also I don't think you need to handle odd/even case seperately

        bug
»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Question D is very good

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what and how does cntv.(n-cntv) contributing to the answer in problem E?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone help me debug?

This code for D fails on test 4

Code

Never mind, got AC!

»
7 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone help with TLE in test case 2 for problem E ??

UPD:For Wrong answer on TC 6 GOT it!! stupid overflow

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Enjoying this contest :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also think you are correct. I think there's a typo in the editorial for E and answer should be:

    for all cnts in cycle: cnt * (cnt — 1) + (cnt * (n-cnt) / 2) where the division is not integer division.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm an idiot, I should've thought about it more before commenting. What you're saying is true, the paths do look like they are being counted twice. You would normally expect it to be divided by 2. However, each time a node from a tree finds a path to another node that's in another tree, there are two ways to get there; it can either go clockwise around the cycle, or go anti-clockwise. This means this multiply-2 from going clockwise-anticlockwise cancels out the divide-2 from the paths being counted twice. So in the end, it's cnt*(n-cnt).

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's giving TLE on test 2 which has 2e4 testcases. Now, in your code, you are running this loop: for(int i = 0 ; i < ARR+2 ; i++) lastocc[i] = -1; where ARR = 2e5+2. Hence, in total you are doing computations more than 2e4*2e5=4e9, which is causing TLE.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi Everyone, this is a small request to those who solved problem E during the contest itself..I find many people solving it in just 15 to 20 minutes. So my request to all of you is 1. What were the important points you noticed about the problem and what conclusions did you have from that? If You can kindly answer , I believe it will give beginners like me good exposure as to how people solve good problems in such short times.. Thank you.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

if prefer Bangla Tutorial, check it out — https://www.youtube.com/channel/UCx-b02yRLunSkO8-T0OaBlg

»
7 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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:

Spoiler
»
7 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In fact it works, with a little improve.

    let x be the value we are trying. (For each value we only do it once) We need some way (you can think about it) to help us get to the next position NXT in the array that a[NXT]==x in O(1). Instead of go though all the array and find.

    so the total time need is O(n) after the improve.

    There are some parts need to be careful, It is easy to write wrongly.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      then i don't know why my code doesn't work. is it because i made the array into string? here is my code:

      int n=sc.nextInt();
      String ns="";
      Set<Integer> sets= new HashSet<>();
      for(int i=0;i<n;i++){
                      int x=sc.nextInt();
                      ns+=Integer.toString(x);
                      sets.add(x);
      }
      int min=Integer.MAX_VALUE;
      for(int x:sets){
                      String[] nArr=ns.split(Integer.toString(x));
                      List<String> list = new ArrayList<>(Arrays.asList(nArr));
                      list.removeAll(Arrays.asList("", null));
                      if(list.size()<min){
                          min=list.size();
      }
      }
      System.out.println(min);
      

      the first thing i did is to make the array into string and use the split() function to split the array and convert the splitted string into arraylist so i can remove the empty strings

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I don't know much about java but I think the split() function take O(n) time to split the array, so the total is still O(n*n). If there is no problem with the time we can use string, it's easy to write. But I don't suggest to use string to often.

        //In c++ there are lot of string operator are not O(1), but greater than it.
        string s="";
        s+='a'; //this is O(1);
        s='a'+s; //this is O(length of s);
        //if we do s='a'+s n times, it is O(1+2+3+...+n) = O(n*n)
        

        We need to use a list or array to save where the next number is. For example.

        a[] = {1,3,2,4,4,1,2}.
        
        nxt[1][]={0,1,5,8}
        nxt[2][]={0,3,6,8}
        nxt[3][]={0,2,8}
        nxt[4][]={0,4,5,8}
        
        

        we add a '0' in the beginning and a 'n+1' at the end. Then for each number check throw nxt, to calculate the answer.

        we don't have space so save a array size[2e5][2e5]. So use a list or vector.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody explain that what is mn and mx in the editorial of array partition and what are the cases when this three cases happen ??

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you can put you code I can see the problem. I'm not that good at English.

    Here is some of my understanding.

    First you only need to check the prime number from 2 to sqrt(n). Why? Because if we check from 2 to sqrt(n) and there is no prime number that n%P==0. We can confirm that n is a prime.

    So there is no need to check the rest of it.

    If the smallest prime factor of n is greater then sqrt(n) then n is a prime. Because if there is P1>sqrt(n) and P2>sqrt(n) there is no way P1*P2<=n.

    Here's how I divide a number in to prime factors

    cin>>n;
    int tmp=n;
    for(int i=2;i*i<=n;i++) 
    {
        while(tmp%i==0)
        {
            cnt[i]++;
            tmp/=i;
        }
    }
    if(tmp!=1) cnt[tmp]++;
    

    Of course tmp can be very big, it need to be write like this

    cin>>n;
    int tmp=n;
    for(int i=2;i*i<=n;i++) 
    {
        if(tmp%i==0) p[++tot]=i;
        while(tmp%i==0)
        {
            cnt[tot]++;
            tmp/=i;
        }
    }
    if(tmp!=1) p[++tot]=tmp,cnt[tot]++;
    
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 months ago, # ^ |
    Rev. 6   Vote: I like it 0 Vote: I do not like it

    I sorry to say that you way is half correct.

    If the number is small, you solution can solve it.

    The way you check prime number and the way you calculate all the prime factors is a bit slow.

    here's how I get prime factors.

    cin>>n;
    for(int i=2;i*i<=n;i++) 
    {
        while(n%i==0)
        {
            cnt[i]++;
            n/=i;
        }
    }
    if(n!=1) cnt[n]++,n=1;
    

    the most improtant part is i*i<=n. you only to check O(sqrt(n)) time.

    the if after is also necessary.

    For example n=21, first you get 7 after /3. Then quit the loop. But 7 is a prime factor. So if n!=1 after the loop then n must be a prime factor and it only appeared once.

    You can try some number and have a deeper understanding.

    This solution is O(sqrt(n)). There are faster solution but you need to learn more. Like how to get prime number from (1 to n) in O(n).

    I hope this will help you.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you very much i knew that my method for checking the prime is inefficient but i didnt know that my way to calculate all the prime factors is also slow thank you now i will try again using ur method.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you tell the algorithm to get prime number from (1 to n) in O(n). I am beginner, would be helpful

»
7 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    They are obviously not the same thing

    $$$(5+2)\operatorname{mod}7=0$$$
    $$$(5+1)\operatorname{mod}7+1=6+1=7$$$
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much! It is very helpful. Now I realised it is a mathematical error.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't know whether this is you problem.

    In the first way, 0<=(i+2)%n<n

    In the second way, 0<=(i+1)%n<n , 1<=(i+1)%n+1<=n

    So your output has a zero. You need to place that +1 after modulo to get value from (1 to n).

    For example you want to get random number from (1 to 10). you need to write rand()%10+1 instead of rand()%10 or (rand()+1)%10. There is a difference

    Is this you problem or I misunderstand it.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, exactly! Your explanation is very clear. Thank you for your attention!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use n-1 edges to build a tree first (link u[i] to v[i] if they are not connected) (or u[i] to v[i] is the 'last edge')

    then transform the un-root tree to a root tree

    the 'last edge' is from u to v

    then the cycle is (root to u),(u to v),(v to root)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't know if it's really well known approach in general but it works very well for me when you need to calculate something on functional graphs.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am also failing this very case, although I am using two pointers and a heap for the middle section

    https://codeforces.com/contest/1454/submission/101139553

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Sorry for late, actually by using two pointer's method you will be in dilemma if suppose right boundary of first segment is having greater or equal element next to it and similarly for third segment it's left boundary has element greater or equal to it to its immediate left. Which one you will increment l pointer or decrement r pointer. U can try this testcase: 6 elements-> 3,4,3,1,3,3 U will understand the fault.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah i see, is there a way to fix this problem?

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No,I don't think so because our approach has no proof i tried like to first increment l++ in case of case mentioned above and in one case i decremented j--;but still i got wa on 3500 testcase.So yes method is wrong and it no proof.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The approach of problem E is topo sort in graph, that is a classic algorithm in graph theory.
But the article says: "without any graph algorithms". I think that is not right.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please have a look, whats going wrong here in problem D:100094748

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to use precision in double without rounding off in c++ ?? Ex , double a = 1.9999999 and I want 'a' to be 1.99

can anyone help me??

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell where am I going wrong? This is my code. Its going wrong for the test case — 10000000000, where the code is printing — 5 5 ..(9 times) 5120 — whereas the correct answer is 10000000000 itself, which I am not getting.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell me why is my solution giving TLE in test 2 in B? 100459042

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone help me out with F? I'm getting WA and I'm not sure whether there's a problem in my logic or my implementation. Thanks!

Edit: found the mistake

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Using heaps and 2 pointers, can someone explain the flaw in my logic? I have one pointer for the end of the left, one pointer for the start of the right, a heap for the middle. If the left side's max is smaller than the right side's max, I expand the left side. If the right side's max is smaller than the left side's max, i expand the right side. If both are same, I check to make sure I am not taking anything greater than the triple max (max element with 3 or more frequency). If I am taking exactly equal to triple max, I make sure that there is at least one triple max element remaining in middle and at least one remaining for the opposite side.

https://codeforces.com/problemset/submission/1454/101141810

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In E, Why there are $$$\frac{cnt_{v}(cnt_{v} - 1)}{2}$$$ paths and $$$cnt_{v} * (n - cnt_{v})$$$ paths that go out of the tree. Can someone elaborate this for me?