diskoteka's blog

By diskoteka, 21 month(s) ago, translation, In English

Hey Codeforces (ノ◕ヮ◕)ノ*:・゚✧

My team and I are happy to invite you to participate in Codeforces Round 878 (Div. 3). The round will take place on Jun/06/2023 17:35 (Moscow time). You will be offered 8 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 of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 8 problems and 2 hours and 15 minutes to solve them. One of the problems in this round is interactive. Don't forget to read the guide on interactive problems.

Note that the penalty for the wrong submission in this round 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 a trusted participant of the third division, you must:

  • take part in at least five 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.

Problems have been created and written by: diskoteka, pavlekn, playerr17, isosto.

We would like to thank:

  1. Aris for coordinating the round

  2. MikeMirzayanov for great Polygon and Codeforces platforms

  3. step_by_step for red testing

  4. Awesome3.14, I.Gleb, vladmart, dmkozyrev, geospiza, phattd, fishy15 for yellow testing

  5. KDZHR, D34D1NS1D3, JeffreyLC, NintsiChkhaidze, nickbelov, kamishogun, kaIimm for purple testing

  6. KoT_OsKaR, Gornak40, Serik2003, Nahian9696, Rudro25, ayhan37, Lyrically for blue testing

  7. TkachDan for cyan testing

  8. MODDI for green testing

  9. KurockaGril2010 for grey testing

We wish you all good luck and a high rating!

UPD: Editorial published

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

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +25 Vote: I do not like it

As an author, I suggest reading all the problems and not missing out on free positive delta.

»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

You missed a green tester :(

»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

as a tester, BEST CONTEST I HAVE EVER TESTED!

»
21 month(s) ago, # |
  Vote: I like it +48 Vote: I do not like it

As a blue tester,

Spoiler

Hope,

Spoiler2
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

orz sir

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Huge tip everyone! The problems for this contest are sorted by difficulty order! Good luck @everyone

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

It's really a seldom Div3.It starts at Tuesday.

»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

As a tester, I can ensure u that the round is balanced and all the problems are interesting. Good luck in the round!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I go to specialist in that contest Div 3 :? Hope

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why would you want me to do that?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      do what ?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        He was trying to make joke. Sorry you didn't get it. He meant that specialist is some place on google maps. That's why he said why do you want me.

»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

As a tester, it's my first time to test a Div.3 round.

»
21 month(s) ago, # |
  Vote: I like it +20 Vote: I do not like it

まどか

»
21 month(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

Thank Aris for purple coordination!

»
21 month(s) ago, # |
  Vote: I like it +38 Vote: I do not like it

As a yellow tester, I want to recommend to read all of the problems. Problems are quite varied. More think before coding. Don't go to implement the first idea which you got. Try to understand each example in problem statement before thinking on the problem. Don't waste a lot of time in solving a single problem and go to solve another problem if you get stuck.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I miss participating in Div 3 contests.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

There's an interactive problem in the contest?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Gonna be my very first Contest :-)

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

My first unrated round. All the best and positive delta to everyone participating!

»
21 month(s) ago, # |
  Vote: I like it +34 Vote: I do not like it

omg madoka

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck!!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope for positive delta.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

The picture is so beautiful awa.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

will try to go for 8/8 this time.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Awesome set of problems with the worst problem language ever!!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Madoka

»
21 month(s) ago, # |
  Vote: I like it -19 Vote: I do not like it

Proud of MODI

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

hope to become Specialist in this contest.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

My first unrated Div. 3 :)

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Finally out of competition :)))

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

hello people, whats max positive delta i can get from this contest?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if your rank is 200ish, you can get +200-300 imo if its 1000ish, you can get +150ish if its 2000ish, you can get +100-150 if its 3000ish, you can get +50-90

    you won't go down, as 1st 6 contests generally increases ratings. The above rating list might not apply to you as it's your 6th contest. So expect some more rating compared to above list.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I become expert today?

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I love madoka!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Typo on explanation for D?

In the thir s example, the carvers can choose patterns 14...

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

is it Div. 2 :)

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

It is hard for being div3

»
21 month(s) ago, # |
  Vote: I like it +71 Vote: I do not like it

