flamestorm's blog

By flamestorm, 2 months ago, In English

We hope you enjoyed the contest!

1915A - Odd One Out

Idea: flamestorm

Tutorial
Solution

1915B - Not Quite Latin Square

Idea: flamestorm

Tutorial
Solution

1915C - Can I Square?

Idea: SlavicG

Tutorial
Solution

1915D - Unnatural Language Processing

Idea: flamestorm

Tutorial
Solution

1915E - Romantic Glasses

Idea: flamestorm

Tutorial
Solution

1915F - Greetings

Idea: mesanu

Tutorial
Solution

1915G - Bicycles

Idea: SlavicG

Tutorial
Solution
  • Vote: I like it
  • +77
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the editorial!

»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

This was a standard div 4, I believe previous div 4s were harder than this. Good contest regardless!

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

For anyone who wants to know more about similar problems like G.

Here is a great blog on shortest path modelling:

https://codeforces.com/blog/entry/45897

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
for _ in range(int(input())):
    n=int(input())
    arr=list(map(int,input().split()))
    newarr=[]
    sl=0
    sd=0
    for i in range(n):
        if i%2==0:sl+=arr[i];newarr.append(sl)
        else:sd+=arr[i];newarr.append(sd)
    
    # print('newarr',newarr)
    
    d={0,-arr[0]}
    f=False
    for i in range(n-1):
        if i%2==0:
            diff=newarr[i+1]-newarr[i]
            if diff in d:f=True;break
            else:d.add(diff)

        else:
            diff=newarr[i]-newarr[i+1]
            if diff in d:f=True;break
            else:d.add(diff)

        if f:break
    if f:print("YES")
    else:print("NO")

        

why does this give TLE in E?anyone

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am not sure but in python checking if f in d: takes enough time to make it TLE, I have encountered this while doing a problem in CSES. Everything else looks fine to me.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      d is a set, its O(1) to my knowledge

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, actually I also used to assume its O(1) always but I guess a while ago I found out through someone's issue in a CSES problem that it is O(n) in worst case. As sets are implemented trough hash tables in python. So you can expect to lookup/insert/delete in O(1) average. Unless your hash table's load factor is too high, then you face collisions and O(n). You can find further information here.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Lookup and insertion of set can be O(n) if it's filled with values that cause hash collisions. Apparently it's possible to craft a very bad input that makes Python's (or Pypy's) set run very slowly.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

int the third question if i put r = sum(the sum of all number) instead of 1e9 then it fails in testcase 3. why is that happening?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The maximum of sum is 2E14, and 4E28 after squared it.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i can't understand? does it mean it cause overflow error?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        long long maximum is about 9E18

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I had the same problem on testcase 3 too, it causes overflow error, just use long long and it should be accepted :)

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          did use long long , still showing runtime error

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            use long long for every integer variable you are using. the root and the sum both should be long long.

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I kept my promise, I can die with a clear conscience.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell where i am going wrong in this solution wirtten by me for G. 239395920

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See using a 2D visited array and 1D dp state for dijkstra won't work as it might be possible that let say a node 1 was visited first time by bike of node 0 let say and got distance 30 then it got visited by node 5 by some other bike at dist 45 then it got visited again as dist 34, node 1 , bike from 0 as though it was marked visited but dist 34<45 contradicting to 30<34 giving us wrong answers on TC#2.

    Wrong Code
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can someone tell why is this approach is wrong

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      1
      4 4
      1 2 1000
      1 3 1
      2 3 1
      2 4 1
      1 1 1 1
      

      Also you are marking nodes as visited and not clearing it when the value is in your hashtable blocking that path until the next test case.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Understood the test case

        Can you also give a better explanation why is it failing and why if we do like this it fails for this question

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          DFS is awkward for shortest paths. In the test case the first time you visit node 3 you've already visited 1 and 2. This doesn't leave any options for continuing from 3 so you cache it's value as INF. Then when you start to follow the shortest path (1->3->2->4) you reach 3 and return the cached value (which is incorrect).

          You'll notice that my example test case all the bicycles have the same value making the problem into a very simple shortest path on weighted graph problem.

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

why my soln of F fails for this test case:

