DK318's blog

By DK318, 3 weeks ago, translation, In English

Hello, Codeforces!

We, DK318 and unreal.eugene, are students of ITMO University. And we have recently joined the developers team of Codeforces and Polygon. We have prepared this round for more careful acquaintance with Polygon. Very soon you will be able to see the first results of our work as developers.

Except us, in round development participated MikeMirzayanov, geranazavr555 and doreshnikov. We hope that you will enjoy the competition!

Codeforces Round #731 (Div. 3) will start at Jul/10/2021 17:35 (Moscow time). You will be offered 7 problems 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 a 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 7 problems and 2 hours 15 minutes 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 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 I_Remember_Olya_ashmelev, 1-gon, CtrlAlt, Tzak, FelixArg, antontrygubO_o, bugdone and brian for testing the round and improving tasks.

Good luck!

UPD 1

Editorial.

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

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

I hope i could never give div 3 rounds officially after this :)

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

    Good luck! Actually, there will be many little guys of my school participate this round tomorrow. Hope everyone can learn and enjoy from this round! :)

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

    hope you achieve your goal, bro.

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

    The feeling is mutual.

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

    So a participant new to codeforces is not a trusted participant right!

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

Hoping to get positive delta on my birthday!

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

I hope i solve A faster and not quit from contest.

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

Hope to get the cyan color again on my profile :) after this round .

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

Hope to be expert for the first time in my life. (UPD: WOW, DREAM COME TRUE)

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

    Yeah,wish you and me good luck. I hope to be expert for the first time in my life too!

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

      I have been expert once: it is fantastic. You should absolutely try this life experience too, good luck!

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

    Dream come true for me too!!

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

Hopeforces

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

Hope I finally leave this drab, lifeless colour behind

»
3 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

After ages photo-2021-07-09-20-41-38

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

Hope I can enjoy the contest and get my first in-round-full-solve :)

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

I was just wondering why Mike Mirzayanov never give any contest!!

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

    While best coders are grinding to get one black letter, Mike is casually sitting with full black nickname

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

      the user has to be an IGM to have one black letter?

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

    Mike is most likely occasionally participating in some contests hosted on the other platforms. At least that's how I interpreted his blog post posted two months ago.

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

    Coaches don't play!

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

Hope to get my nickname colored

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

Hope to become blue this time :)

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

Hope I will continue hoping after this hopeful contest.

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

![ ]()

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

I was wondering who can create contests and how do you do it?

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

Hopefully I hope to hope

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

Hope to reach Pupil soon

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

Hope i will learn some important thing from hopeful contest

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

Hope

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

2 contests back to back! Hoping to have a good weekend...

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

Hope that I will gain confidence after this.

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

orz

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

Hope to gain some confidence after a string of disastrous rounds.

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

I hope to become an LGM after this round.

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

My first unrated contest ><. Feels awkward tbh, after giving every contest to gain rating.

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

After losing Codeforces Round #730 (Div. 2). Now it's time to take revenge from Codeforces Round #731 (Div. 3)

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

I hope I could touch 1500 mark after this round. Good luck to everyone

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

