Ripatti's blog

Codeforces Beta Round #93
By Ripatti, 13 years ago, translation, In English

Hello everyone!

I am glad to welcome you on today round of Codeforces. I hope that recent color revolution and a more later time for start of round will make some variety into process of solving problems:)

An author of today problems is me. RAD helped me to prepare this round, Delinur translated statements into English.

Good luck.

UPD.

The round ended, ratings was updated.

Winners of div1:

1. Egor

2. tourist

3. unicef

4. sevenkplus

5. ivan.popelyshev


Winners of div2:

1. RainbowDash

2. cjtoribio

3. miraliv

4. adrian.jaskolka

5. majia5

Yippee!

Editorial.
  • Vote: I like it
  • +200
  • Vote: I do not like it

Comments Comments (78)
| Write comment?
13 years ago, # |
  Vote: I like it +13 Vote: I do not like it
Thanks :) I would like to remind all Div2 coders who are aiming for Div1 today, now violet starts from 1700, not 1650.
 
→ Reply
13 years ago, # |
  Vote: I like it -6 Vote: I do not like it
I really like your contests, not all, because of long statements. But in my opinion you are professional on creating contests... I am about Ripatti.
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Just a reminder, a contest starting at 1:00am or 2:00am local time is really inconvenient for the people live in East Asia. 

→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Is it possible to unofficially join the round? because I will join a little late so I wouldn't like it to affect my rating but would still like to solve in real time.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it
    Join as a team. It will be unrated.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I a sorry , how can I do that?
      I only find one option which is as an individual.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        For "School Regional Team Contest, Saratov, 2011" it was as havaliza said, but in normal rounds it isn't possibile to join as a team
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it -25 Vote: I do not like it
          Simply, you can register another account and use it for this contest.
          → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
for Chinese coder..the contest start at 1:00 am local time = =!
what's worse!!
for an Australian...the contest start at 3:00 am local time ><!
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it
    The contest will always start at a bad time at some place in the world. In Brazil, the "traditional" time is always lunch time, so sometimes we don't eat in order to participate.
    That's why I like when the contest time vary a lot, like TopCoder. If it's not a good time for you today, it will probably be a good time in the next round.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it
      I agree with that. Even though most of the time, CF times suite me best (around 7/8 PM), but I agree that it will always be bad for some participants and varying it for each competition would make sure that not the same lot is always at receiving end of the bad timing.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Don't forget that it is a Russian website. Currently 1152 members are from Russia. I think that this time is perfect for the most of participants.
        → Reply
        • 13 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          But this is an international site right where most participant are outside russian. I think CF must anticipate contest time. most in Indonesia CF contest start at 10 PM and now it start on 12 AM.

          Well thats my opinion :))
          → Reply
  • 13 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it
    伤不起。。。
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is it normal that Div2 contestants are 4x times more ? 
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    As far as i remember Div 1 is approximately 10% of all users. So yes, its normal.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    and also 1650 to 1699 are in div 2 with new ratings system.
    → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Could anyone give me a hint on the theory behind div2 D/div1 B, is it suffix trees? Or some variation on KMP?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Some variation of "z-algorithm" probably.
    Here is a solution that uses hashing: if t is the answer, then it's a prefix of s and a substring of s[1..len(s) - 1]. Moreover, each prefix of t satisfies this condition. So one can find the longest t with binary search: checking if one string is a substring of another (fixed) string can be done in linear time with hashing.
    Now you need to find the largest prefix of t that is also a suffix of s. Again, linear time and hashing.
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I would like to see the solution without hashing that fits the time limit.


      Edit. Especially I don't understand why KMR algorithm got TLE?

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        My solution do not use hashes
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it
          Ok, but still don't see the point in rejecting KMR algorithm. Why the length couldn't have been something like 10^5 or greater time limit...
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Do you speak about KMP ?

            It works fine
            → Reply
          • 13 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it
            The hashing method fetetriste talks about is basically KMR. You just need to do some manual thinking once you need to get your suffix right. Otherwise you get n^2 on cases like "a"*1000000+"b". 
            → Reply
        • 13 years ago, # ^ |
          ← Rev. 2   Vote: I like it -9 Vote: I do not like it

          Egor

          How do you make your own library in java

          import net.egork.string.StringUtils;
          → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Could you please give me some material(links) or papers about "z-algorithm"? Thanks a lot for your help. My Email Address is lisen10@otcaix.iscas.ac.cn

      Ps:It is better in English. Thank you again.
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I solved it with KMP.  I computed the inverse of the failure function and stored it in a balanced BST.  Then iterate over all prefixes p of s which are also suffixes, and examine whether p appears in the middle of s.
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    It is solvable by KMP. You must count the length of the maximal prefix that is also a suffix for each position, let's say in table p. Then you are interested in checking if p[n-1] is also somewhere in the middle (if p[n-1] = 0 the answer is NO). To check this, it's enough to count the number of positions where p[i] = p[n-1]. If there is more than one such position it means that we have found substring somwhere in the middle. If not, then you must use the fact that another maximal prefix that is also a suffix is p[p[n-1]-1]. You check if it's greater than 0, if yes than you have your substring otherwise, the answer is NO.

    → Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
