NeekT's blog

[Help] Problem 4C-Time Limit Exceed/Runtime Error
By NeekT, history, 3 years ago, In English

Hi everyone, i'm trying to solve problem 4C. (https://codeforces.com/problemset/problem/4/C)

You have to build a database of usernames and modify the entry if the name is already taken. I defined a data structure to hold the username and the number of time it appears in the database. Then i asked for each username and checked for repetitions. This is my first attempt:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MAX_NAME 32
 
typedef struct{
  int rep;
  char name[MAX_NAME+1];
}entry_t;
 
int main(){
  entry_t* db;
  int i,j,n;
  
  scanf("%d", &n);
  db=malloc(sizeof(entry_t)*n);/*Allocate memory for the name database*/
  if(db){
    
    for(i=0; i<n; i++)  /*Set all repetions of each entry to zero*/
      db[i].rep=0;
      
    for(i=0; i<n; i++){  /*Acquire entry and check for repetitions*/
      scanf("%s", db[i].name);
      for(j=0; j<i; j++){
        if(!strcmp(db[i].name, db[j].name))
          (db[i].rep)++;
      }                   /*Print out the results*/
      if(!(db[i].rep))
        printf("OK\n");
      else
        printf("%s%d\n", db[i].name, db[i].rep);
    }
  }else
    printf("Errore allocazione memoria");
  return 0;
}

I tried to allocate the memory using the malloc function and i got the Time Limit Exceeded error code. So i tried (mostly out of desperation) to declare a big enough array to hold all the data, this way:

typedef struct{
  int rep;
  char name[MAX_NAME+1];
}entry_t;
 
int main(){
  entry_t db[10000];

and i got a different error: Runtime Error. So i tried to go bigger

typedef struct{
  int rep;
  char name[MAX_NAME+1];
}entry_t;
 
int main(){
  entry_t db[100000];
  int i,j,n;

and i got again the Time Limit Exceed error.

Can someone give me a hint about what i'm doing wrong? Also, i'd rather not use "continue" or "break" commands since my professor doesn't want me to get in the habit of it...go figure. I've seen some accepted answers that seem to be very similar to mine except for these two commands. I've also seen some people using a hashing function, which seems a really cool thing to learn but I'd like to go for a more basic approach first. Thanks.

  • Vote: I like it
  • -17
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

You haven't provided submission link , so i went through you submission and i think you are talking about this one : link .

You are using two for loops (nested) and since $$$n=1e5$$$ , it will give TLE.

You can use map to solve this problem . It's quite often used in easy problems .

not use "continue" or "break" commands since my professor doesn't want me to get in the habit of it

Can you elaborate why professor doesn't want you to use that . I don't see any issue in using that.

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

    I think the first line has the link. And yeah the Professor is weird.

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

    Thank you for your answer. He asked us not to use break and continue because he finds such instructions to be unnecessary: he said we simply don't need them if we use the for and while loop properly. I remember him mentioning something about a "Bonh-Jacopini Theorem" but take that with grain of salt since it was quite a while ago and my memory might be playing some tricks to me.

    I put the link at the very beginning of the post, but next time i will refer to it more clearly.

    "Hi everyone, i'm trying to solve problem 4C. (https://codeforces.com/problemset/problem/4/C)"

    On a side note, do you have other tips on how to ask for help on my blog? I've seen some downvotes and i guess I might be omitting some important information. I checked out the official (and unofficial) FAQ but I couldn't find much useful information.

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

      I put the link at the very beginning of the post, but next time i will refer to it more clearly.

      I meant your submission link.

      On a side note, do you have other tips on how to ask for help on my blog? I've seen some downvotes and i guess I might be omitting some important information. I checked out the official (and unofficial) FAQ but I couldn't find much useful information.

      The question you asked tells that you are just starting with CP . You should have done bit more study of time complexity. Other than that it's fine. When i was newbie i asked a doubt (blog) and got around -20 votes ;).

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

Lets see this through :

Your approach is for every string db[i].name check the database for how many times db[i].name occurred.

So you are doing 2 loops here, something like : 

for(int i = 0; i < n; i++) 
    // Take in db[i].name 
     for(int j = 0; j < i ;j++)
       // Check how many times have I seen db[i].name so far
  1. This gives a O(n^2) algorithm and since n ~ 10^5.
  2. We have to do O(10^10) operations which is not possible in the Time Limit Given.

I think you don't understand Time-Complexity for now. Watch a video or something like that.

→ Reply