_jte_'s blog

Codeforces Beta Round #86
By _jte_, 13 years ago, translation, In English

Hi all, 


Today we would like to invite you to take part in round #86. Round is prepared by Andrew Malevich (aka Kenny_HORROR) and me, Taras Brzezinsky. We are students of Belarusian State University. We would like to thank  MikeMirzayanov ,  it4.kp , RAD , Gerald и Fefer_Ivan for helping and advice in preparing round and  Delinur for translation.

While participating, you will get known with boy Peter and remember some of his school days to help him to solve some problems

The points for the problems in Div 1 & 2 will be: 500-1000-1500-2000-2500.

New service "Virtual contest" will be unavailable during the round due to possible instability.

Good luck to everyone!

UPD

The contest is finished, ratings are updated. 
Congrats to winners:
DIV1:
2) KADR
3) yaro
5) Egor

DIV2: 
4) lxn

Editorial is currently available, the whole problem set analysis will be added in few hours.

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

Comments Comments (111)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
very slow judging queue.. =.="
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
String tasks are not interesting! They were exhausting
→ Reply
13 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I don't like today's contest, slow judging and exhausting problems :(
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I have another question. Why penalty for wrong submission isn't counted when program fails pretest 1, whilst it is counted when it fails another pretest from the statement?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It is as a rule in round format.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Can you give me the link to this rule? I can't find it. And if there really is such a rule, what is the point of it?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        You gain no penalty for sending wrong file or not commenting freopen(...), or even printing debug output.
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I was under the impression that you were only penalized if your previous submission passed all pretests, and then you resubmitted another solution after that. The rules from the link seem to support that interpretation:

        "You may resubmit the solution at any moment, but it may reduce your score. It happens if resubmission is successful (i.e. passes all the pretests + previous hacking attempts). In this case, the previous successful attempt would be considered as a reason for penalty"

        So has this rule changed?
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          No. What the rule says is this: if you ultimately submit a failed submission, you obviously do not gain any point. If you ultimately submit a successful solution, the points you should gain from this submission will be reduced by a fixed number of points (a penalty) for each solution previously submitted ; the only exception is a submission that failed the first test case (for the reasons cited above).
          → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Aie... Bad contest for me too. And the slow judging was really bad for advance quickly on the contest...
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Ya ,today's contest had some tough questions .I wasted all my time on Question E.Thought I could solve that.
All prime numbers of the form 4n+1 qualify for it(and 2 also) .But I was getting Time limit exceeded!!!
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    But what do you use for those prime numbers? A function "is_prime" who is a little as:
    bool is_prime(int n)
    { for(int c=2;c*c<=n;c++) if(n%c==0) return false; return true; }

    If yes, it's slower than calculate alls numbers prime, no?
    vector<int> list_prims;
    void precompute(int n)
    {
      list_prims.push_back(2);
      for(int c=3;c<=n;c+=2)
    {
     for(int c2=0;c2<list_prims.size();c2++)
     if(c%list_prims[c2]==0) goto end;
    list_prims.push_back(c);
    end:;
    }
    }

    I don't know if what I said it's stupid, I have not calculated the complexity of the second fonction. But more we have a big number n, more there is space between two number prime...

    Ps: I have Time limit Error for the pretest 4, so it seems to not be the good solution.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hey bro,same situation here...waiting for the editorial...nice problem anyway...
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Problems C, D ( Div. 2 ) were too heavy on implementation
I guess my opinion right now can't be really true, as I did really bad :-/
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Not really. Specially if you use STL for C, D. The "find" function of class string in C++ really speedens things up and helps in a nice and clean implementation. (Though i made a very dumb mistake in D :( )
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thank you for one more nice contest !! Clear and short statements, unrelated problems, I like it..
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is happening with the system testing? :(
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
plz plz .......unrated :(
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
this is why system testing is very slow.. 300++ testcase for problem A div 1.. is that necessary ???
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    A div1 is lengthy and I was confused and locked it in a hurry, only to not be able to re-submit again :(
    So, a sentence with just one word which is a verb should give "NO", isn't ? I'm missing something from statement. Could some one point out that. Thanks.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      ok, found it.. I missed reading this rule "A sentence is either exactly one valid language word or exactly one statement. " :(
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      It should be "YES" because sentence is word or Statement(that should contain a noun)
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      One word can any part of speech.

      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      No, it shouldn't give "NO". The definition of a sentence is: "either exactly one valid language word or exactly one statement." So a valid word is enough. That cost me a lot of submissions :-/
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
       a statement with just one word which is a verb should give "YES".. verb is a valid word, so it's a valid sentence..
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Shit, miss that. Don't understand this one word rule. If got then may be for the first time top 10 :( Bad luck
        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I can't understand the statement of pB(div 1) very well.
What's the output of the input below?
2 or 3?

acdbadcb
a
b
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It's much annoying to stare at "In queue •"... :(
Hope, proper steps will be taken :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
That is one damn slow systest. 1+ hour and counting
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In my opinion,it is not good to set many string tasks.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I hope that judges have solutions without using hashes for Petr#.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    why ?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Because they need hash function that for each possible string from the statement returns different value (f(x) != f(y) if x != y) otherwise the solution is incorrect.
      I think that solution which uses suffix array is very valuable, but I would also like to see other non-hashing solution, because suffix array isn't a proper method for B level. I mean such a solution that can be implemented in java and pass all systests without any pruning.
      Once upon a time during a contest I discovered 2 different strings of the same length (<= 100), that made my hashing function failed and it was rather a good hashing function, because I solved many tasks using it. Since then I think that hashing is a good method for ACM-ICPC style, when I have immediate result, but if I can't correct my mistakes during a competition, then I don't use hashing.
      I also believe that writers are aware of the fact that using hashing isn't a 100% correct solution and give such time limits, that you can solve this problem with methods appropriate for lvl B.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Okay.
        What do you think about Prob C DIV1. ?
        I see some people hard-coded primes in the intervals of 10^6 or so .
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I don't like math :P but I don't see any problem with this task :)
          → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        It seems tourist didn't use hash, maybe you can look at his program
        → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    What to say, I am tired of solving just 1 and 2 in Div2.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes, there is non hash solution for Petr#. Editorial will be posted soon.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      What is test case 68 is it:
      aaaaa... 2000 times
      a
      a
      ?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Nope. It was worst case in my opinion:
        aa..aabb..bb
        a
        b

        in program there 1000 a's, and 1000 b's.
        → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, we can use idea of Trie and get rid of hash
    My AC code from practice http://ideone.com/hMmmm

    Edit: hmmmm :p
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Will space complexity be too high? A trie of length L with an alphabet A requires O(|A|L) am I right? Maybe it can be implemented in another way?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        No, you can allocate memory dynamically, then you will just need O(sum of lengths of words in trie).
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I hardly used Tries before, so I came up with that naive implementation. May be we can use a vector (c++) and create only necessary child links, like I modified here http://ideone.com/7MlnI . Run time increases and space complexity decreases, by constant factor.

        Can some give a rough idea on how to still reduce space ( if at all we can ).

        Thanks.
        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Easy looking problems caused lots of problems.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Not sure why my Div 2 E timed out on test 12 - it spends the same amount of time on any test case (builds all "interesting" numbers for each test case, no matter what l,r are)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Case (heh) in point:

    Test: #10, time: 4510 ms., memory: 96140 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    100 152262461
    Output
    4281819
    Answer
    4281819

    Test: #11, time: 4720 ms., memory: 96140 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    200 299399868
    Output
    8110312
    Answer
    8110312


    Test: #12, time: 5000 ms., memory: 96140 KB, exit code: 0, checker exit code: 0, verdict: TIME_LIMIT_EXCEEDED
    Input
    300 99050033
    Output
    2854733
    Answer

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Very unrealistic and irrelevant constraints in my opinion.
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I would not go that far but, to be honest, I haven't seen a code optimization problem in a contest in a while (meaning, there hasn't been a need to reduce the constant factor).

        I did remember seeing Yarin's Sieve a while ago,  but I never really had use for it - this time I googled for it and implemented it in Java. For other's benefit, here it is (my code passes if I inline the calls to isPrime(), which is a shame):

        [code]

        /*
        * Convert Yarin's Sieve to Java... bleh :)
        */

        private static final int MAXSIEVE = 300000000;
        private static final int MAXSIEVEHALF = MAXSIEVE / 2;
        private static final int MAXSQRT = (int) (Math.sqrt(MAXSIEVE) / 2);

        private byte[] a = new byte[MAXSIEVE / 16 + 2];

        private void init() {
            Arrays.fill(a, (byte) 0xFF);
            a[0] = (byte) 0xFE;
            for (int i = 1; i < MAXSQRT; i++)
              if ((a[i >> 3] & (1 << (i & 7))) != 0)
                for (int j = i + i + i + 1; j < MAXSIEVEHALF; j += i + i + 1)
                  a[j >> 3] &= ~(1 << (j & 7));
        }

        private boolean isPrime(int n) {
            return (a[n >> 4] & (1 << ((n >> 1) & 7))) != 0;
        }

        [/code]

        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Note that above sieve works for odd integers less than MAXSIEVE only;
          → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is there any solution for the problem B of  Div 1 without hash?, I did something with trie but I got Memory Limit on test 76.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Liked today's problems :)
waiting for editorial to see the non-hashing solution for Petr#.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I dont know what stopped me for coding the solution for Div2 E.
I thought to myself..at 1:30(hh:mm) before end of contest."ahh..sieve...surely it will TLE " ......
Again at 1:00(hh:mm) ..."yeah..sieve must TLE  ...the limits are very high ... "
Again at 0:30 ..." n^(1+k)  must time out [0 < k < 1]" ...

But when I see AC solutions they used sieve only... :(


→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    not "sieve only"! they developed sieve, i mean divided it into parts... and so on...
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      whose solutions are u referring to ?
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Actually few got AC with dividing it into sqrt(N)  parts.
      Just optimizing the sieve can also do the trick.
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Does problem petr# have a solution better than O(n^2)  ?? ( n = size of string)
 
I get Time Limit on test 21 !!! and my solution is O(n^2) !!
Did anybody has this problem too?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Suffix tree... O(NlogN) solution
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
       what is a suffix tree?

      p.s. why does n^2 gets time limit ?
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    There is a ( solution that will be posted in editorial. This solution uses suffix array.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Is there in jury's solutions, solution of B(Div1) by using dynamic programming, how it was solved by Gennady?!
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Your solution works O(N*N*logN) because operation .insert() perform for O(log N), but STL version of this tree is too slow....
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    insert in a set is not O(1) so you solution isn't n^2, I think it.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is there a way to know the test case when a solution is hacked?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I think no . . . we can't know test case that use to hack

    but i can tell you that i use
    ababab...... 1000time
    a
    b
    to hack you
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can do it after contents, using hacks tab
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can problem B (div.1) be solved by hashing? If yes, what kind of hash function should you use?
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I used usual polynomial hash, 


    H(S) = (s1 + s2 * p + ... + sn * pn - 1) modQ, where

    p = 31, Q = 263 - 1.

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Is it still possible to construct a counter-example for it just like for most functions? 
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        In theory of course yes, but I do not know such an example. However, hash solutions were not main solutions from jury this time.
        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it


→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

(On Problem C)
It seems that I discovered a serious bug in Codeforces. . . . .

Submission judged with MLE:
  1. const int N = 3e8+5;
  2. bool b[N/2]={0};

Submission judged with AC:
  1. const int N = 3e8+5;
  2. //bool b[N/2]={0};
  3. vector<bool> b(150000020,false); // why no MLE?! CF has bug in counting memory?!

I suppose the authors intend not to accept a solution with O(N) memory. . . . right?

I understand now. :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I was wondering What does "Skipped" pretests mean?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If you have sent N times a solution and each time you passed pretest, then it will show N-1 times "Skipped", until the last program you sent: that will be avaluated against final tests.
    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A sentence is either exactly one valid language word or exactly one statement.

note like this in A-Div1 , C-Div2 very important it should be in bold font. too many Div1 and Div2 coders get WA @pretest 4.

especially, in low score problem with long statement.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I agree.
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    maybe we should be more attentive?
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Less important notes been bolded in previous contests, unlike this one! :( .. bold notes in this problem was very important it was Strings problem with a code a bit- larger and getting WA make you back to your code not for the problem statement to check missing notes.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        have you ever seen bolded notes in acm contests? I haven't. And I think most of us trains here for acm.
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I don't mean ACM I am talking about the previous contests in CodeForces.
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Codeforces for fun or codeforces for acm?
            → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i am stacked in a peculiar situation here. my code for the problem A gives correct out put in my computer, but fails for the same sample tests [sample 1] in the judge. looking for ways to out of this worst situation and want to know from the experts whether the problem is with my code, or my PC or with the JUDGE. tnx in advanced. I AM WAITING AND WAITING, FOR ANSWERS.

my code for problem A:

#include<iostream>
#include<math.h>

using namespace std;

int main()
{
//    freopen("sam.txt","r",stdin);
    int k,l,i;
    cin>>k>>l;
    for(i=1;;i++){
        int temp=pow(k,i);
        if(temp==l){
            cout<<"YES"<<endl<<i-1<<endl;
            return 0;
        }
        if(temp>l)break;
    }
    cout<<"NO"<<endl;
    return 0;
}
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    PS: please run my code in your PC and submit it in the JUDGE to see whats happening truely.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      nobody is giving any answers here. in the mean time PEIN_original gave me a message telling that he ran the code in hic PC, which gives correct output for sample test 1. so where is the problem with the judge. i am just going mad .... SOMEBODY PLEASE PLEASE PLEASE find me way out.
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    the problem in this line
            int temp=pow(k,i);
    when i>30 .. temp overflow of int ,, for this make temp long long .. and pow(k,i) has error percesion error when casting in (long long) it rounded down so it doesn't equal to the actual value .. so add 0.5 before casting so this line should be
            long long temp=pow(k,i)+0.5;
    hope you got it :)
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
The problems were awesome. I have just one question about div2 A ... i wanted to solve it using logarithm. obviously
  1. n = math.log(l,k)
  2. if n == int(n):
do stuff
is not the way to go. I tried if n-int(n) < eps where eps = 1E-13... it did pass test that failed before but it still gives me a wrong answer. How would i make that right? or is idea using logarithm just plain wrong?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    i think it's possible n-int(n) will be wrong too. suppose n = x. if i'm not wrong sometimes it will be saved as (x-1).99999999997. so int(n) will be x-1. (not so sure)
    you should have tried   abs(n-floor(n)) < eps  ||  abs(n-ceil(n)) < eps     just to be sure.
    but for problems like this i always follow KISS rule!  Keep It Simple Stupid.
    i just used this:
    while(n%k==0) n/=k;
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I have no idea to solve Problem E in div2! Call for help!!!~
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Editorial will be posted in few hours.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
anyone can tell me the solution of the problem E (div 2)? tks!
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can find it in editorial (it's also DIV1 C problem)
    → Reply