Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

vovuh's blog

By vovuh, history, 4 weeks ago, translation, In English,

<almost-copy-pasted-part>

Hello! Codeforces Round #615 (Div. 3) will start at Jan/22/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria ZeroAmbition Stepanova, Mikhail pikmike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

This is unusual, but good news! Our friends at Harbour.Space have a message for you:

Hello Muscat

Hi Codeforces!

As a special prize for the Codeforces Round #615, we would like to invite the top 3 participants to take part in our Hello Muscat ICPC Programming Bootcamp, which will take place in Oman, from March 19 to March 25, 2020. The prize will cover the participation fee, accommodation, and half-board meals for the entire duration of the bootcamp (except flights)!

There are three requirements to satisfy:

  • You took part in at least 10 rated contests on Codeforces
  • Your max rating should be less than 1900
  • You should be eligible for ICPC and/or IOI 2020+
Fill out the form→

So unofficial participants are also in a game (if meet the requirements).

Good luck to everyone!

UPD: I want to thank Artem Rox Plotkin and Dmitrii _overrated_ Umnov for invaluable help with the round preparation!

UPD2: Editorial is published!

 
 
 
 
  • Vote: I like it
  • +220
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

First comment!!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

**hope i will be cyan after contest **

»
4 weeks ago, # |
Rev. 3   Vote: I like it -13 Vote: I do not like it

Queueeeeeeeeeeeee.

»
4 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +51 Vote: I do not like it

codeforces: Div.3 contest
me: Let's get a speed performance check.

»
4 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

Why is vovuh always in the makers of div3 rounds(This does not happen in div 2 rounds).

No complains, just curiosity.

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

    I think that is so because vovuh started Div. 3 competitions. Not sure though....