"The display rows are numbered with integers from 1 to n upside down"

Oh, you meant it literally :)
→ Reply
13 years ago, # |
  Vote: I like it +30 Vote: I do not like it
C for div2 and A for div1 was very tough! :|
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes, it took me a long time to finish it. Though the thought is simple.
    → Reply
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Start the system testing :)
→ Reply
13 years ago, # |
  Vote: I like it +18 Vote: I do not like it
Really cool problemset. Congrats Ripatti!

Eagerly waiting the editorial. xD
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is it just me or that Div 1 systests aren't moving?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I think I got it, the big number of submissions in Div 2 and the small number of submissions in Div 1 is making grading Div 1 submissions slow.
    → Reply
13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
what is "Denial of Judgement" ?
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
i am interested in what was 6th test at C for div 2 and A for div 1
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You should not minimize y2, when y1=0.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      I don't think that test
      my code have that condition and still got WA in pretest 6
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For div2 C, I expanded the equation and got:
y1/y2 = -(t0-t2)/(t0-t1)
What were the conditions for the solution ?!
Thanks :-)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For DIV-1 B, is it expected that an suffix array algorithm + binary search (each iteration run a linear scan) (O(N lg N)) will get TLE?
Is anyone who AC this problem by suffix array + binary search?
I just wanna know, whether my code have some logical bug, or it is just too slow for this contest.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Suffix Array has complexity NlogN with big constants, even when Suffix Array si NlogN it requires a lot of optimisation to get it work here. NlogN = 1,000,000*20 = 20MM, but looking your loops it seams ~4NlogN or greater ~ 80MM, adding the binary search for searching the string in places it tooks more than 100MM which is near TLE
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      So a code with a smaller constant in the SuffixArray+LCP+etc construction may AC?
      If so, I will try to optimize the code later to see if it is the case later.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Yes your are right, although i dont know if you can do a suffix array with lower constant, mine is higher than yours, and i ran you solution in my laptop with a big testcase and ran ~1s, don't trust it though but when trying optimising, try the case
        generated here

                for(int i = 0; i < 1000000; ++i)
                    s[i] = (i%2 ? 25-i%26 : (i%26))+'a';
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        oh sorry i found a worstcase where you solution get a bad time like 4s

                for(int i = 0; i < 1000000; ++i)
                    s[i] = (i%100 ? 25-i%26 : (i%26))+'a';

        i think is really hard to optimise it, probably imposible :/
        → Reply
    • 13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      > Suffix Array has complexity NlogN

      That's improper suffix array. Proper Suffix Array is linear :)

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        cool, knowing something like that is interesting for me, i would like to learn such a suffix array :p could you point some info abaout it. I based my argument in chhung6's code and mine, but i have heard about linear suffix array, but is never late to learn :)
        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My solution for D works on my computer and on "Custom Test", but not on the grater.
