sober_phoenix's blog

By sober_phoenix, 3 years ago, In English

codeforces EDU has a collection of really great and educational problems. But I have a question, whether it would be fair to publish editorial for the problems in EDU section ?

On one hand it has contest like environment ( for example hiding system tests etc. ). This means, it can potentially be treated as publishing editorial/solution for an ongoing contest.

On the other hand, it also has a practice like environment ( for example, the different solution approaches are discussed in the comments). In that case it should not be a problem to publish editorials. CSES problems can be a good example here, it's editorial is readily available on codeforces.

So, I would like to know your opinion about this.

Full text and comments »

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

By sober_phoenix, history, 4 years ago, In English

So I was trying to solve the problem 16E - Рыбы with push dp. However it's failing locally. Can you please help me figure out where is this going wrong ? Submission : 115175573

main idea

dp(i) — denotes the probability of having the fishes represented by mask i.
initially all fishes are alive hence dp((1<<n)-1) = 1 i.e dp(111...(n times)) = 1, now from each state i, next day, it can go to a state i^(1<<j) , for such a j for which j-th bit is turned on . i.e j-th fish is alive on the current day in the pond. probability of going to such a state will be given by —

let , cnt be the count of fish alive in that pond on the current day then probability to go mentioned state will be,
prob_sum = a(k1 , j)/C(cnt,2) + a(k2,j)/C(cnt,2) + ..... such that all k are the set bits of mask i and k!=j (i.e all alive fishes in the pond on current day except the j-th fish).

Can anyone help me find the wrong in my approach or code .

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it

By sober_phoenix, 4 years ago, In English
  • Vote: I like it
  • +97
  • Vote: I do not like it

By sober_phoenix, history, 4 years ago, In English

Well, let me guess about your journey to this blog. Maybe you were reading something important on codeforces, then you saw this blog title pop up in your recent action menu. Curiously you clicked on the title blog addiction and now you're here. This is precisely what happens to me most of the time . Maybe I'm reading editorial of a past contest then I see any interesting title appearing in my recent action feed . In no time , I fell into the rabbit-hole of blogs , and completely lost sight of the original goal ( in this case , reading editorials of the problem I couldn't solve).
With the ever increasing user base of codeforces , the title nowadays are very clickbait-ish . I guess this is how people ( including me ) develop youtube addiction too .
I'm sure this has happened to many of us . How do you deal with this ?

Full text and comments »

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

By sober_phoenix, history, 4 years ago, In English

If you're using any build script to build and compile your C++ program then there's a high chance your system got frozen during a contest ( possibly because there were some infinite loop that you didn't notice ) and probably you had to restart your system . This gets very irritating during a contest . Although there's a workaround of this problem using timeout script in some system, but it's not always compatible with g++ commands . A better solution is to set the resource limit ( CPU time , virtual memory , stack size etc. ) in your program using a function : setrlimit . A general template is :

#include <sys/time.h>
#include <sys/resource.h>
int setrlimit(int resource, const struct rlimit *rlim);

A detailed description of all the terminologies can be found here. the setrlimit takes two arguments the first one (resource) specifies what sort of resource you want to set limit on (e.g RLIMIT_AS for the process's virtual memory (address space) , RLIMIT_DATA for the maximum size of the process's data segment etc. ) , And the second argument specifies the numeric value of the limit that you want to impose (it's value depends on the resource parameter that you're specifying ) . Personally, I like to impose limit on the CPU time (RLIMIT_CPU) and file size (RLIMIT_FSIZE).

Note : This function works on UNIX based system , And in order to ignore any of these limits in your final submitted program it's better to wrap this snippet around an #ifndef #endif conditional directive with ONLINE_JUDGE macro . That being said here's the minimal code snippet that I use :

#include<bits/stdc++.h>   
#ifndef ONLINE_JUDGE
#include<sys/resource.h>
#include <sys/time.h>
#endif
int main(){  
        #ifndef ONLINE_JUDGE
        /* setting up soft limit on resources */
        rlimit rlim , rlim_time ;
        if(getrlimit( RLIMIT_FSIZE , &rlim) || getrlimit(RLIMIT_CPU , &rlim_time) )  
            return 1 ; 
        rlim.rlim_cur = MAX_FILE_SIZE // maximum file size (in bytes) that your program will be able to create ; 
        rlim_time.rlim_cur = CPU_TIME // maximum allowed runtime for your program ; 
        if(setrlimit( RLIMIT_FSIZE , &rlim ) || setrlimit(RLIMIT_CPU , &rlim_time))
            return 2 ; 
        #endif
}

Full text and comments »

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