G2 is almost the same as 2022 ICPC Asia Hangzhou Regional Programming Contest problem I. The only difference is the constraints and input/output format. https://codeforces.net/gym/104090/problem/I

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +103 Vote: I do not like it

    As the writer of the original problem, I am disappointed :(

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      《In Search of Truth》 XD (just joking)

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Hint Of Some Problems :p

A: Divide some no overlapping subarray like x***x. add all * char to the answer.

soln

B: Main tricks is k>=30 cross 1e9 so have to consider onely k=0 to min(k-1,29). if(k>=30) ans=n+1. else ans= min(n+1,2^k).

soln

C: Took every subarray maintain given condition and find all way of that subarray[x= (cnt-k+1) & way= (x*(x+1)/2], here cnt is thw continuous subbarray ne which maintain given condition.answer is summation all such subarray.

soln

D: Use Binary Search.

soln

E: maintain the block in a vector with pos and end time. delete when time arrived. and other swap/check operation can be handled easily.

soln

G1: Find the 1st 1000 number manually using k= +1. Then find every +1000 position difference gap and see which number repeat. its need <=20000 queries.

soln

G2 is a Nice Problem. But can't solve :|

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    please explain the solution for D...

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I fixed the answer as mid. Then 1st person cover the 2m distance from first. Last person cover last 2m distance. Then just check other gap <= 2m or not , which covered by 2nd person. 2m caused, m distance from left and m distance from right.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hello , I seem to have had the right idea for G1,however i recieved "Wrong answer on test 50" as a verdict. Could you please take a look at my code and see if you can spot my mistake ?

    my code
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. did you memset poz[NMAX] to zeroes ???

      local variables might not be initialised to all zeroes ( still depends on the c++ version you are using ) .

      only global variables are assigned to zeroes. try initialising all zeroes and see if it works.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This was indeed the mistake! Thank you very much for pointing it out!

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey Bro! thank you for your hints man! one question in B prob how can we but how can we prove ans = n+1? it would be awesome if you could pls explain or give any reference.

    Thank you for the help.

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      My thought was like, as we can only use (2^i). so every number can be represented by only one 1 way, which is easy to prove which binary representation maintains.. so if we just ignore k (k>=30) then for any n we can make 0,1,2,3,4,5,.....,n and ans is n+1

»
21 month(s) ago, # |
  Vote: I like it +49 Vote: I do not like it

Problem G is quite identical to https://codeforces.net/gym/104090/problem/I

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

My randomized solution 208802508 for G1 worked but I don't know why !!

Can someone please explain?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Randomized would work , mine got WA on test case 16 don't know why :(

»
21 month(s) ago, # |
Rev. 3   Vote: I like it +32 Vote: I do not like it

F: We denotes dp[t][i][j]=1 if we can arrive position (i, j) at time t, 0 otherwise. The initial status is dp[0][0][0]=1, and transition is dp[t][i][j]=dp[t-1][i-1][j] || dp[t-1][i][j-1] || dp[t-1][i][j]. And in each second we need to clear positions shot by railguns. We repeat this process until dp[t][n][m]=1 or for all (i, j) we have dp[t][i][j]=0. The complexity is O(n*m*(n*m+r)).

G1: We can solve the problem by sqrt decomposition: First, we use 1000 queries to get a[1], a[2], ..., a[1000]. If there are any value occurs more than once, we have n<1000 and get the answer. Otherwise, we have n>=1000. Now we can use another 1000 queries to get a[2000], a[3000], ..., a[1001000], we must return to some position in [1, 1000] at some time.

G2: The constraint n<=10^6 is too large for 1000 queries, but how can we solve this problem if we've known that M<=n<M+62500 (=M+250^2)? Well, we can use similar strategy: First use 250 queries to get a[1], ..., a[250], if n<250 we can get the answer. Otherwise, first we assume M<=n<M+250, and we query for a[M+250]. If M<=n<M+250, then 1<=M+250-n<=250, that means we will return back to [1, 250] and we can get the answer. Otherwise, we can assume M+250<=n<M+500 and query for a[M+500], then assume M+500<=n<M+750 and query for a[M+750], and so on. Finally we will solve the problem within 500 queries. So how can we use other 500 queries for finding M? Well, we only need to make 500 random queries and take the maximum value of answers. The probability that maximum value is not greater than n-62500 is ((n-62500)/n)^500, when n<=10^6 this probability is no more than 10^-14, therefore this method will pass 1000 testcases for probability >=(1-10^-11), so it's safe enough.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What's M in solution of G2 ?

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    What was the intuition to use a randomised approach for G2? Or rather what pointed to the idea of using a randomised algorithm?

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      The number of a[i] is fixed initially, so if we make random queries, we will get random numbers uniformly distributed in [1, n], and if we take the maximum value we get, it will be pretty close to n, so we can reduce the number of candidates of answers.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I'm not able to calculate probability that n exceeds M + 62500 ... How to do it ??

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      We make 500 random querise and let M = the maximum answer returned. Since a[i] is fixed initially, n>=M + 62500 means that for all 500 random queries (which will return a random integer in [1, n]) return a value <= n-62500, so the probability is ((n-62500)/n)^500 = (1-(62500/n))^500, when n<=10^6 we have 1-(62500/n) <= 0.9375, so (1-(62500/n))^500 <= 9.67e-15.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone verify my sketch to G2? I couldn't implement it due to school.

For 100 times, RNG a number x between 1 and 9E8 and move -x +(x+300) (call this a "turn"), which basically advances by 300 and also gives a random position using 2 moves

if we get nothing above 90000, we know $$$n<160000$$$ and we can use the G1 solution for the remaining 800 moves else, do 200 more turns and then the max number we visited is probably within $$$90000$$$ of $$$n$$$, so we can advance by that many spots and then increase by 1 for the next 300 moves, which guarantees that we reach something we know the position of and we can determine $$$n$$$

»
21 month(s) ago, # |
  Vote: I like it -12 Vote: I do not like it

My approach for G1 and G2 involved randomization, but infortunately it failed on test case 16, can't figure out why so ? Can someone please explain, will be a great help... Also is there anything wrong with the approach?

Approach :

Store all those sectors you have visited till now, also keep track of how much you have to add i.e. +k or -k. Then if we encounter same sector again then our answer will be distance traveled to reach that sector until now — distance traveled to reach that sector earlier. It would be multiple of some number, we would just find for what multiple the answer exists.

My code

#include <bits/stdc++.h>
#define int long long int

const int N = 1e6 + 1;

int query(char sign, int k){
    std::cout << sign << " " << k << std::endl;
    int ans;
    std::cin >> ans;
    return ans;
}

void print_ans(int res){
    std::cout << "! " << res << std::endl;
}

void solve() {

    int n;
    std::cin >> n;

    int sum = 0;
    std::map <int, int> mp;
    mp[n] = sum;

    int r = rand() % N;
    sum += r;
    int q = query('+', r);

    while(mp.find(q) == mp.end()) {
        mp[q] = sum;
        r = rand() % N;
        sum += r;
        q = query('+', r);
    }

    int d = sum - mp[q];
    int p = q;

    std::set <int> ans;
    
    for(int i = 1; i * i <= d; i++) {
        q = query('+', d / i);
        if(p == q) {
            ans.insert(d / i);
        }
        q = query('-', d / i);
        q = query('+', i);
        if(p == q) {
            ans.insert(i);
        }
        q = query('-', i);
    }

    print_ans(*ans.begin());
    
}

signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    solve();
}
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain Binary Search solution for D? I got the intuition but couldn't do it

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Binary search on the best max time

    let the current check is for number x to see if the max time can be $$$<= x$$$

    x will work if the 3 carvers took the max allowed capacity and the max difference for each caraver items is <= x

    first you will sort the array

    A carver can take items from l to r if $$$⌈(v[r] - v[l]) / 2⌉ <= x$$$

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is still not clear, can you please explain little bit more with detail?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Let's see why binary search works

        let A > B

        if the best max difference for all carvers is less than B then for sure, it is less than A

        Then we can represent all possible answers like this

        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ...
        0 0 0 0 0 0 0 0 0 0  1  1  1  1  1  1  1  1  1  1  1  ...

        which zero means the 3 carvers cannot serve all people wen the max distance is x

        we need to find the smallest max possible distance so, we need to find the first 1, here comes the binary search

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You may want to have a look at Binary Search videos in the Edu section. They present Binary Search on Answer with superb clarity and problems.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How answer to B is k > 30 ? n + 1 : Math.Min(n + 1, 1 << k), basically how number of ways is being counted?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is nothing but the maximum quantity of numbers less than or equal to n which can be represented using k bits.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. Got it — the set bit is literally giving the which all desert you are going to buy.

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    long long a, b;
    cin >> a >> b;
    long long int ans = pow(2, b); // calculates the different ways of bought deserts

    // log2(a) calculates how many deserts he can buy.

    if(log2(a)>=b){
    
        cout << ans;
    
    }
    
    else{
    
        cout << a+1;
    
    }
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think he was not asking for the code. He wanted to know the reason for doing this.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why log2 can you explain ?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        to calculate the number of bits required to store 'a' in binary form

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

When will Editorals come out...? Hoping it!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

could land into double digit rank for the first time, if not hacked

»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

G2: The (de)merit of asking randomization algorithm under the ICPC rules: resubmit makes no damage

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wow! If you submit two times the same code in ICPC and both get WA you only get 1 WA?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      The penalty is #submission $$$-$$$ $$$1$$$ of your first AC (after systest).
      Before systest: WA TLE AC AC WA TLE AC TLE AC -> +2 If systest rejects 3rd and 4th submissions but accept 7th and 9th submissions,
      After systest: WA TLE NG NG WA TLE AC TLE AC -> +6

      If this is usual round, only the last Pretest Passed is used for systest, but ECR, Div3, or Div4, all of your AC can be used for the systest.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain what the statement of Problem A is trying to say?Thanks in advance.

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Given the encrypted string 'a', you must output the original one (let's call it 's'). It says that for every letter 'c' in 's', 'a' has it in the form c------c where '-' is a random letter. For example if s = "pepe", examples of 'a' could be: "ppeeppee" (there are no middle-letters), "papexepfpede" (it has a, x, f and d), "pkkkpekepooopemzzme"

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Can someone check why my binary search solution to D times out? It's supposed to run in O(n log n), but I can't figure out what's going wrong.

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    a

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is advised to avoid using floating point arithmetic whenever possible, with that in mind I changed your code so that it uses an integer ceiling function (line 16), after that change the code got WA on test 3, which was the result of lowballing your hi variable, after changing it to 10**9 it got AC.

»
21 month(s) ago, # |
  Vote: I like it +34 Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

My first contest, solved 4 problems :) Can anyone tell how we can hack anyone's solutions or how to come up with any corner testcase which can be used for hacking? Thanks in advance

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain E and how to solve it ??

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    I solved it with string hashing. If you know what is string hashing the problem is very easy.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I upsolved it with set(but couldn't solve it during the contest).

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    You can use polynomial rolling hash function to hash the given strings. Modifying the hash values for query 1&2 is trivial

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      when u removed the particular hash of tht character in block or unblock wont the further character be affected by this how u tackled this?

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    we can use a set to store the indices of characters that are not equals, on every query of type 2 we update these sets, on every query of type 3, we check to see if any of the indices that are in the set are not equal

    alternatively, we can just check if the number of blocked elements are equal to the number of indices that are not equal (i seen some do this)

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yeah you don't even need the set. Just get a count of the number of different chars between s1 and s2. Every time some modification happens, increment or decrement the diff depending on if the modification made it so more/less chars are now similar. If the diff == 0, it means the strings are identical

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why the downvotes lol? this clearly works

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just maintain a multiset of the differences between s1[i] and s2[i] for each i, and a queue for the the current blocked indices.

    If type of the query is 1: insert the index into the queue of the blocked with the time when it will be unblocked. remove s1[p] — s2[p] from the multiset.

    If type of the query is 2: Just case work, remove the old differences of pos1 and pos2 from the multiset then update the string then insert the difference again.

    If type of the query is 3: The answer is YES if all differences between s1[i] and s2[i] == 0, it's easy to check that from the multiset.

    And don't forget to remove the unblocked indices at each iteration and insert the difference to the multiset again.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks everyone

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have much simpler approach to solve E .

    Just maintain all the mismatching index in set. Whenever you block the mismatching index, remove it from set and add it into blocking cells( u will release this lock right before 'i' + t query).

    have look at my code for better understanding I have written comments as well.

    my solution : https://codeforces.net/contest/1840/submission/208829151

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

NumberOfWaysForces :))

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How did D get so many solutions? It was extremely difficult.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone pls give me any hints for problem F?