»
4 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Why someone sumbit a wrong solution on purpose then hack his solution ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe they wanted to be at the top of the hackers during the hacking phase.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if so, what they will gain ?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What will they lose either? (Don't say rating as its probably their fake ID)

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Again into the ashes

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think smarter requirements are needed for prizes in order to get rid of smurfing.

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

15000 participants but 100 upvotes?

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

Hope to become cyan. Hey rising_from_the_ashes! I felt in love with your handle!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I hope to become blue idk how the scoring works

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you are unrated for this contest as you are not trusted participant. Read this.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        my rating is <1600

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          but you haven't participated in more than 2 rated contest.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            am I reading it wrong? if you are <1600 the contest is rated.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm still cyan but I made good progress

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hey, you can install its browser extension so that u will get an estimate that ur rating is going to change by how much

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think I will just wait to see what happens. Though the site is very unstable currently (last round only took 2 hours for ratings to change)

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

          The site's not unstable, this round has a hacking phase that goes on for 12 hours after the contest. As successful hacks can change the results, standings are subject to change during the phase, and thus rating is not updated because rankings can change. Rating will update (relatively) shortly after the phase ends.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            the site is unstable for me as I tried to submit stuff 2 hrs ago and I was getting 502 error pages didn't last round have hacking phase too?

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Want to become cyan after this round.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys! please answer me. How to tag someone by its handle in codeforces?

»
4 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

I hope to successfully give contest in guu health and vitaliti. And hopefully get me some bobs and vagene.

»
4 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

3bmcws.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why i can't register now?

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

    there is many a times constraint in CF contest that you have to register atleast 5 min before the contest start

»
4 weeks ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

Hey, in my test 1 in problem C, i have a correct answer, but it's WA because my a[1] and n are dupcilate. Is it a bug in my test?

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Long Queue!

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Please do something about the long queue time. Thank you!

»
4 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Queueforces!!!

»
4 weeks ago, # |
  Vote: I like it +63 Vote: I do not like it

»
4 weeks ago, # |
Rev. 5   Vote: I like it -28 Vote: I do not like it

{Deleted}

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    There is no reason to kill yourself right now because of some computer not working properly, you will die somewhen anyway

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but the contest was extended 10 minutes

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

anybody know how to solve E ?

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

    solve each column seperately. calculate how many steps of move 1 if you do k steps of move 2

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

    Solve for each column independently. For each shift

    $$$0 \le s \lt n$$$

    , count how many numbers will match their intended positions after shifting (let it be $$$f_i$$$ for a shift by $$$i$$$).
    Hint

    Then, for a fixed column, the answer is the minimum over all

    $$$n - f_i + i$$$

    , and the total answer is the sum of those.
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C ?

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

    Get all prime divisors of the given number. To calculate first number Fix the first number as the very first prime number.

    To calculate second number: Start multiplying from next prime number onwards until the product becomes greater than first number.

    To calculate third number: Product of all the remaining prime numbers.

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

    Find all divisors of n.

    Than brute over all pairs of divisors and let that number be a, b.

    Than c = n/(a*b); if c is not divisible by that multiplication than don't select this pair. else you have found your answer.

    My Submission

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sqrt(n) * sqrt(n) brute force My submission . Recall that you can always find pairs of factors of a composite number by iterating to sqrt(n).

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

    Project Euler style problem! Can be done without prime divisors list. Iterate over all c for c*c <= n. If c divides n, let ab = n / c. Iterate over all b for b*b <= ab. If b divides ab, let a = ab / b. Ensure a, b, c distinct.

    c is at most sqrt(n), b is at most sqrt(c), so algorithm is O(n^3/4) time

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      don't you think 100(no of test cases)*10^(6.5)(if every number is 1 billion) would not pass in the given time limit at it is approx. 10^8.5.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think the estimate is conservative as most numbers will terminate much quicker (it is still good to think about worst case for hacking). But as a rule of thumb, with a fast language (C/C++) a computer can do 10^8 or 10^9 computations a second.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Simple and clear solution in 3 steps :
    1. find all divisors of n greater than or equal to 2.
    2. brute force the divisors using 3 loops and check whether you can get those 3 numbers say a,b,c such that a*b*c ==n and a!=b && b!=c && a!=c .If you got these 3 numbers then flag = true and break from all three loops.
    3.If flag is true then print yes and a,b,c else print no . for further reference see my code by clicking on C.cpp : C.cpp

  • »
    »
    4 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Greedy approach; let sq = sqrt(n) iterate i from 2 to sq, if n is divisible by i, store i in vector then divide n by i. Outside loop,if the vector size is 2 while looping, instantly break. if vector size < 2, print false. Else check if n(after loop) is not equal to numbers we push to vector and not equal to 1. If false then no, or else the answer is 2 numbers in vector and n that we get after looped.69322228

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The initial observation is 2*3*4 is the minimum value from which we can have valuable answers .After skipping those , my idea is to find two numbers a,b such that a*b = n . Then find two numbers i,b such that b%i==0 and i!=a so that we can assign value of i to b and (b/i) to c .

    #include<iostream>
    #include<bits/stdc++.h>
    #define int long long
    #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    using namespace std;
    int32_t main()
    {
    	fast;
    	int t;
    	cin >> t;
    	while(t--)
    	{
    		int n;
    		cin >> n;
    		if(n<24){
    			cout<<"NO";
    		}
    		else{
    			vector<int>v;
    			int a=0,b=0,c=0;
    			for(int i = 2 ; i<sqrt(n) ; i++ ){
    				if(n%i==0){
    					a = i;
    					b = n/i;
    					break;	
    				}
    			}
    			for(int i = 2 ; i<sqrt(b) ; i++ ){
    				if(b%i==0 && i!=a){
    					c = b/i;
    					b = i;	
    					break;
    				}
    			}
    			if(a!=0 && b!=0 && c!=0 && a!=b && a!=c && b!=c){
    				cout<<"YES"<<'\n'<<a<<' '<<b<<' '<<c;
    			}
    			else{
    				cout<<"NO";
    			}
    		}
    		cout<<'\n';
    	}
    }
    
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you lock your submission? I could not see the lock icon anywhere on the dashboard for the problems I solved.

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

    Submissions ran on system tests directly, so there are not pretests and options related to, like hacks and locking problem

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So for this contest there was no hacking phase? Sorry to ask stupid questions but I am new to this.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Just like me boy!

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why does it say "and after the round it will be a 12-hour phase of open hacks" in the blog?

»
4 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

Since I'm not an old user of codeforces, it's the first time that I experienced something like this(tooooo long quotes). I think it's not right to blame CF, 'cause I'm sure that these kind of issues are not more than fingers of hand through CF history. Any way #unrate_615

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

how many number of divisors number has in problem c. In worst case.

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

    Try number 734033887

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It works for 30. which has 3 distint divisors 2,3,5

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        srry. My mean was this case divisor of 734033887 are : {1, 5009, 146543, 734033887}; if we take 5009, 146543 as first and second value , we don't have 3'rd option to take instead of 1 which is < 2

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You have missed the case where there are only two primes and both of their power is 2. For example : 36. Your code returns NO. But there is an answer : 2, 3, 6

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Haven't completely checked your code but you over-complicated the problem while the constraints aren't that big.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I simply do prime factorization of number.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try 1 36

    Answer exists 2, 3 and 6

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the 11th test in D? Why did my program fail it?

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

My approach for E: Process each column separately .For every column calculate cost for every possible rotation. For calculating the cost of every rotation loop through every value and find out for which rotation this element is at its correct position,and decrement the required no. of operation for that particular rotation by 1 .Choose rotation which require minimum operations .

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

Thanks for the contest!

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

guys i know that my question is not related to the constest, but how can I figure out users that I'm in their friends?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand where I went wrong in Problem C. My Solution Thanks in advance

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Your code is too long,I think you should learn to write concise code

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I use std::set to matain the answer, and the code is pretty short and clear, here's my submission:69350130.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    even shorter code by maintaining the count of remainders

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did something stupid but the key idea is that the values only matter mod x. So we keep counts of 0 to x-1 mod x. The MEX can be computed greedily by trying to increment MEX and decrementing counts as we go.

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

    D was simple but little tricky for me. Let's say dp[i] contains what is the max MEX value till ith query. and let's say it is K;

    Now since dp[i]=K, it implies that we were unable to generate K from previous numbers till now. So for the (i+1)th query_number we will try to generate the Number K onwards(including it) so that our max value of MEX become greater than previous and best possible till now.

    Now lets say K=ax+r so K can be generated iff there exist a query_number previously of the form Z=bx+r so that you can just add or subtract +/-(a-b)x to Z depending on whether a>b or b>a in order to get K.

    SO you can feel now that there is no need of actual query_number n... we just need n%x — remainder. so just create array of size x. and play with remainder...

    Here is code

    Spoiler

    My_submission

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

    Maintain array $$$B$$$, indexed from

    $$$[0, x)$$$

    . Initially,

    $$$B[i] = i$$$

    .

    For each query, do

    $$$B[y_j \text{ mod } x] \text{ += } x$$$

    . The answer after each query is the minimum value of $$$B$$$; however finding the minimum naively would be too slow (

    $$$O(qx)$$$

    over all queries). We could use a segment tree, or even just an ordered set (for each query, remove

    $$$B[i]$$$

    from the set, update

    $$$B[i]$$$

    , then add it back to the set. $$$B$$$'s values would always be distinct), to reduce it to

    $$$O((x + q) \log x)$$$

    , which should pass. Do be careful about overflow; either use 64-bit integers or stop updating an index if it exceeds a threshold

    $$$> q$$$

    .

    This works because it is always optimal to change each

    $$$y_j$$$

    to the minimum possible non-negative value not already in $$$A$$$ (the array in the problem description), and

    $$$B[i]$$$

    represents the minimum non-negative value $$$b$$$ where

    $$$b \text{ mod } x = i$$$

    and

    $$$b \notin A$$$

    .
»
4 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

How to solve D?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The question becomes easy when you observe that a number when added to x or subtracted to x, it's modulo w.r.t 'x' remains the same.

    Now, you just need to maintain precomputed of first % 'x' numbers, i.e from 0 to x — 1.Let's say this array as 'a'. Now, whenever a number comes. Find its modulo w.r.t 'x', and maintain a map or set, to check whether that number has come before.

    if you use this number, let's say y. then increase that number in your precomputed array i.e a[y] += x.

    Why? Because whenever a number will come, it will be holding place for next place of that modulo multiplicity.

    I tried my best to explain to you. Take a look at my submission, you will get more idea.

    My Submission

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is the time complexity of your solution in worst case?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to try on the hack? Its showing Illegal contest ID on clicking on 'Hack it!'

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

    I think there's no hacking phase. 'cause the solutions ran on system tests directly, and not pretests

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

      On div3 there is always a 12-hour hacking phase

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

        Oh, so you do not need to LOCK your solution in Div3.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Locks are available in div1/div2 contests, not in div3 contests. You can read the rules of div3 to get more information

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    to hack in div 3 open the solution of whom you want to hack and on the top right by clicking on "hack it" you will be directed to test case window where you can put the hack test case.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

when will editorial come

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Presumably sometime after the 12 hour hacking phase ends

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Who can explain to me why in my solution to Problem D I have to use long long.

the code:https://codeforces.com/contest/1294/submission/69352519

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Where it is mentioned in problem D that we can increase or decrease one element in an operation more than once?? I mean a[i]-m*x or a[i]+m*x is possible for m>1 also in one single operation????

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Very similar to Problem F ?

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

    Yes and the author is my teammate sonu628. Unfortunately I couldn't solve it. ;_;

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

      Never mind, I could not solve it either, even after solving it in the contest. I assumed the diameter of a linear tree = n (thus WA 39) :(

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

    Didn't expect someone will remember :)

    P.S:- feeling happy ;)

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

Hacks for C?

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem F, what is wrong with this approach? First, I find a diameter and choose a and b as the ends of that diameter. Then, I banned every edge between a and b and create the new graph. After that, I run DFS from every vertex between a and b. Finally, I choose c as the vertex whose depth is higher (depth 0 is also considered, in that case c is between a and b). This was my submission.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    I didnt read your code but your approach is O(n^2) you can simply do a multisource bfs.

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

      Once I have erased the edges between the nodes in the diameter, I have a forest in which I have a tree rooted on each node and running DFS from them is O(V + E)

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

      Can you please explain your Multi-Source BFS Approach ?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Its also basically the bfs, but initially in queue you have to put all the nodes whose distance is initially 0, also make their distance 0 initially. Now in the while loop instead of queue having a single node it will have many nodes with distances 0. The time complexity is same since it traverses whole graph, maintaining correct distances i.e O(V+E) .

        Now in this particular question after finding the diameter ends,for all the nodes in their path make their distance 0, and run multi-sources bfs to get the third node which is farthest from the path.

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

    TRY this case:

    12 11

    1 2

    2 3

    3 4

    1 5

    5 6

    6 7

    1 8

    8 9

    9 10

    8 11

    8 12

    I think the answer is 9 but your approach will give 10.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      please ignore. my bad. your approach will also give 9

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Don't worry, thanks. I got AC. The approach was right, I had a bug of using the name of the variable temp instead of diameter in my loop.

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

69357392 I know my code is not that clean, but please check it for my bug on B!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    anyone!? ;_;

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Irrelevant comments: checking bounds, n=1 case, and ans=="YES" is not needed. The points can be sorted destructively. Once points are sorted lexicographically we can perform the yes/no check with one coordinate. Between two points you only need some Rs followed by some Us. idk what the last output R is.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, what does "in one move" mean? It means increase or decrease any element of the array only one time or any? I asked my friend after contest, he said any. Did i forgot something?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    One move means increase/decrease one element once, but since they give you unlimited moves, you in effect can do unlimited increases/decreases.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I mean why unlimitedly moving not declared in detail?

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Approach for D?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just count remainder of X.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    simplest way I can think to explain D

    #include<bits/stdc++.h>
    #include <utility>
    using namespace std;
    typedef long long int ll;
    
    int main()
    {
     ll q,x,i,j,k,l,m,o,p,t;
     cin>>t>>x;
     set<pair<ll,ll>> se;
      for(i=0;i<x;i++)
      {
          se.insert(make_pair(0,i));
      }
      map<ll,ll> mp;
      while(t--)
      {
          cin>>i;
          l=mp[i%x];
    
          se.erase(make_pair(l,i%x));
          mp[i%x]++;
          se.insert(make_pair(mp[i%x],i%x));
        //  cout<<(*(se.begin())).first<<(*se.begin()).second<<"dekh le\n";
          cout<<x*(*(se.begin())).first+(*se.begin()).second<<endl;
      }
    }
    
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I really liked this Div 3 round. Especially how Mathematical C and D were. And that there were only 6 distinct problems.

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

    Agreed, I come from Project Euler background so it is familiar

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Great. How many problems did you solve on Project Euler ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there anyone else with E failing on Test 8 ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve E? I heard that it is greedy, but i can't understand. Why greedy works? :(

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

    while traversing in each column(say j), if any element(x) is found which belong to column j in the final matrix. Then find no of moves required in the cyclic shift of this column so that x reaches to its correct position.

    Maintain a map[mv,fre]

    mv: no of moves required so that x reaches to its correct position in the cyclic shift.

    fre: frequency of such elements which reaches to its correct position after mv moves in the cyclic shift.

    Now, for each column min no of moves required(say min_col) is the n-max(difference between freq and mv). So the ans is sum of all min_col

    For better understanding have a look

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody help me with the testcase on which my soln is failing

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hello all. My code for problem C gives the wrong answer on test case #2. Here is what I am doing: a) Find the "first" divisor of n greater than equal to 2. b) Find the "second" divisor which is not equal to the first divisor if possible. c) If possible then check if n/(first*second) is >= 2. d) If not possible then there is only one divisor >= 2 of n except itself. Then choose "second" = (first*first) and check if triplet is possible.

Please Help!![submission:69361400]

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

    Sure, try $$$100$$$ as test case. According to your code, your first divisor is $$$2$$$ and the second one is $$$4$$$, so you check if $$$4$$$ divides $$$50$$$ and that gives you NO, you should choose a divisor after extracting the previous one. Also, your code is

    $$$O(t*n)$$$

    and

    $$$n \leq 10^9$$$

    and

    $$$t \leq 100$$$

    , so it will give you TLE.
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

what is the hack for C ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Idk, but maybe it's due to the timeout since most of the hacked code got over 1900ms...

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test case 8 in E??

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hi guys can anyone tall me how to solve C? I don't understand why it always is optimal to try first divisor of n

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    find all prime factors with their respective powers in sqrt(n) time then check three cases case 1. no. of prime factors are more than3 answer always exist and it is any combination you can pick up then

    case 2 only 2 prime factors but their total power is greater than or equal to 4 then answer exist else no. (a,b,a^x*b^y)

    case 3 only 1 prime factor available then check if its power>=6 (a,a^2 a^3) then answer always exist else no.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I also wrote my solution based on same logic, except that I was considering for case 2 that the sum of powers should be greater than equal to 3

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We just need to find 2 different divisors such that one of them is a composite one with again 2 different divisors and also you need to check that they are greater 1.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hmmmm you can list all of divisors of N, the max numbers of divisor of N is 100 (if N == 1e9) so you can use O(N^3), right? Use 3 loops and check every divisor by conditions of problem

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

      Not exactly n³ because no. Of divisors are way to less for numbers <= 1e9.Its not 100 but around 1700-1900 i guess

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

        you can check it! numbers of divisors of 1e9 is 100, I tried it before I wrote my solution

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

          Any number less than 1e9 has not more than 1344 divisors, with 735134400 having exactly that many. Actually, it is reasonable to estimate the number of divisors as cbroot n for small numbers (even though it asymptotically grows slower than any polynomial).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys, I am confused about the Problem D. In the example it states that: "After the fourth query, the array is a=[0,1,2,2]: you don't need to perform any operations, maximum possible MEX is 3 (you can't make it greater with operations)." __ However, if we add one to the last element will get a=[0,1,2,3] which I think has a MEX of 4. Can someone explain me why adding one to the last element does not improve the MEX?

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

    You can add only number x. In this testcase x equals to 3, so u cant add 1, u can add only 3 as many times as you want

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks man, I totally overlook such requirement.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Whats testcase 3 of problem F?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This testcase worked for me:

    Input
    Output
»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

No hacking in this Round? I am getting Illegal contest ID.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

any idea to solve problm D please ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

when will be editorial will be up?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When the ratings will be updated?-

»
4 weeks ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Whoops, looks like I submitted a solution for 1294E - Obtain a Permutation that has an error in it not covered by the testing suite, but it's too late to hack it: 69397747

Spoiler
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I have hacked it now with the sample you provided

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I think I am the only one who solved C via Miller-Rabin.

It proves that it is no use to think the problems as too difficulty in div3 rounds

»
4 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

I have created the video solution for the first four problems, explaining my understanding and approach for the same. Codeforces 615 DIv3 Video editorials

Do like comment, share, subscribe if you like the video. Do subscribe for more such content

Happy Coding

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Man are ducking serious, first four problems are super easy, there is no need to make a whole video explaining them. Besides why didnt you explain all the problems? Are they too tough for you?

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

I think your test cases for 1294E - Obtain a Permutation is too weak. 69353056 Shows: Output: 0 For Input: 4 4 5 2 3 4 Where the actual result is: 1

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

Huge gap between next contest....... Please decrease the gap

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

I got a mail from codeforces because my submission matched with someone.I am giving you a guarantee that it became co-insidently.i saw this code(question B) before in my collage fest at DAIICT,Gandhinagar,India.So please give me rating of my codes. thaks...........

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Sahil_M is also my collage mate and he was also there in fest.so co-insidently this thing happened.

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I am sorry I participated in the round with 2 personal users (7ouda,7ooda) and I don't know that it's rules violation.

»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Hi dear,

I participated in Codeforces Round #615 (Div. 3) with my 2 personal handle (7ouda,7ooda) and submitted same solutions so my submissions was skipped, and I didn't know that it's a rules violation, so please can you help me.

Thanks, Mahmoud.