Fefer_Ivan's blog

Codeforces Round #197
By Fefer_Ivan, 11 years ago, translation, In English

Hello, Codeforces.

Today at 19:30 moscow time, Codeforces Round #197 will take place.

Authors of this round are me and Gerald. I'd like to thank the following people for their contribution: Delinur for translation of the statements and MikeMirzayanov for creation and supportion of Codeforces.

The score for problems: 500 — 1000 — 1500 — 2000 — 3000.

Good luck!

UPD: To make the announcement more interestiong and thrilling we decided to add a horse joke and a photo, taken during the preparation of the round.

Q: What did the teacher say when the horse walked into the class?
A: Why the long face?

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

Comments Comments (79)
| Write comment?
»
11 years ago, # |
  Vote: I like it -65 Vote: I do not like it

Too late and too short announcement!

→ Reply
»
11 years ago, # |
  Vote: I like it -23 Vote: I do not like it

I hope to it has DP && graph problems ... thanks for great time

→ Reply
»
11 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Is this a step towards the COW LEVEL?

I wonder what's the effect of the mask on coding performances. On one hand you probably focus a bit better, but you might also become horsey...

→ Reply
»
11 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Really intresting [but easy!] Problemset and nice horse joke and photo!!
Thank U a lot!!

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Are you sure that this round easy? Especially problem E? I don't think so

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just Problem E is not easy!!
      Usually Problem Ds are harder than Xenia and Bit Operations...

      → Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Very nice problems.. Thanks to authors...!!!

→ Reply
»
11 years ago, # |
  Vote: I like it +36 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Not sure if this is correct ;) Would also be curious to learn the intended solution. I think this is not it.

    Intuition: a sequence of length 1000 after three operations consists mostly of a few sequences like 5,6,7,8,... and 9,8,7,... . The boundaries of such sequences are of interest to us, because they may have probably been the points where the string 1,2,...,1000 was "broken". For example, in the sequence 321789456, the numbers 3,1,7,9,4,6 seem to be interesting. On the other hand, there should not be many interesting numbers.

    So, let's say that a number i is suspect if it is not neighboured in the sequence by the numbers i-1 and i+1 (and let's also have 1 and n be suspect). We do backtracking — we try to generate all possible sequences that are created by reversing subsequences that begin and end with a suspect number. The complexity should be , where s is the number of suspect numbers (I would guess no more than around 14).

    → Reply
»
11 years ago, # |
  Vote: I like it -13 Vote: I do not like it

pretests are too weak!

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

nice system testing! ))) thanks

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

How to Solve D?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I you knew Segment tree you could solve it!!!

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      enlighten me please, I could't find a suitable Data Structure for it

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

      I haven't learnt about segment trees yet, but I solved the problem by storing all the results inside a 2D vector. Then for each query, you will have to update 17 nodes in the worst case. My solution wasn't very fast though.

      → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    You can simply solve it using Segment Tree. Suppose you have a Segment Tree which is a Full Binary Tree with 2^17 leaves and thus has height of 18. Now you need a property to compute the value of one node using its children. If your node is at odd height then its result is the OR of its children, otherwise it's their XOR. You can update in O(logn) and find the wanted value in O(1) (just take the root of the tree) Hope i helped :)

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      GOOOD ONE bro !!! Helped a lot, I couldn't see that way ;)

      → Reply
»
11 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Nuff said.

→ Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem C is very tricky :(

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

    I failed C as well, however the contest was interesting and the problems were very well explained.

    Thank you very much Fefer_Ivan.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I get AC after the end of competition. Just because I add code that enumerate the first weight of left scale. so sad...

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

Got it... Sry

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    Your program didn't print anything in output

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it -15 Vote: I do not like it

7 successful hacks for Problem C just with this simple test:
1110000000
4
:O Just Like my previous avatar!

→ Reply
»
11 years ago, # |
  Vote: I like it -11 Vote: I do not like it

for problem E, answer given by solution for testcase#7 is incorrect. the result won't be 1,2,3,4,...,98,99,100 the result for given answer by judge's solution is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 97 98 22 23 24 25 26 74 73 72 71 70 47 48 49 50 51 52 53 54 55 56 57 58 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 27 28 29 64 65 66 67 68 69 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 63 62 61 60 59 92 93 94 95 96 99 100

it's not correct! or i & many other contestants understood the problem in a wrong way.

→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can anybody explain why do this solution get AC?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i didn't read the algorithm, but it's output for TC#7 is same as mine, but he passed it and i didn't! i don't know why!!! here is my code

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      No, your answer is reversed.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        oops. the problem wanted her movements, not us! :| by the way, my algorithm is not correct, i reversed it just to check, and i didn't pass TC#8 because i'm solving it with more than 3 moves.

        → Reply
»
11 years ago, # |
  Vote: I like it +15 Vote: I do not like it

During the contest,Aatr0x (I don't know him) sent me following message... And I noticed he passed D.Anyone sent D's sourcecode to him?

#include <cstdio>
#include <algorithm>
#include <vector>


using namespace std;

char s[15];
int m,last,cnt;
vector <int> v,ans;
int l,r;

int main()
{
    scanf("%s%d",s,&m);
    for(int i=0; i<10; i++)
        if(s[i]=='1')
            v.push_back(i+1);
    while(1)
    {
        int i;
        for(i=0;i<v.size();i++)
        {
            if(v[i]!=last && l+v[i]>r)
            {
                last=v[i];
                l+=last;
                ans.push_back(last);
                break;
            }
        }
        if(i==v.size())
            break;
        cnt++;
        if(cnt==m)
            break;
        for(i=0;i<v.size();i++)
        {
            if(v[i]!=last && r+v[i]>l)
            {
                last=v[i];
                r+=last;
                ans.push_back(last);
                break;
            }
        }
        if(i==v.size())
            break;
        cnt++;
        if(cnt==m)
            break;
    }
    if(cnt==m)
    {
        printf("YES\n");
        for(int i=0;i<ans.size();i++)
            printf("%d ",ans[i]);
    }
    else
    {
        printf("NO\n");
    }
    return 0;
}




THIS IS QUESTION C
SEND ME D
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    He sent me the same message also.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    He sent me the same message! Of course I ignored him...

    → Reply
»
11 years ago, # |
← Rev. 5   Vote: I like it +3 Vote: I do not like it

"she writes down the bit-wise OR of adjacent elements of sequence a" if this sentences wasnt wrong than

1 . step => a1 , a2 , a3 , a4

2 . step => a1|a2 , a2|a3 , a3|a4

3 . step => (a1|a2) ^ (a2|a3) ...

...

but problem is

1 . step => a1 , a2 , a3 , a4

2 . step => a1|a2 , a3|a4

3 . step => (a1|a2) ^ (a3|a4) ...

Because of this statement i couldnt colve this problem , may be i 'm quilty too because dont read all statement or dont look sample test , whatever there is a problem with statement.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Yeah I made the same mistake at first as well. Just goes to show that reading the sample helps. :)

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain test 7 for problem E for us? Lots of contestants failed on that with the same output: 3 22 97 27 74 47 69 I don't think this output is wrong... Can anyone help me?

→ Reply
»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

imho, D much more easier than C.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is(just a kind of feeling)! but i dont understand the meaning of the problem D. perhaps i should learn maths harder..

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      this problem is just standard segment tree problem , not related to maths

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        That is an interesting statement...

        Can segment tree be defined without using mathematics?

        Unless I am misunderstanding what "maths" means, I do not think it is possible. But someone can prove me wrong.

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach D efficiently?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    After every query only n elements of this pyramid are changing, and you can recalculate them after each query.

    ADD: You can store all information in array a[2N], where N = 2n, elements with indexes more or equal N are leaves and childs of vertex i are 2i and 2i + 1. See my solution

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I assume that by pyramid you mean the "recursion" until we reach 1 element...

      So if we have the numbers: 1 6 3 5 and we have query 1 4, we will obtain the list 4 6 3 5, you mean that only pair 4 6 needs to be computed, yes? Then this result will "propagate" and we use it with (3 & 5) to get answer?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 4   Vote: I like it +1 Vote: I do not like it

        By pyramid I meant binary tree, which you can draw in process of calculating the result. On every vertex there is number. You need update value of first element(4), update OR-sum of first two elements 4 | 6, and update value of root of this "tree" XORing (4 | 6) with CALCULATED(you have no need to calculate it again) value of (3 | 5).

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you please tell me why we need memory of 2^n size? Because, in other seg tree problems I saw using 4*n size of memory.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Segment tree of size k needs at most 2n + 1, where n is the least number such that 2n ≥ k.

            → Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

system testing was very fast today (Y) :)

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

why 4344499 and 4341816 solutions were skipped in system test? There were no additional submission in each of the problems and both of them passed the pretest.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my solution for Problem D use 1700+ms and other's avg time is 300ms...

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the contest dealt with various kind of problems which was very very helpful to develop the skill for a contestant :)

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Hi all! I solved problem C but i don't explain my code get Accepted this problem