from bisect import * I=lambda:map(int,input().split()) rr=range for _ in rr(int(input())): n,=I() an=0 l=[list(I()) for _ in rr(n)] l.sort() k=[] for i in rr(n): ind=bisect(k,l[i][1]) an+=len(k)-ind k.insert(ind,l[i][1]) print(an)

test case: 1 200000 -999999999 999999999 -999999998 999999998 -999999997 999999997 -999999996 999999996 -999999995 999999995 -999999994 999999994 -999999993 999999993 -999999992 999999992 -999999991 999999991 -999999990 999999990 -999999989 999999989 -999999988 999999988 -999999987 999999987 -999999986 999999986 -999999985 999999985 -999999984 999999984 -999999983 999999983 -999999982 999999982 -999999981 999999981 -999999980 999999980 -999999979 999999979 -999999978 999999978

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

here is my code for f using binary index tree. https://codeforces.com/contest/1915/submission/239413594

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my E's solution got hacked for this testcase? Both the editorial's and my solution is giving "NO" as output.

int main(){
    cout<<"1\n200000\n";
    for (int i = 0; i < 100000; ++i)
    {
        if (i != 0) cout << ' ';
        cout << "1 107898";
    }
    cout <<endl;

    return 0;
}

My code:

int main() {
    tc {
        ll n; cin >> n;
        vector<ll> v(n);
        for(int i = 0; i < n; i++) cin >> v[i];
        if(n == 1) {
            cout << "NO" << endl;
            continue;
        }
        bool flag = false;
        for(int i = 0; i < n - 1; i++) {
            if(v[i] == v[i + 1]) {
                flag = true;
                break;
            }
        }
        if(flag) {
            cout << "YES" << endl;
            continue;
        }
        flag = true;
        unordered_map<ll, int> mp;
        ll pre = 0;
        for(int i = 0; i < n; i++) {
            if(i & 1) pre += v[i];
            else pre -= v[i];
            if(pre == 0) {
                cout << "YES" << endl;
                flag = false;
                break;
            }
            mp[pre]++;
        }
        if(flag) {
            for(auto it : mp) {
                if(it.second > 1) {
                    cout << "YES" << endl;
                    flag = false;
                    break;
                }
            }
            if(flag) cout << "NO" << endl;
        } 
    }
    return 0;
}
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I am not sure, but maybe because of unordered map? Here: https://codeforces.com/blog/entry/62393

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, when I used unordered_map it was giving TLE but when I used simple map it got accepted. But why?? Also unordered_map complexity is better as compared to map.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Because average TC of unordered_map is O(1) but in worst case it can be O(n) in case of collisions, test case is specifically created to have collisions, that's why read the above blog and learn from it.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh now I understand! Thanks a lot for the help!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Insert in unordered_map is usually O(N), so your overall complexity goes from O(N) or O(NlogN) to O(N^2). Unordered_map uses hash tables, so if you come up with tests anti-hash tables you’re gonna get hacked because of TLE

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

Can anyone give the reasoning, on why a normal dijkstra won't work for problem G ? We are asked to find the path that takes minimum time from node 1 to node n.

can't we just update the distance to a node based on this? d[v] > d[u] + min(k, s[u]) * w[u][v]

why are we storing d[v][s] ? why do we need 2d array to calculate shortest distance to node v using slowness s

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you might go to a node just to achieve it's slowness factor and then come back from where you came.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Cause we need to update larger distances also if we come from a speeder bike as it may cost us less in future travel to nodes. As in test case 1 we have to update or store dist to node 2 (1 base) i.e 13 though shortest is 10 since we came from a speeder bike. It would not be stored in 1D dijkstra giving wrong answer of 10+6*2=22 rather than 13+(6*1)=19.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone help in question 6. How is this standard problem

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Basically we just want to count how many pair (i, j) that a[i] > a[j] and b[i] < b[j]. Because this is the necessary and sufficient condition when people i and people j meet at the same point.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

e can also be solved easily by creating prefix sum array for even and odd indices we need to find even[j]-even[i]=odd[j]-odd[i] which is equivalent to even[j]-odd[j]=even[i]-odd[i] so just store the difference array of even and odd prefix sum if any value repeats answer is "yes" else "no"

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain E to me?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explaine why this approach to E not working ?