»
21 month(s) ago, # |
Rev. 6   Vote: I like it +9 Vote: I do not like it

Solved problem 1840E - Character Blocking in $$$O(q\times n$$$). Submission. It works because comparison of two strings in C++ works in $$$O\left(\dfrac{n}{16}\right)$$$ (it is possible to compare $$$16$$$ bytes ($$$256$$$-bit registers) per single operation by activating GCC pragmas).

UPD. Hacked!

UPD 2. Wrote new solution which is still alive.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can some1 please kindly point out what is so terribly wrong with my solution of E: 208819873.

I tried looking at the tests (my solution fails exactly on second pretest token number 5352, test case number appears to be 1665) but it doesn't make much sense to me because the strings appear to be in uppercase (unless I'm missing some silly mistake with my input).

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    nvm i got wrong.. t didn't change

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      But aren't the queries coming only at integer moments in time (like t1 = 1, t2 = 2 and so on)? Also since we can block only one position at a time and the interval t is constant, doesn't that imply that we can only "unblock" one character at a time, the queue is going to be sorted by itself (unless I understood the problem statement wrong).

      My solution using a good old map<char, int> didn't pass as well, so the issue is most likely not in the lower/uppercase inputs.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    electric_boogaloo Did you find any tc? I'm also failing idk y

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      got it

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Same, something like:

        1
        lf
        nf
        13
        4
        2 2 1 1 1
        3
        1 1
        3

        fails (getting NO after the block of first characters, when the strings should be equal)