I think it is O(t^m) with t<=10, m<=1000 This is my code http://codeforces.me/contest/339/submission/4352722 Thank you :D

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    OMG. really INCREDIBLE. i dont belive that is realy. but it is realy.==> TEST is very low

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    :|

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i++)

    define DOWFOR(i,a,b) for (int i=(a),_b=(b);i>=_b;i--)

    define mp make_pair

    define pb push_back

    define reset(c,x) memset(c,x,sizeof(c))

    define oo 1000000000

    using namespace std; char s[100]; int m,res[10000],sl=0,w[20],t=0,sum[2]; bool ok; void duyet(int x) { if (sl>=m&&ok==false) { printf("YES\n"); FOR(i,1,m) printf("%d ",res[i]); ok=true; return; } if (ok==false) FOR(i,1,t) if (ok==false) { if (w[i]!=res[sl]) if (w[i]+sum[x%2]>sum[(x+1)%2]) { sl++; res[sl]=w[i]; sum[x%2]+=(w[i]); // cout<<sl<<" "<<sum[x%2]<<" "<<sum[(x+1)%2]<<endl; duyet(x+1); sl--; sum[x%2]-=(w[i]); } } else break; return ; } int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); gets(s); scanf("%d",&m); reset(w,0); reset(res,0); FOR(i,0,strlen(s)-1) if (s[i]=='1') { t++; w[t]=i+1; } // FOR(i,1,t) // cout<<w[i]<<endl; if (t<1) { printf("NO"); return 0; } sum[0]=0; sum[1]=w[1]; sl=1; ok=false; FOR(i,1,t) if (ok==false) {

        sum[0]=0;
    sum[1]=w[i];
    res[1]=w[i];
    sl=1;
    duyet(2);
}
else 
{
    break;
}
if (ok==false)
{
    printf("NO");
    return 0;
}
return 0;

    }

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    i do something like this i used dfs on a tree that have t^m vertex but it will get much faster if you code that if a vertex can't be an answer don't continue it. see my solution 4358155

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, thanks you. I think you have same idea with me ,I agree with you :D Your code is very short and clear :D Haghani

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, problem A and B are easier than before... And at first thought use dfs to solve problem C will get TLE...

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Will there be a post with the author's solutions?

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Some code got Accepted on problem E will fail on this test:

10
5 4 3 2 10 1 9 8 7 6
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    4350288 this one for example.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the idea behind this testcase?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it 
      --[-----first swap-----]--------------------------------------------
---------------------------------[--------second swap------------]--
-----------------[------------third swap-------------]--------------

      Some codes didn't work this situation.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        4 2 4 1 3 That example is more shorter (doesn't work that test on his program)

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What a Ridicule joke... :-|

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem C?

→ Reply