approach
code
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check my code!difference logic is correct but it gives TLE on testcase 14 mainly due to use of sets .

»
2 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Can anyone please explain why the below solution fails for problem G:

Approach: A slight modification of the Dijkstra's Algorithm. We calculate DIS [ i ] [ j ] to be the shortest path to reach from node 1 to node ' i ' with bike of slowness factor ' j ' . Update the DIS array when a new path having shorter distance is encountered with bike of same slowness factor.

Submission link 239402842

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You are updating mins. But when going a -> b where mins at a was 10 and b would become 5, you are calculating time using 5 * edge weight. Note that to reach b you should use 10 * edge weight, use updated mins after that.

    Edit: code here's mine with the same idea

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      The fault actually lied in the initialisation of the distance array. The initial config of dist array has to be INF for all values except 1 , slow [ 1 ] as opposed to my initial config where all values of slowness had been set to 0 for node 1, hence the WA.

      Here is the updated one :

      239790511

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand the sentence in the E problem, " Be careful about using hash tables, as they can be hacked.". Could anyone explain this?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this round unrated for me?

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone show me how to solve F without ordered_set? Maybe with Fenwick tree or something else?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can sort by leftmost point (i.e. a[i]) and then iterate from back to front. You will first need to do coordinate compression of b[i] values (for that you can use a map). After that when you are at i , all j > i satisfy a[j] > a[i] and you will query fenwick(map[b[i]]) , to get number the elements which are less than b[i].

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this code for problem c is not working? (https://codeforces.com/contest/1915/submission/239353207)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The input was upto 10^9 thats why it wasnt working,you should have used LongLong as ModifiedCode

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have tried that earlier it wasn't working.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but i submitted the modified code and it got AC

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The input of the array and initialisation fo sum variables are wrong,as max(int16_t) <10^9 so you wont be able to store it in first place.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          check last reply 239299477

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            The problem is float k=sqrt(sum) consider sqrt(sum)=999999.9991 the value of k that will be used is 10^6 and for the same value int j=floor(k) // == 1e6 which will make them equal to each other making the YES but the answer should have been NO,so to correct it use double k in the same code,you will get AC

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            To avoid all this take a look at myCode

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone hack this solution for problem G? 239328319

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why this code for problem d is not working for following test 22 dababbabababbabbababba

include <bits/stdc++.h>

using namespace std;

int main () { int t; cin >> t; while (t--) { int n; cin >> n; string s; cin >> s;

for (int i = 0; i < n;)
{
  if (s[i] == 'a' | s[i] == 'e')
    {
      if (s[i + 1] != 'a' & s[i + 1] != 'e' & s[i + 2] !=
      'a' & s[i + 2] != 'e')
    {
      if (i + 2 >= n - 1)
        break;
      s.insert (i + 2, ".");
      i += 2;
    }

      else
    {
      if (i + 1 >= n - 1)
        break;
      s.insert (i + 1, ".");
      i += 1;
    }


    }
  else
    i++;
}
  cout << s << endl;
}

return 0; }

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
for _ in range(int(input())):
    n=int(input())
    arr=list(map(int,input().split()))
    for i in range(0,n,2):arr[i]=-arr[i]
    s=0;pres=set();f=False
    pres.add(0)
    for ele in arr:
        s+=ele
        if s in pres:f=True
        else:pres.add(s)

        if f:break
    if f:print('YES')
    else:print('NO')

TLE on test case 14?help!!!!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If I get a input for which like everyone gets hacked due to TLE, i can only apply in a contest to a limited people but whosoever i put they get hacked,

Shouldn't there be system testing for all the successful hacks afterwards with those inputs on all users???

Ain't it unfair?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    to my knowledge solutions do get retested after the hacking phase with the use of new hack-inspired tests

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, it doesn't atleast what i know for div 3 and 4, you can do as much hack as you can with the same generator code, but even if successful it won't be tested on ohters, me and my friend had same logic my got hacked his not.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        last div3 got retested tho. maybe it will be retested a bit later?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Maybe, let's wait and watch

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            oh, did your solution use unordered_set or unordered_map? it might be the reason you got hacked, average comlexity of it is linear, but if there are too much collisions it can be o(n), people use this to make others solutions get tle, so try not to use it, there was a post about unordered map and etc. so read it if you have free time

            upd.: here is a link https://codeforces.net/blog/entry/62393 upd.2: average complexity is constant, not linear, sorry

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              ohhh alright, thanks a lot for sharing, didn't had much knowledge about it, still at basics

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

good contest but some solutions for g should not be accepted due to overflow

look at this one

https://codeforces.com/contest/1915/submission/239403382

curr is int and it should be long long upd: didn't know system testing hadn't been finished

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why me solution got AC? it has a time complexity of n^3 https://codeforces.com/contest/1915/submission/239328701

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

in this Submission,the verdict says wrong answer and the reason is wrong output on the testcase

ABC ?CA CAB (4th case of test 2)

However , my program works exactly well with this testcase as well .

Is there any error from codeforces side?

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it
    Code where error exists
    Hint
    The error
    Solution
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much for pointing that out! One of the last things I would expect to create a error!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanx a lot for this round! I really got my spirits up. :))

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why this fails in Test case 26 for Problem G