»
21 month(s) ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

I try to hack the solution of problem F using the following generated test cases, and it just give me "unexpected verdict", what is happening, can problem author fix this?

import sys
sys.stdout.write("10000\n")
for _ in range(10000):
    sys.stdout.write("1 1\n")
    sys.stdout.write("100\n")
    for i in range(100):
        sys.stdout.write(str(i+1)+" "+str(1)+" "+str(1)+"\n")
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why when i try to hack i have message : Validator 'validator.exe' returns exit code 3 [FAIL Expected integer, but "��1" found (stdin, line 1)]

Also whole test on codeforces has a lot of this random "�" question marks.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are you trying to hack using a text file or genenerator (code to generate the input)? Can you paste the hack test / generator code in a comment? It's very difficult to say what is happening without more information.

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I'm generating test like this : ~~~~~ int32_t main() { string a = ""; int n = 26033, q = 26033; for (int i = 0; i < n; i ++) a += 'a'; cout << 1 << '\n'; cout << a << '\n'; cout << a << '\n'; cout << 2 << ' ' << q << '\n'; for (int i = 1; i <= q; i ++) { cout << 3 << (i == q ? '\n' : ' '); } return 0; } ~~~~~

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        First of all, queries should all be on separate lines (not space-separated), but that isn't what the validator is complaining about.

        I tried to hack a solution using your generator in hack -> generated input, and the only thing the validator was complaining about was what I mentioned above.

        Did you generate the code like this and copy-paste the output into the hack? That might be the reason the input seems invalid.

        P.S: Please format your code by placing "~~~~~" (without quotes) on a line before and a line after your code.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I was generating to the txt file and it seems like there are for some reason invisible "�" marks. I can see them when I open file in visual studio.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Copy pasting works, before i was sending file.

          Do you know btw why 256kb is max size of test for hacking? It's impossible to create max test ;d

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You can send a code file that generates the test case on the server by selecting "generated input" instead of "manual input" on the top of the hacking interface. If you do this, there is no limit on the size of the test case.

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