I have never done more than 3 problems in competitions :((

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

Hope that this round would be less of mathematics as compared to past few rounds

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

hope i will solve atlest 2 in this round. Don't ruin my hope with math plz!!

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

Much waited for this but Clashing with Leetcode :( ,anyways preferred cf over all others :)

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

Is pupil possible for me after this round ?. Current Rating : 1064

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

I hope I can get rid of four questions

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

O, new authors, cool. This Div 3 promises to be interesting.

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

I got one wrong answer in the last div3 round because of just one #define int long long ,hope not to repeat the same mistake again.

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

    How can using long long instead of int cause WA?

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

Div3 is always High Hopes

Spoiler
»
3 weeks ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Hope to become green this time :p

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

Oh no.. I have to read for tomorrow's exam. But today is my long awaited Div 3 contest. Confused which to choose!

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

Hope to solve more than two problems

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

Good Luck Everyone

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

Another chance to dye my name Blue (or Green?)

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

Wishing best to the new authors ! Hope they wont let me miss vovuh div3s

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

Hope to slove from A--> D this time :(

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

Hope to be specialist in this round

»
3 weeks ago, # |
  Vote: I like it -71 Vote: I do not like it

can some some tell me how can i optmised the little bit so that it may runfaster link


//SATYAM SINGH #include<iostream> #include<bits/stdc++.h> using namespace std; #define ll long long int #define pb push_back #define mod 1000000007 #define inf 1e18 #define ump unordered_map #define mp make_pair #define all(v) v.begin(),v.end() #define inpv(v,n) for(int i=0;i<n;i++) cin>>v[i] #define outv(v) for(auto i:v) cout<<i<<' ' #define loop(i,a,b) for(int i=(a);i<(b);i++) #define looprev(i,a,b) for(int i=(a);i>=0;i--) #define log(args...) {string _s = #args ;replace(_s.begin(),_s.end(),',',' ') ; stringstream _ss(_s); istream_iterator<string> _it(_ss) ; err(_it,args);} void err(istream_iterator<string> it) {} template<typename T,typename ... Args> void err(istream_iterator<string> it, T a,Args... args) { cout<<*it<<" = "<<a<<endl; err(++it,args...); } void file_i_o() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } void dfs(unordered_map<int,bool>&visited,int src,int &count,vector<int>adj[]) { visited[src] = true; count++; for(auto i:adj[src]) { if(not visited[i]) { dfs(visited,i,count,adj); } } } void solve(vector<int>&comp,vector<int>adj[],int n){ unordered_map<int,bool>visited; for(int i=0;i<n;i++){ int count = 0; if(not visited[i]) { dfs(visited,i,count,adj); comp.pb(count); } } } int main( ) { clock_t begin = clock(); // file_i_o(); // Write your code here.... int n,m; cin>>n>>m; vector<int>v[n]; loop(i,0,m){ int a,b; cin>>a>>b; v[a].pb(b); v[b].pb(a); } vector<int>comp; solve(comp,v,n); ll ans =0; for(int i=0;i<comp.size()-1;i++) { for(int j=i+1;j<comp.size();j++) { ans+=comp[i]*comp[j]; } } cout<<ans<<endl; // code ends here !!!!!! #ifndef ONLINE_JUDGE clock_t end = clock(); // cout<<"\n\nExecuted In: "<<double(end - begin) / CLOCKS_PER_SEC*100<<" seconds"; #endif return 0; }
»
3 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

No . of question = 7 Hope = h h>=1

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

I really like these problems. Thank you for this round!

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

guess it's time to finally learn bit operations lol

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

Bring back King vovuh

vovuh orz

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

UUFCK

REKEHTMORFUC

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

This is the first time I pass all problem's pretest in one round. Thanks for this round!

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

I used SCC compression in problem G. I wonder if this is an overkill.

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

    i dont know what youre talking about so i think it is. You can just do dfs and not pass through a vertex twice if it has infinite paths

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

      Could you elaborate on that? Do you mean just calculate the SCCs and then bfs out or something like that only counting the first two visits? Or do you mean avoiding SCCs altogether.

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

        Ok so my idea is that you do a dfs and mantain which vertices were in the path of the current path of the dfs. If you can go from that vertice v to a vertice p on the dfs path from 1 to v, then p has infinite paths to it.

        Then, you can call a dfs to p like it would normally do and for each vertice it goes through you mark that vertice as also having infinite paths. This doesn't explode into insanity because as mentioned in the other comment you can choose not to go on vertices marked as having infinite paths (you will pass at most twice for each vertice).

        You can also mark the other types of values like having 1, more than 1 or no paths pretty easily as well

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

    Yeah I also modified some scc compression code to solve this problem but it does feel overkill for a Div3.

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

      xD I used that same reference code when writing my solution. Definitely felt overkill, I've only seen SCC actually required on like GM+ level problems.

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

    Can you comment what is wrong in this solution?

    I was trying to make topological order of this graph, the nodes that do not appear in this are in some cycle. Then I found the number of paths of nodes in topological order and the nodes that are in cycle and get -1 ,if they are connected to 1, else 0. WA submission

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

    I also used SCC compression to get the dag. Then using bfs to count 2 visits at max. Then using if any node in a single SCC containing multiple nodes is reachable then all nodes present in that SCC are -1. Then every node which are reachable from those -1 nodes are also -1. This can be found using multisource bfs with the -1 nodes. Don't know if it is overkill.

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

Gud contest, the problems were amazing. I wasn't able to solve full of it but that's okay though.

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

Couldn't solve E. But the contest was amazing. Liked the problems... Any hints for E?

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

    You can see that after each move each array in A will contain one more element of it in the initial array. SO after n move => every element in A will contain the gcd of n + 1 element in the initial array (that's the worst case). If after k moves and we have an array which all of its elements are equals then that will also true for k + 1 and so on. So the main ideal here is to do a binary search on k and use sparse table to calculate the gcd from l to r in O(1) to make sure the complexity is O(nlogn). (sorry for my bad en)

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

      This is for prob F, anyway Thanks :) I waited for this

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

    I solved it using two stacks. Maintained the minimum (t[i]-a[i]) for left and minimum (t[i]+a[i]) for right at the top of the stack. After that, it's pretty straightforward.

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

    Editorial coming soon

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

    just for every air conditioner move as long as u can to left and right (u can't when actual value is less then proposed by your conditioner)

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

    Can use multisource shortest path kinda thing for E..

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

    Finally solved right after contest ended, woof.

    hint 1
    hint 2
    hint 3
    actual spoiler

    edit: ha, I am slow in so many ways today

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

    Actually, after a lot of thinking, I realized that the solution of E is pretty straightforward.

    We need to scroll from left to right, maintain the answer, and scroll from right to left and maintain the answer. It doesn't matter which way we scroll first.

    My solution LINK

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

    make a prefix and suffix array and print the minimum value...min( smallest value or prefix array , smallest value of suffix array) and the main thing is that how prefix and suffix array works.

    Make an array 'store' of size n+1 and initialized with infinity,when you take the input update the temperature of store[i] ( like ith index has 'x' temperature, store[i]=x ) now make a prefix array and initialized with infinity the optimal value for prefix[i]=min({prefix[i],prefix[i-1]+1,store[i]}); because it may be possible that current value is optimal or if prefix[i-1] is more optimal so we need to add one in prefix[i-1] or it may be possible that store[i] has optimal tempetature.

    And the time complexity is just O(n).

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

I have solved Problem F using Segment Tree + Binary Search. Anyone who has solved this with the same approach? Just want to know.

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

    I thought the same but was really solving slow this contest!

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

    You can use a sparse table since the array is static. Mine passed in 155 ms. 121971699

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

      Probably worth noting that $$$O(1)$$$ sparse table queries work here because gcd is idempotent.

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

    I used Sparse table + Binary search but I think segment tree should be sufficient. Because the time complexity of your algorithm should be O(nlog^3(n)) and n = 2e5, so you need 1.16*10^9 *C operations in total which should fit in the time constraints (4s).

    Upd:Forgot to include the gcd

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

      Mine didn't work. I tried Segment tree + binary search, but ended up with TLE. Had to change it to sparse table to get accepted.

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

        Hm I guess the constant for the segment tree and other operations is too big

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

      Correct me if I'm wrong, but how will segtree + binary search be $$$O(n log^2(n))$$$ here?

      We will have $$$O(log(n))$$$ steps of binary search. For each step, we will need to process the answer for $$$n$$$ positions. For each position, the segtree will make at most $$$O(log(n))$$$ "combinations" of answers of child nodes. Each of these combinations will require an $$$O(log (n))$$$ gcd operation. So won't the total be $$$O(n log^3(n))$$$? While this could still pass (needs around $$$10^9$$$ ops and 4s TL), it feels risky. Or are you using a different approach that only needs $$$O(n)$$$ queries of the segtree?

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

        Whoops, totally forgot about the gcd operations which costs O(logn) my bad

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

        doesn't exist a way to do binary search inside a seg tree? I think errichto mentioned something like that sometime. When you are in a node if gcd so far is small enough you try left at first, secondly right else you say the node is too big and you go up in the tree

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

        https://codeforces.cc/blog/entry/63771

        apparently lots of gcds chained are fast I also did segtree + binarysearch, passed with 1300ms

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

    i solved using segment tree + two pointer.

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

    I think I might be the only one with a non-binary search and non-segtree approach for F. Could not get AC so I'm not even sure if it's the right approach.

    1. Divide a[i]/ gcd(a[0],a[1],...a[n-1]);
    2. Concat array A with A to make A[1..N],A[1..n] of length 2n.
    3. Now we know that the final gcd will be 1. All we need to find now is for a particular prime P, what is the longest continuous segment in the array where all numbers are divisible by P.
    4. Final answer is, over all the primes, what is the length of maximum continuous segment as defined above.
    5. Start from the index 2n-1 and move left to index 0. We can store the maxContinuous length of each prime in a separate array and update it (+1 if divisible, 0 if not) as we move left.

    I couldn't get AC in time, but does the approach sound correct?

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

      I asked anandOza it is too slow there is many primes 70000n is too slow. but you can improve it not many primes appears a lot so you must remember at which index a prime appears and compute the longer interval on that (not confirmed solution though) but give it a try

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

        For any prime p at appears in a[i] (ie, a[i]%p = 0) ,if p appears in a[i+1] too, then continousLen[p]++. Else contiuousLen[p] = 1.

        This way you don't have to look at all the primes, but only those that are appearing in the number a[i]. We also update the maxLen over such primes only. Consider this similar to lazy updates.

        So this should effectively pass in the the TL. This would be O(N * |max number of primes in one number|) Does this make sense?

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

          it definitely make sense to me, that's beautiful

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

            Thanks. Unfortunately thought of at the last minute so no AC. But i'm glad you liked the solution.

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

was F binary search with segment trees

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

    that is how I solved it, yes

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

    There is a solution with Sparse Table.

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

    Simulate the process, but take adjacent equal values together as a pair of $$$(value, count)$$$

»
3 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

ReadingForces

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

Good contest

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

Choked so hard on F, had every single idea except for the right one until 15 minutes for the contest to end

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

Can someone explain what is wrong in my solution for problem E?

Code

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

can someone tell me why I am getting this error on C and what does it mean - wrong answer Cannot merge "a" and "b" to get given output (test case 1)

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

    Since we need to merge the actions of both programmers, we need to take actions (numbers) from already given sets i.e. 'a' and 'b' and merge them. So, every element from 'a' and 'b' must be present in your output, not more not less. Your output may have one or more of the following problems: - There maybe an extra element in your output or - Maybe some element is missing or - Maybe relative order of elements in 'a' or 'b' or both is being changed.

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

For me, problem statement in C was very big and boring, totally -> nice contest

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

This was a great contest. What was the idea on problem F? I only got to the point that the final array will have all elements = gcd(x1,x2,x3...xn). Can you tell me the thought process?

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

    After k processes, the element x_i will be: gcd(x_i ~ x_{i+k}). To calculate this, You can use sparse table.

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

Shouldn't problem B (Alphabetical Strings) be marked with the "two pointers" tag as well?

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

A and C felt somewhat bashy but otherwise contest was fine... G was a decent problem but I kept bricking on it until I realized I needed to change like two lines :| guess that's what I get for not learning SCC.

Curious on how people solved F -- I ended up using segtree but this is obviously not intended.

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

    How did you solve F with the help of seg-tree? Can you explain, please?

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

      After $$$k$$$ steps $$$a_i = \gcd(a_i, a_{i + 1}, \cdots, a_{i + k})$$$ (indices taken $$$\mod n$$$). Thus you can binary search on $$$k$$$ to get the answer.

      Since $$$a_i$$$ is equal to a $$$\gcd$$$ range in the original range, for a given $$$k$$$ we query this value for each $$$i$$$. Solution thus takes $$$O(\log n * n \log n) = O(n \log ^ 2 n)$$$. Look at my solution if you're curious about implementation.

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

        Wouldn't the gcd add another log factor? Or am I missing something?

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

          SecondThread was touching upon this in his stream, he claims that it wouldn't because of the nature of $$$\gcd$$$ decreasing at most $$$\log \text{max}(a_i)$$$ times before it'll reach $$$1$$$ (or something like that). I'm not really sure how the analysis works, maybe he can shed some light on it.

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

            Oh, I always assumed segtree gcd queries would take O(log2 n)

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

              I could be totally wrong here, but this is what I was thinking. Maybe some LGM who has a bigger brain can either confirm/deny this:

              So like, the GCD can only actually change log(n) times. Each time the GCD call goes one iteration deeper, that means that the answer will decrease by a factor of about 1.6, and this happens across all layers.

              The more general version of my hypothesis here is that: if you are calling the GCD with the result of previous calls n times, I think your runtime is really O(n + log(maxVal)), rather than O(n*log(maxVal)). I haven't heard other people say this before, so it might be some huge holes in my logic that makes it not true, but it seems cool enough to be interesting.

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

The number of accepted solutions increased gradual way.

Proves that Level of question increased in a very uniform way. Loved this !!!

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

    Even if the problems were all of the same difficulty you could see a similar pattern.

    Let's assume that everyone approaches the problems in alphabetical order, and that different coders solve problems at different speeds. The first problems will be solved by a lot of people, and the last ones only by a few very fast participants.

    The distribution of the number of accepted solutions is not a proof that the problem difficulty was increasing in a uniform way.

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

How to solve F ?

Few observations I made :

Answer is gcd of whole array call it g.

The steps for a element ai are-> gcd<ai,ai+1>,gcd<ai,ai+1,ai+2>,...gcd<ai,...an,a1,a2...ai-1>

The minimum step# which gives g in above sequence let that number be y.

Answer is maximum over all y for all i.

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

    Observe that After performing a minimum number of steps each element of array will be equal to the gcd of the array.

    I used a segment tree with binary search. Note that gcd never increases, So suppose if I am finding the minimum number of operations that are required to make this element equal to gcd, then I can do a binary search on range $$$[i,n]$$$. If we are unable to make the element equal to gcd then do a binary search in the range $$$[1,i-1]$$$

    Our answer is equal to the maximum operations that any element needs.

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

      Cool approach. We can also duplicate the array and do binary search on range [i,n+i-1] right? so no need to break it ig.

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

Does it take time for the rating to appear on my profile? Thanks

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

    You gotta at least wait for the hacking phase to end (for educational rounds and Div 3 rounds) and then it will take another few hours for the final system test to come, so basically you have to wait 12~24 hours. But for other rounds, it takes about 2 hours for the rating to be updated.

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

The problems were interesting with well-written statements and plenty of examples. Thank you for a good round!

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

I took a tiny step closer to be Green :)

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

I solved F without using segment tree/ sparse table/ binary search, although it may fail for some strong tests :(

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

Logical and clear questions. Nice contest

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

I cannot locate error in my submission for Problem C?

Submission: https://codeforces.cc/contest/1547/submission/121993312

Please help me out!

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

    imagine i=n, and it's possible to complete with b, your j will grow to m with the while and then make a runtime error in your else (in b[j]<=k) and the condition j<m, I think so it would work

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

Any idea for E?

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

    Create array of values and set every value to INT_MAX. For every air conditioner change its value to input value. Then for every air conditioner u go as far as u can to left and right. U stop if your value (air conditioner temp + distance of air conditioner) is bigger than actual value in array.

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

    Or simply go once in the array from left to right, ans[i]=min(ans[i], ans[i-1]+1)

    Then do the same from right to left.

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

      Damn, it was that easy, i wasted like 40 mins on it :/

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

I was 1199, and cf predictor shows -5. Seems like I'm the cursed one

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

    Which cf predictor are you using. Please share link.

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

    I think you might reach pupil :).

    CF predictors tend to show lower sometimes

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

I noticed that top-ranked guys solved the first several problems within 20 mins. I was like, how is that possible...

I'd say that I came up with the solutions once I understood what the problem was saying. And I also didn't get any WAs for those problem, which would incur delays. But it still took me about 50 mins :(.

Is there any special techniques other than reading/coding speed that makes those guys incredibly fast?

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

    What I have observed is that there are many factors behind their incredible speed.

    First of all, they are quick at thinking and realizing what needs to be done to solve the problem. That usually comes with practice and experience.

    Second thing is that apart from clear thought process, they have a much simpler and smaller implementation than most others.

    I am not sure about this one but I think that high speed also comes from reading and understanding problems fast, leaving out the irrelevant details and focusing on what is important to solve the problem, hence reducing the effective problem reading time.

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

Why rating changes from Codeforces 730 were reverted and again evaluated ? Anyone please answer..

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

    sometimes cheater are found afterwards and their standing is decrease, sometimes the contrary happens, someone proves he's not guilty. and so it's necessary to recompute the ratings (I earned 1 point more) somebody obfuscated his code maybe he was considered a cheater

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

I thought that problem C is a simple dfs but I got tle. Is there a specific pruning condition?

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

    It is more greedy like.

    You simulate the process, that is, whenever one of both people want to add a line, we add a line. Else the one with the smaller index changes that line.

    If there are not enough lines to change the current line then there is no solution.

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

hint/help for D

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

    think greedily what is the smallest value you can append to y. you start with 0. to know what the smallest think about each bit if it's needed

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

      You know that the first number x1 of the answer sequence is always 0. Find a1 xor x1. We know a2. How to find x2 using it and the result a1 xor x1. How exactly to find a number so that the sequence is lexicographically minimal? Can someone explain this in more detail? Thank you.

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

    Choose y[0]=0.

    Then choose for all subsequent y[i] the smallest possible value to set all bits of x[i-1]^y[i-1]

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

Something Weird happened with my submission for problem G, today. My initial submissions gave wrong answer on test 3 on submission. After the contest I found that the 4599th output of my answer differed from original answer. I made another submission and found that this was the test case my code was printing wrong answer to:
1
4 4
1 3
1 4
4 2
3 4
(Found using — this submission (See participants output for test case-3).
But when I ran this test case (in codeforces custom invocation) with my original solution it gave correct result, whatever was expected. (Original Submission Link).
Can someone help, where did I made the mistake. I am new to this platform, so any help would be appreciated.

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

Thanks for the round! Here's a link to my screencast.

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

Deleted

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

So after a long wait Division 3 contest is finally back. Solved 5 problems and I feel skipping the LeetCode Biweekly Contest 56 which was running at the same time as that of this contest was finally worth it!!

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

I Hope I reach another color this time .. just got bored from the gray color :(

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

    Is it really necessary to use a profile picture with a swastika?

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

      maybe this help me to be red in codeforces :)

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

        I guess for you being Red is more important than having empathy.

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

      Actually, the "swastika" is an ancient symbol that is originated in India with its roots in the Vedas, the oldest scriptures of Hinduism. The word itself is said to be derived from the Sanskrit root, swasti, which is composed of su, meaning 'good' or 'well', and asti, meaning 'it is'. It generally translates to 'it is good'. Although the symbol was later on modified by Hitler but that's another thing.

»
3 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

Just anyone please tell me the mistake in this code. Problem AMy submission

include<bits/stdc++.h>

using namespace std;

int main() { #ifndef ONLINE_JUDGE freopen("inputff.in","r",stdin); freopen("outputff.in","w",stdout); #endif

int t;
    cin>>t;
    while(t--)
    {
      int xa,ya;
      int xb,yb;
      int xo,yo;
      cin>>xa>>ya>>xb>>yb>>xo>>yo;
      if(xa!=xb&&ya!=yb)
      {
        cout<<abs(xb-xa)+abs(yb-ya);
      }
      if(xa==xb&&ya==yb)
      {
        cout<<0;
      }
      else if(xa==xb)
      {
        if(xo!=xa)
        {
          cout<<abs(yb-ya);
         }
         else if((yo>ya&&yo>yb)||(yo<ya&&yo<yb))
         {
          cout<<abs(yb-ya);
         }
         else
         {
          cout<<abs(yb-ya)+2;
         }
      }
     else if(ya==yb)
      {


        if(yo!=ya)
        {
          cout<<abs(xb-xa);
         }
         else if((xo>xa&&xo>xb)||(xo<xa&&xo<xa))
         {
          cout<<abs(xb-xa);
         }
         else
         {
          cout<<abs(xb-xa)+2;
         }
      }

      cout<<endl;
    }
     return 0;
   }
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    else if((xo>xa&&xo>xb)||(**xo<xa&&xo<xa**)) { cout<<abs(xb-xa); }

    You used the same condition xo<xa&&xo<xa, verifying only the cell A, instead of xo<xa&&xo<xb

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

I am the only one who feel nasty statement for Problem C :):), and ended up without solving :):)

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

    I did get confused when I first read C, especially when my perf was so high. I went straight to the example first, then went back and read the rest to check if I missed anything. The parts that that describe Monocarp and Polycarp's sequences are identical, so you can also skip those after a quick glance.

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

i missed vovuh

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

9206baf56572ebc9908e8ed4e798fe4513e47577 .

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

    I think top-rated coders underestimate newbies and pupil potential and therefore attempt to downvote our comments. This is my personal viewpoint. Please accept my apologies if I have offended anyone.

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

So, it's div 3 for div 1, well played.

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

Problem resolved

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

Are solutions with multiset or priority queue for F getting too?

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

Was the round rated for newbie category? below 900

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

This has been a very exciting contest for me. Thank you very much!

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

I wish i could finally be cyan.

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

Was this contest supposed to be unrated?

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

Why is the round unrated for me? I am at 1399 and trusted participant as well

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

    I don't think anyone has got their ratings for this round yet because it states that whether you're trusted or not this round is rated for everyone <1600

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

      I can see it is unrated in my chart.

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

        We all have to wait a little

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

        I think every contest until rating is updated is put into that chart as seen from past rated contests.

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

why r the ratings not yet updated??

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

It was a coincidence for sure. I published my code on ideone.com and used it on default settings, i.e in public mode. Please give my ratings back. I will take care of this in future. From now on I will use Vs Code.

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

    I got mail that my code of question B was coincides with some of the other users. I used idedone compiler for A and B. I changed setting of compiler from public to private but only for A and not for B. I was not knowing that it should be changed every time. Also, I submitted my code prior than with whom my code matched. Please give my ratings back. I'll not use idedone compiler in future so that this incident will not occur.

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

I expect better statement for div3 . statement should be short and clear ,its div3

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

I received a message that my contest submission for problem A was the same as Cidjethadaya, Ashutosh054 and Hitarth_agarwal. Also, my submission for problem C was the same as K4ay. However, notice that I submitted my solutions before them. I used public ideone to test my code (I didn't know there was such dishonest people that could look there during contest time) so I guess they copied it from there. Please, take a look DK318, unreal.eugene, MikeMirzayanov, geranazavr555 and doreshnikov .