submission

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nvm just needed to change long long to unsigned long long

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain testcase 1 in problem G

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the best solution is this way:

    Node 1 to Node 2: cost = 0 + 5 * 2 = 10;

    Node 2 to Node 3: cost = 10 + 1 * 2 = 12;

    Node 3 to Node 2: cost = 12 + 1 * 1 = 13;

    Node 2 to Node 4: cost = 13 + 5 * 1 = 18;

    Node 4 to Node 5: cost = 18 + 1 * 1 = 19;

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Damn, my solution for the E got hacked because I was using the unordered_map :( I know how it can be fixed just so funny that I was getting caught on this again

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me explain problem G. I didn't understood the editorial

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

[1st submission][2nd submission]

these are my two submissions to problem F , the only difference between these two submissions is that one has (#define int long long) and in other submission I commented that line , the one with (#define int long long ) got TLE whereas the submission without this got AC, why so and how can we avoid this TLE?

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can we use DP in any way to find the solution for problem G?

I know we can go with some modification of dijkstra's algorithm, but was wondering if any one has done it differently.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain how can i find number of pairs of segment such that one completely lies inside anohter , inorder to solve F

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sort the input based on the starting position then for segment i all the segments j such that i < j < n and ending position of j is less than i will completely lies inside segment i

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem F, after sorting, its actually just Kendall tau distance, which can be solved in O(nlogn) with segment/fenwick trees or with some divide and conquer techniques, related to merge sort and quick sort

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain to me why do I get TLE when I use unordered_set in PROBLEM G? When I changed it to set, I got AC.


void solve() { std::cin >> n; std::vector<int> a(n); for (int i = 0; i < n; i++) std::cin >> a[i]; long long s = 0; std::unordered_set<ll> st; st.insert(0); for (int i = 0; i < n; i++) { a[i] *= ((i % 2) ? -1 : 1); s += a[i]; if (st.find(s) != st.end()) { std::cout << "YES\n"; return; } st.insert(s); } std::cout<<"NO\n"; }
  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    link to blog. unordered map set work on hashing so it can tle if inputs are intentionally generate to cause large no of collisions it's better to use so it's better to use set and map in contest

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

We can solve problem F by using merge sort algorithm.

You can count the number that smaller the current number and before it in the second element of pair after sort it by nondecreasing sort.

This is the code: https://codeforces.com/contest/1915/submission/239384276

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem-F can also be solved using Fenwick tree? If yes, then can someone please explain the solution using Fenwick tree.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i assume that you know that in problem can be simplified to counting the inversion in an array to do this you can assign each element A[i] to it's index in sorted order like A = {5, 7 3, 2, 9} sorted A = {2, 3, 5, 7, 9} now you assign each element to it's relative index like (5 => 3), (7 => 4) and so on now A becomes A = {3, 4, 2, 1, 5} notice that all the elements in A are now between 1 and n. now assume you have visited array vis and a an array B which stores the prefix sum of vis array now iterate on A in reverse order and add B[A[i]] to you'r ans. why? it's because if you see carefully B[i] stores no. of elements < A[i] that are already visited and update the vis array vis[A[i]] = 1 and recalculate the prefix sum array B. the complexity of this O(n^2) now you can do the same thing in fenwick tree using point updates so it will be O(n*long(n)). you can learn fenwick tree from here hope it helps and sorry for my bad english.

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

please dont freeze the contest need to upsolve it not able to submit code now

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    after system testing it will be open for practice

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C, why sqrt doesn't get TLE?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved 5 questions during the contest and now it is showing only 2 correct and 2 incorrect while the 5th is unsolved. Why is that ?

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

IN problem E. Romantic Glasses TEST case 6: 2 5 10 4 4 9 6 7 8

why answer "YES"

there is no possiblity of equal subarray from (l,r)???????????????????

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for editorial !

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, can someone explain why using a hashtable leads to a TLE/hack?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

now its 24 hrs,why we are not getting our ratings?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

has anyone solved F without using segement or fenwick tree in python? using bisect insort to keep a sorted list gives TLE on 11

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

worst thing about div3,div4,educatioonal is this ,rating is changed after two ,three days, Guys if you think its so tough then stop making this rounds or Change something to be faster.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i wrote the solution of E using unordered_set but it somehow gave tle, then i changed it to set and it got accepted. Can anyone explain why this happened?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because in worst case Unordered set's runtime is O(n), for set it's O(log(n))

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

Could anyone please provide some reference material for the problem of counting the number of pairs when one fully contains another, described in the editorial of F?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Need help with C. Took inputs as long long, added them. Take l=0, r=total, k=0. While(l<=r){ m = l+(r-l)/2; if(m*m <= total) k=m, l=m+1; else r=m-1; } At the end if(k*k != total) print No else print Yes

I am getting Wrong Answer at case 3. Please, point out what I did wrong. Submission

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think the upperbound of your binary search is too big. you should change the upperbound to somewhere at 2e7 (or sqrt root of 2e14)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much. Now I got it. m*m exceded 1e18 limit which caused junk calculation. I copied the comment to sent people from my friend list for disscussion but now I got it. Thank you so much.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Insertion for vector is O(N) on average.

    Your solution's time complexity is O(N^2) imo.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand how to solve Problem E? Didn't find the tutorial helpful.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This contest in Very nice (A and B and C) but D..E.. don't try Tge Author is very smart I salute him I hope he sees my messages To all authors

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

Can someone please look at the following code snippet (for problem 1915-F), and tell me why it gives TLE on test case #3: (And please bear with my excessive usage of macros, i hope you understand what the code is doing.)

bool comp(pair<int64, int64> a, pair<int64, int64> b) {
	return a.first < b.first;
}
 
void solve()
{
	inp(n);
	multiset<int64> mst;
 
	vector<pair<int64, int64>> ab(n);
 
	lp(i, n) {
		inpp(ab[i].first, ab[i].second);
	}
 
	sort(all(ab), comp);
 
	uint64 ans = 0;
 
	lp(i, n) {
 
		ans += (uint64)distance(mst.upper_bound(ab[i].second), mst.end());
		dbg2(i, ans);
		mst.insert(ab[i].second);
 
	}
 
	out(ans);
	return;
}
»
2 months ago, # |
  Vote: I like it +33 Vote: I do not like it

First of all thanks for the nice problemsetting. SlavicG, mesanu, flamestorm

I have a slightly different solution for problem G, here is how it goes:

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

From what I understand, to anyone reading this, the reason your solution to part E was hacked was probably because of using an unprotected hashmap. Usually it's O(1), but people have looked into source code of both python and c++ and have found ways (you can find, they're on codeforces blogs) to make a dictionary have lots of collisions, in rough terms causing the dictionary to go from O(1) to O(n^2). A simple fix (in Python) is to convert integer hashes to strings (although this might cause a performance drop), or to create your own hash function (in Python you can create a very large random number and put the keys XOR's to that number).

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

For question 3, the max sum is 2E14 whose square root is ~1.4E7 or ~1E7. So having right bound of 1E9 is more than sufficient to get correct answer. This can be done using 64-bit integer since max square is 1E18 which can fit in 64-bit integer without overflowing.

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

.nvm

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

In the tutorial of F, the explanation says "for each of them add the number of segments that we have already passed that have an a value larger than the one of the current segment." Shouldn't it be smaller instead of larger as we have B sorted in increasing order ? Edit: I got it

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

In Problem E can anybody tell why solution gives TLE when I use unordered map and gets accepted when I use map

void solution(){ ll n; cin>>n; vector a(n); unordered_map<ll,ll> mpe; ll sume = 0,sumo = 0; for(auto &it:a) cin>>it; for(ll i = 0; i < n; i++){ if(i % 2 == 0){ sume += a[i]; }else{ sumo += a[i]; }

    ll diff = sumo - sume;
    if(diff == 0 or (mpe.find(diff) != mpe.end())){
       cout<<"YES"<<endl;
       return;
    }

    mpe[diff] = i;
}

cout<<"NO"<<endl;

}

int main(){ ll t; cin>>t; while(t--)solution(); return 0; }

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A more efficient (and prolly simpler) code for G as it does not require a 2D array: https://codeforces.com/contest/1915/submission/239576580

It's just Dijkstra with time as the parameter, but when I push cities into the priority queue, I also store the minimum slowness with which I will leave the city, once I visit it (the minimum between the slowness with which I entered the city and the slowness of that city's bike). Instead of a "visited" array, I made an array which stores the minimum slowness with which I have left the city, if I have visited it. So when I visit a city again, I carry on with that iteration only if the slowness with which I am entering the city is strictly lesser than the minimum slowness with which I have exited the city before, otherwise I continue with the next iteration.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someoone teach me G in a little more detail I don't know much about creating a new graph with state data.

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

For problem D this also works:

  for(int i = 1; i<n-1; i++) {
    if(s[i]!='a' && s[i]!='e' && (s[i+1]=='a' || s[i+1]=='e')) dot[i] = true;
  }
  for(int i = 0; i<n; i++) {
    if(dot[i]) cout<<'.';
    cout<<s[i];
  }

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F1915F - Greetings

My Submission — 239523874

My solution got TLE due to distance function which results in overall worst case complexity of O(N^2). To resolve this problem we can use order statistic tree, but I have no prior knowledge of it. Can someone please share any good resource such that I can understand the concept behind the order statistic tree.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone suggest good resources to learn about ordered set?

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

My G did not withstand system test.

https://codeforces.com/contest/1915/submission/239379244

Subtle bug in Djikstra implementation, try to find it if you like. (Note: I know what it is and I think it was a great way to learn something through the contest, won't make the same mistake again now.)

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

could someone explain why my code is failing in 26th test case this is for problem G ~~~~~ //Ram Ram

include <bits/stdc++.h>

include<ext/pb_ds/assoc_container.hpp>

include<ext/pb_ds/tree_policy.hpp>

using namespace std; using namespace __gnu_pbds;

define ll long long

define int long long int

define _test int _TEST; cin>>_TEST; while(_TEST--)

define ff first

define ss second

define pb push_back

define ppb pop_back

define all(x) (x).begin(),(x).end()

define fr(i,s,e) for(int i=s;i<e;i++)

define read(x) for(auto &i:x) cin>>i;

define write(x) for(auto i:x) cout<<i<<" ";

define input(n) int n; cin>>n;

typedef tree<int,null_type,less,rb_tree_tag,tree_order_statistics_node_update>pbds;//find_by_order,order_of_key

signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

_test
{
  int n,m;
  cin>>n>>m;
  vector<pair<int,int>>adj[n];
  for(int i=0;i<m;i++){
    int u,v,w;
    cin>>u>>v>>w;
    u--;
    v--;
    adj[u].pb({v,w});
    adj[v].pb({u,w});
  }
  vector<int>s(n);
  read(s);
  vector<vector<int>>dist(n,vector<int>(n,INT_MAX));
  dist[0][0]=0;
  priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>q;
  q.push({0,{0,0}});
  while(!q.empty()){
    auto pr=q.top();
    q.pop();
    int curr_dist=pr.ff,curr_node=pr.ss.ff,curr_bike=pr.ss.ss;
    if(curr_node==n-1){
     cout<<curr_dist<<"\n";
     break;
    }
    for(auto it:adj[curr_node]){
     int added_dist=it.ss*s[curr_bike];
     if(curr_dist+added_dist<dist[it.ff][curr_bike]){
         dist[it.ff][curr_bike]=curr_dist+added_dist;
         int bike=curr_bike;
         if(s[it.ff]<s[curr_bike]) bike=it.ff;
         q.push({curr_dist+added_dist,{it.ff,bike}});
     }
    }
  }
}

} ~~~~~

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Below code for G gives tle on t.c 3 . maybe coz of heap, what alternative should i use then?any help would be appreciated

for _ in range(int(input())):
    n,m=map(int,input().split())
    g=defaultdict(list)
    for _ in range(m):
        u,v,w=map(int,input().split())
        g[u].append([v,w])
        g[v].append([u,w])
    bike=list(map(int,input().split()))
    
    st=[[0,1,bike[0]]]  #[cost,node,bike speed]
    total=0
    while st :
        out=hq.heappop(st)
        if out[1]==n:total=out[0];break
        for ch in g[out[1]]:
            hq.heappush(st,[out[0]+ch[1]*min(out[2],bike[out[1]-1]),ch[0],min(out[2],bike[out[1]-1])])
    
    print(total)
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    one more thing! keeping track of visited nodes is giving wrong results, why so?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, my solution is failing on judge test case 3.
I tried to get the full input but the viewer trims it. Does anyone know how to get the full test case?

If not, can someone please help me figure out the bug in the solution?

https://codeforces.com/contest/1915/submission/239760036

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

why is unordered_map not working but normal map working?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me to find what's wrong with my solution please? (My code for 1915E — Romantic Glasses). It's getting wrong answer on test case 3. My code is in JAVA. I've tried my best but can't find anything :(

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In your last for loop, compare in the following way because on comparing def.get(i)==def.get(i-1), it is comparing the references not the value.

    for(int i=1;i<=n;i++){
       long a=def.get(i);
       long b=def.get(i-1);
       if(a==b){
       ans = "YES";
       break;
     }
    }
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ooooh, I see. It returns Long which is an object not a primitive type. Thank you so much :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hello do any one knows similar types of problems like F?? (on pbds or similar)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi if anyone is solving using java, can someone explain why I am getting tle for the 3rd test case for F My approach is this : create pairs of start and ends, then sort pairs based on starts, Iterating through the list incrementing ans with number of elements greater than the the end of the current pair, then adding the end of current pair to the set.

to find the elements greater than end of current pair, I am using the method tailSet from TreeSet method, which is supposed to take log n (according to some sources online) I am thinking if it can be done without implementing a custom self balancing tree, it would be great, let me know what approaches you guys used.

this is my code Thanks In Advance!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why Dijkstra in G problem is not getting TLE verdict? We have n^2 vertices, for each vertex we traverse m edges, which should be at least O(n^2 * m) yet author's solution's passing with no probs. Where my logic gone wrong? Or I guess don't understand Dijkstra at all LOL

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dijsktra's time complexity, when using priority queue is O(E + VlogV), you can refer to the : proof here

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is a good question, and flamestorm or SlavicG should've presented a more elaborate complexity analysis in the editorial.

    We have $$$V = 1000n$$$ vertices, but we do not traverse all $$$m$$$ edges for each vertex. Instead, each edge $$$(u, v, w)$$$ is traversed at most $$$2000$$$ times: once from each of the vertices $$$(u, 1), (u, 2), \ldots, (u, 1000)$$$ and $$$(v, 1), (v, 2), \ldots, (v, 1000)$$$. Hence, the total number of edges is $$$E \le 2000m$$$.

    The time complexity of Dijkstra's algorithm as implemented in the editorial is $$$O((E + V) \log V)$$$, which for $$$n = m = 1000$$$ has an upper bound of roughly $$$60 \cdot 10^6$$$.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, that was insightful, thanks!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for problem E was failing on test 16 due to TLE, even though it uses a similar approach to the official solution. I replaced unordered_set with set and it passed. Surprising! https://codeforces.com/contest/1915/submission/240287325

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello! This is my first ever comment on CF. I have a question regarding prob F. I have 2 codes: one uses a vector to store left boundary of interval & one uses a set. The one using a vector is getting accepted, but the one with the set is giving TLE. Does anyone know why is that? Here are the links of the 2 submissions.

https://codeforces.com/contest/1915/submission/240288584 https://codeforces.com/contest/1915/submission/240288739

Thank you in advance :)

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    siraz16 I have the same problem. Feel free to check the 2 codes. In case you find an answer please lmk.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why G need "dist[u][k] == inf" ?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why regular set is not fast enough for the problem F? Use same logic but instead of BIT use set.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just looked at your code. If you're using set, and you call the function std::distance() between two iterators in a set, the function itself will take up O(N) time because set uses bidirectional iterator instead of random-access iterators, which is too slow. std::distance() is always linear time unless you have random-access iterators(like vectors, deque) and then it would be constant.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem F, is it possible to count number of inversions under O(N^2) without using merge sort, fenwick tree?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My Java solution for 1915F — Greetings using BIT

https://codeforces.com/contest/1915/submission/241033242

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why unordered map is giving TLE while map is not?

void solve(){

ll n; cin>>n;
vector<ll>vec(n,0);
for(auto &x : vec) cin>>x;
if(n==1){
   cout << "NO" << endl;
    return; 
}

map<ll,ll> mp;
mp[0]=1;
ll s=0;

for(int i=0; i<n; i++){

    if(i%2==0) s+=vec[i];
    else s-=vec[i];

    mp[s]++;
}

for(auto &x:mp){
    if(x.second > 1){
        cout << "YES" << endl;
        return;
    }
}
cout<<"NO"<<endl;

}

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In tutorial of 1915E what does the author mean by hash map can be hacked?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain what's wrong with my solution for F using merge sort tree? https://codeforces.com/contest/1915/submission/241313800

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone solve the question about 1915G Problem's time complexity? I knew the time complexity of the dijkstra algorithm as O((V+E)logV). My question is that assuming n*1000 nodes, the number of edges will be (n*1000)^2? I need help with how the number of E is calculated.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How did the first example of G come out, and why did I calculate and simulate it as 23

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
from sys import stdin;

T = int(stdin.readline().strip());
for _ in range(T):
	N = int(stdin.readline().strip());
	AB = dict()
	for i in range(N):
		a,b = map(int,stdin.readline().split());
		AB[a]=b;
	AB=dict(sorted(AB.items(), key=lambda e: e[1]))
	G=0;
	for i,K in enumerate(list(AB.keys())):
		G+=len([x for x in list(AB.keys())[:i] if (x>K)])
	print(G)

Why does this give TLE in F? Thanks.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

import java.util.*;

public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int cases = sc.nextInt(); while(cases-- > 0) { int glasses = sc.nextInt(); int[] juice = new int[glasses]; for(int i =0;i< glasses; i=i + 1) {

juice[i] = sc.nextInt();
        }
        HashMap<Integer, Integer> mppp = new HashMap<Integer, Integer>();
        int quantity = 0;
        mppp.put(0, 1);
        int bit = 0;
        for(int i =0; i < glasses; i += 1) {
            if(i % 2 == 1) {
                juice[i] *= -1;
            }
            quantity += juice[i];
            if(mppp.containsKey(quantity)) {
                System.out.println("YES");
                bit = 1;
                break;
            }
            mppp.put(quantity, mppp.getOrDefault(quantity, 0)+1);
        }
        if(bit == 0)

        System.out.println("NO");

    }
}

}

Why is this code giving wrong answer for problem E?

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Someone help me out with Problem G of this contest. This is my respective solution 245688650. It is giving the wrong answer in test case 3.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Take a look at Ticket 17335 from CF Stress for a counter example.

    Your current strategy is 1 --> 2 --> 1 --> 6 --> 7.

    However, the optimal strategy is 1 --> 4 --> 1 --> 2 --> 1 --> 6 --> 7.