PLEASE TELL ME THE INTUITION BEHIND THE G1/G2 PROBLEM???

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you look carefully at the limit of number n and limit of queries, it gives the vibe of divide and conquer, since most commonly used division is by ✓n.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Reads problem statement for D, sees that time limit is 3s => neuron activation => immediately starts coding out binary search.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

F: Holy, the TL is magically changed 3s instead of 1s, and my 100+ successful hacks are disappeared and left -85...

My hacking case is here, this isn't exist in the pretest:

1
10000 1
100
10000 1 10000
10000 1 10000
...
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Look up for xuhao95's post.

    Looks like that case makes the input really big. I guess std got TLE on reading the data.(I would also guess most solutions got TLE on reading the data.)

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      No, this testcase satisfies the constraint and it's only about 100 lines.
      This testcase kills unnecessary $$$\log$$$ or something with $$$O(nm(n+m+r))$$$ and should be included as a pretest. (sorry, the testcase of my first post contains unnnecessary 1)

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        I was talking about why they magically changed the TL from 1s to 3s.

        I know your case is good and strong and killed many solutions, but it's accidentally affected by the incident of that case.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          I see. The problem is $$$\Sigma r$$$ isn't bounded and the input can be $$$10^6$$$ lines then, for safe io, the TL was raised to 3s and it affects my usual hack. sad...