Any ideas for what might cause that kind of error?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Ah, problem was the graters use of '\r' in the end of lines..
    → Reply
13 years ago, # |
  Vote: I like it -8 Vote: I do not like it
I am blue for the first time.Thanks Ripatti for preparing such beautiful problems.Took me 13(my lucky number)contests to turn it blue
→ Reply
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
My solution gives correct output on my computer and different output on judge for tes-31 of prob-C of div2.[Involves floating point comparisons]
Does it have anything to do with optimizers ?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Same thing, but my code fails case 11. which has a input "1 1 100 100 1" and i got correct answer "100 0" to the case on my computer. Other people who passed the problem output "100 100" just the same to mine output here.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      "100 0" is not the correct answer "100 100" is since the bath will fill faster
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        You re right, thanks for the tip. Seems that I need a sleep.
        → Reply
13 years ago, # |
  Vote: I like it -12 Vote: I do not like it
In problem C in Div-2,
how can we recognize that the bath is going to be fulled? there is no data about bath size :?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    If you maximize y1+y2, that is the amount of water/s you send in, surely the bath will be fulled as fast as possibly.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
hey all .... i am having RTE in problem -4 (div-2) on test-25. i am leaving ma code here.. plz some one help me getting a AC.


#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>

using namespace std;

string s;

vector<int>v[333];


bool if_true(int mid,int dis){
    int i;
    for(i=0;i<=dis;i++){
        if(s[i]==s[mid+i] && s[i]==s[s.length()-1-dis+i])continue;
        else return false;
    }
    return true;
}

int main()
{
//    freopen("sam.txt","r",stdin);
    int i,j,dis;
    char a,x;
    cin>>s;
    for(i=0;i<s.length();i++)v[s[i]].push_back(i);
    a=s[0];
    x=s[s.length()-1];
    int dis1=-1;
    int mid=-1;
    for(i=0;i<(signed)v[x].size()-2;i++){
        dis=v[x][i];
        if(s[s.length()-1-dis]==a){
            for(j=1;j<(signed)v[a].size()-1;j++){
                if(s[v[a][j]+dis]==x && s.length()-1-dis>v[a][j]){
                    if(if_true(v[a][j],dis)==true){
                        if(dis1<dis){
                            dis1=dis;
                            mid=v[a][j];
                            break;
                        }
                    }
                }
            }
        }
    }
    if(dis1==-1){
        cout<<"Just a legend"<<endl;
        return 0;
    }
    bool flag=true;
    for(i=0;i<=dis1;i++){
        cout<<s[i];
    }
    cout<<endl;
    return 0;
}
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    vector<int>v[333];
    need it be 2000
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      i tried with :
      vector<int>v[2000]   
      as you said... but the case is the same.
      actually i was intended to have a map of the positions of the certain character that appears in the string. and whren i get char x at position i in the given string i do the followings:

      v[x]<--i ; so i should need actually v[] of size 124. think problem is some where else.....
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        You can launch your program with failed test as input and find bug by yourself.
        → Reply
  • 13 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it
    plz some one help me finding the erro.. plz plz .. . who else can fix it but you people \m/  :D
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      Read the description again, write the code again with moderate thinking. Check other Accepted codes. You will get your bug.
      → Reply
13 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it


→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I am struggling with the Hot Bath problem (Problem C on Div 2 and Problem A on Div 1).  My code passes the given examples and is consistently generating wrong answer on test 8.  Can anyone give me advice on corner cases I may be missing?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    you can check the test cases and the expected answer for each test case by opening contest standings then view the code of any contestant. All test cases along with their answers will be listed right below the code
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Where is the Editorial ?
→ Reply