»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

AC A,B,C,D. It's so good!!! Thanks diskoteka,pavlekn,playerr12,isosto and their friends for this great contest.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

A very good div3 has increased my rating

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I am not a trusted participant (I had given only 2 contests before this), will my rating get increased on the basis of this contest?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Your question would have been answered if you had read the blog once...

    It's even in bold!
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I did read that and thought it would be rated, but it doesn't show in my profile as rated. It shows in all contests. Hence why I asked the question.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        You need to wait,it takes times.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Sees D -> Sees "Best" Waiting time -> Gets a Déjà vu -> Speedruns BS at the last f minute -> Gets Satisfaction

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for problem D was hacked. I used binary search and the complexity is O(nlog(n)). I don't know how it is hacked. this is the submission 208804659

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same happened to me. I noticed that this guy hacked only pypy3-64 solutions, so i guess it's a pypy3-64 problem

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

when will be rating updated?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1840/submission/208820120

I don't know where I am wrong. Help me!

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Bro, for query type 2, after swapping, They might get equal, If they become equal. Why you are not removing that index from set.... Try This.. I hope it might work....

    if(s1[xp]==s2[xp]){
            if(mp.count(xp)) mp.erase(xp);
          }
    
          if(s1[yp]==s2[yp]){
            if(mp.count(yp)) mp.erase(yp);
          }
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

A good game!

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Why rating updated without system testing?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone run my code? It prints correctly in my computer.

https://codeforces.net/contest/1840/submission/208770610

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Div 3 = 1 easy question + div2

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me to take a look at my Code for Problem E? I have been reviewing it for more than 1 hour and asked people around me, but I couldn't identify the issue.208953748

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Found a bug, the boolean addition used in the middle may overflow.But it still didn't pass.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Also found that boolean will translate to int so it will not overflow at all.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just move this comment to tutorial.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

I got a message from the codeforces team that my code for problem 1840C (submission 208741874) is matching with DEAD_TCT's submission, I swear I didn't share my code with anyone else, it's a coincidence. The python code was very short and the problem is easy so everyone familiar with Python ended up with more or less similar code, And my submission time is far before his submission time. I have recently started giving contests regularly but this kind of thing will demotivate me. I request team to kindly look into this issue.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I looked at both submissions and I must say that it does seem pretty believable, at least to me, that this is a coincidence (I just chanced upon this comment while idling around recent actions).

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

I write to you first time because this time I really not break any rule , you send me notification like that "Your solution 208761272 for the problem 1840B significantly coincides with solutions satyam9696/208761272, _souhardya/208772620", first of all I really don't know him who is he , first time i visit his profile after your notification. I also not used or neither upload any code on ideone( I don't know what is this). one thing i want to say ,the question for which you give me notification it really have small code ,I think in too many people two-to three people can have same code for a 6-7 line answer of code. it is just like for summation of two number everyone write a+b. once again i want to say i not copy any one code you can also see my wrong submission of that question, i was making really small mistake again and again than i write fresh code and it pass that's it. please see into it.

»
21 month(s) ago, # |
  Vote: I like it +18 Vote: I do not like it

Few days ago there was a problem with my laptop. So I used one of my friends laptop to participate in some contests.I forgot to logout from my account from his laptop. Now that guy logged into my account and copied my solution during the contest. I had no idea about the incident until I got a message from codeforces. I Don't know what kind of proof would be accepted or how can I prove what I'm saying. But I'm doing contests and upsolving for years in codeforces without any violation of rules. I would be grateful if you consider the situation and avoid giving me any penalties.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

emmm so how can i become a tester:)

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

I got a notification that my submission of 1840B 208789335 is copied. I just modified my previous submissions 208747728 and 208761375 This is clear proof that I didn't copy. after getting the wrong answer for my first submission to 1840B, I switched to the next question. Then again I checked my previous submission, and what was wrong with it and I modified and submitted it again. You can check my submissions. There is not much difference from my previous submissions.

»
21 month(s) ago, # |
  Vote: I like it +29 Vote: I do not like it

Keep learning because life never stop teaching.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are the ratings for this contest rolled back?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool round, I finally made it to blue)

»
20 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

deleted